Reputation: 171
The image below shows a not-so-trivial, but heavily scaled-down version in terms of number of nodes of the problem I'm facing.
Suppose that there's a start node, labelled "a" and a goal node, labelled "Z" in a multigraph. Between "a" and "Z" there are lots of paths, like "a-Z", "a-b-g-Z", etc. (highlighted with bold in the picture), which, combined form a graph of their own.
Is it there a standard algorithm to identify this sub-graph?
Upvotes: 2
Views: 51
Reputation: 3123
Yes, there is such an algorithm.
A vertex v
is part of the subgraph if and only if: v
is reachable from a
in G \ {Z}
, and v
is reachable from Z
in G \ {a}
.
All you need to do is implement a "reachability algorithm" (a simple graph traversal does the job) for every vertex in the graph.
Edit: this solution is not correct. One has to verify that there exists a path p1
from a
to v
and there exists a path p2
from v
to Z
such that p1
and p2
are disjoint. A naive implementation could quickly become intractable for large graphs.
Upvotes: 1