385 questions
3
votes
3
answers
108
views
Iterative graph traversal: non-BFS and non-DFS ordering
Consider this traversal algorithm in pseudocode:
Traverse(G, v):
S is stack
stack.push(v)
label v as visited
while S is not empty:
v = S.pop()
for all w in G....
- 63
3
votes
1
answer
154
views
Efficient Algorithems to find position of vector in 2D array
I have an interesting problem but cannot find the relevant literature, so need algorithem suggestions or just the correct way to phrase the problem so I can find the literature.
I'm given a vector of ...
- 1,559
2
votes
1
answer
105
views
For given edge, find all nodes the edge lies on any path from
I have undirected connected graph with one main node (denoted by M in examples below).
I am trying to find efficient algorithm to following specification:
input is set of edges (denoted by thick ...
- 12.3k
0
votes
0
answers
54
views
Indirect and direct link in a tree
Suppose 3 sets of nodes, each corresponding to a distinct set in an undirected graph:
Set-A = {1, 2, 3, 4, 5}
Set-B = {6, 7, 8, 9, 10}
Set-C = {11, 12, 13, 14, 15}
The graph is defined by ...
0
votes
0
answers
37
views
Neo4j traversal framework - how to effectively test some node is not reached
I have a Neo4j 5.26 database with graph (minimized example):
CREATE (x1:L {id:1})-[:R]->(x2:L {id:2})-[:R]->(x3:L {id:3})
-[:R]->(x4:L {id:4})-[:R]->(x5:L {id:5})
and some ...
- 12.3k
2
votes
1
answer
135
views
Graph traversal algorithm using shapely geometry points
I am trying to create a path planning algorithm for a robotic mower to cut all the grass in a defined area while avoiding obstacles or restricted areas. I am using the Python Shapely library to define ...
- 43
5
votes
5
answers
315
views
Finding loops between numbers in a list of sets
I marked my answer as the answer because it is the one that is doing what I was wanting and anyone wanting to do the same thing should start there. But I would love to see a better answer (order of ...
- 19.6k
2
votes
1
answer
234
views
Why are back edges and forward edges said to be impossible in BFS for an undirected graph?
Is it true that there are no back edges and no forward edges in a BFS of an undirected graph?
I feel this is incorrect. Here is my counterexample (graph is represent using adjacency list):
0 : 1
...
- 131
0
votes
1
answer
46
views
Dynamic WITH statement
Is it possible to dynamically construct a WITH statement?
I have to do a graph traversal, but I don't know in advance which collections contain the graph nodes. I have tried to create the statement ...
- 43
0
votes
1
answer
71
views
gremlin apache: how to use the weights of edges to define the order in which an edge is followed?
I'm trying to traverse a graph (directed) where the edges have weights.
How do I use the weights to define the order in which an edge is followed: the lower the weight (module of the weight to be ...
0
votes
1
answer
151
views
Postgres slow recursive CTE graph traversal due to visited edges
I have a postgres table with a 100K± records representing edges of graph (will grows even to 1M) defined as (I left the relevant parts only):
CREATE TABLE public.collection_lineages (
id int8 NOT ...
- 101
-1
votes
1
answer
50
views
Which algorithm can I use to number the graph as follows
Each node in the above graph has been numbered.
I am trying to find the graph traversal algorithm that can be used to number the graph in this order. Appreciate if anyone can suggest an algorithm that ...
- 510
0
votes
1
answer
42
views
Find shortest path from multiple source vertex and output the each path length sum against the target vertices
I have written the below AQL shortest path traversal query to find the shortest paths from a set of start vertices to a set of target vertices.
In the output I would like a consolidated result. ...
- 2,064
0
votes
0
answers
130
views
Given an undirected weighted graph, how to find the minimum cost so that I can start from any node and traverse all other nodes that is in the graph?
Title: Finding the Maximum of Minimum Costs in a Modified Kruskal's Algorithm
Question:
I'm working on a graph problem where I need to find the maximum of the minimum costs starting from a specific ...
- 1
1
vote
0
answers
36
views
Approximation Algorithms for the Longest Simple Path in a Directed Graph
I am implementing a new approximation algorithm for finding the longest simple path in a directed, unweighted graph from a starting node s to a destination node t. I would like to compare my algorithm'...
- 11