I need to find all edges which are on any path between two nodes [src, dest] in a directed graph.
Means that each edge (from base to head) has to satisfy:
- there is a path from src to base
- there is a path from head to dest
I could collect all edges which are connected to src and collect all edges which are connected in inverse direction to dest and compute the intersection of them.
But there has to be an algorithm, right? (Don't know if there can be a more efficient) So I am searching for the name, or clever solutions to solve it with existing algorithms.
To get an overall result I'll report what I did.
I implemented the in the question mentioned algorithm. (Lets call it thigg's algorithm, because noone mentioned a name)
Thigg's algorithm:
As mentioned by Edward Doolittle in his answer the graph can be optimized before by identifying Strongly-Connected-Components and reducing them to one node. This would reduce the effort of the algorithm on each run.
I implemented thiggs algorithm with the Boost-Graph-Library (without SCC optimization) where
a
is the source andb
the destination vertex:I used a breadth first search to get a list of all vertexes which are reachable by
a
:Where vis is a custom visitor which puts all the visited vertexes to a list. Then it reverts the graph to get all vertexes which can reach b
And finally computes the intersection:
Note that your graph has to be bidirectional in order to use
make_reverse_graph
.The algorithm also works for edges as mentioned in the question.