Questions tagged [graph-traversal]
The graph-traversal tag has no summary.
56 questions
2votes
1answer
221views
Is there a multidimensional topological sort of a directed acyclic graph?
In my application, I perform a topological sort of nodes where an integer represents a node's ID using DFS and white/gray/black coloring. See https://yuminlee2.medium.com/topological-sort-cf9f8e43af6a ...
- 169
2votes
2answers
404views
Best-first search on a graph
I am working through an example of best-first search on a graph, and I'm having some trouble understanding exactly what the process should be. This is the graph I have: The heuristic values are in ...
0votes
2answers
226views
Drawing all lines from right to left - fast
I have several drawings from SVG files which basically contain basic outlines of figures. They are constructed in segments of various shapes (lines, ellipse arcs, Bezier curves ect.) Something like ...
- 127
0votes
1answer
1kviews
Find duplicate subgraphs in directed graph?
Is there a good way to search for duplicate subgraphs in an immutable directed graph, where edges and nodes may be labeled? I was thinking I could try to name the nodes according to their position in ...
- 2,863
2votes
1answer
628views
Neo4j graph performance: should I cache slow queries in a separate database?
Setup/Intro I have 10k+ nodes in my Neo4j graph in which I need to display a sub-graph (100-500 nodes) between 2 start/end nodes on the frontend app along with info about the critical path and all ...
- 121
2votes
2answers
355views
Collaborative graph exploration algorithm
Given a minimum spanning tree in an unweighted graph of (10 .. 500) vertices and (vertice_count .. 1000) edges. Each vertex can have up to 6 edges. Given K agents/bots/processes/etc.., all starting ...
- 41
1vote
1answer
220views
How to apply Graphs/Trees/BFS/DFS concepts to Lists
I have been doing problems on LeetCode recently, and keep getting stuck on some graph or tree problems. I understand the underlying concepts of Graphs, Trees, and different methods of traversal just ...
- 147
1vote
2answers
116views
How important is the data to assess code coverage?
per the title how important is the data in assessing code coverage? As background, let's say that you're given 20% of the entire dataset to help trace the different pathways each row of data goes ...
0votes
1answer
1kviews
Walking a graph without recursion
I'm working on a class that receives a relational EDM/data model (e.g. a SQL DB or OData API manifest) and performs a couple tasks on them (not necessarily at the same time, could be two separate runs)...
- 170
1vote
2answers
109views
Algorithm. Find the group of documents with the least amount of words
I need help with a problem which I have been working for the last month. I have a group of documents, each document has a set of unique words (if the word appears more than once in the document, I ...
- 119
1vote
1answer
54views
Modified graph traversal
This question is most easy to describe as a modification of that my question. Suppose that question is solved as the following Python class: class Traversal(object): # ... def next(self): # ...
- 791
0votes
1answer
118views
Not sure how to setup my data for a waypoint system
I have a system i've written on paper and am trying to write this into C# in a easy to use manner. I want a series of connected waypoints (where by waypoints can be connected to any number of other ...
- 2,092
2votes
2answers
398views
Algorithm to select sets of objects while maximizing number of objects covered
If we have different objects, [A1, A2, A3, B1, B2, B3, B4, B5] Some calculations will be performed to find compatible objects. For example, lets assume following 3 sets were formed and every set ...
- 131
6votes
1answer
587views
Toll placement problem (Graph theory)
I'm working on a problem that reduces to something like toll plaza placement on a set of highways. Given a large undirected graph and a list of node pairs with a toll value between them, I need to ...
0votes
1answer
731views
Heuristic for optimising the traveling salesman problem (tsp) in under O(n²)
I have a large data set (more than 3 Million distinct data points that have 6 integer numbers). I want to compute the shortest route in terms of hamming distance. (amount of numbers that change ...
- 103
