wojas
wojas

Reputation: 171

Subgraph in multigraph

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?

example

Upvotes: 2

Views: 51

Answers (1)

m.raynal
m.raynal

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

Related Questions