Questions tagged [graph-traversal]
The graph-traversal tag has no summary.
56 questions
2
votes
1
answer
253
views
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 ...
- 195
2
votes
2
answers
459
views
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 ...
0
votes
2
answers
243
views
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
0
votes
1
answer
1k
views
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,883
2
votes
1
answer
654
views
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
2
votes
2
answers
388
views
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
1
vote
1
answer
237
views
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
1
vote
2
answers
134
views
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 ...
- 41
0
votes
1
answer
1k
views
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
1
vote
2
answers
126
views
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
1
vote
1
answer
71
views
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
0
votes
1
answer
129
views
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
2
votes
2
answers
429
views
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
6
votes
1
answer
689
views
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 ...
- 73
0
votes
1
answer
748
views
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