Graphing Algorithm To Match Nodes

Question

Given a directed graph, what is an algorithm I can use to find a random subset of its edges so that every node has exactly one incoming and exactly one outgoing edge?

For example, this could be the graph I am given:

And this would be a valid output graph:

This is valid because:

• It contains all the nodes on the input graph
• All its edges are also on the input graph
• Every node has exactly one edge leaving it and one edge coming to it (and that can't be the same edge, no loops are allowed, every node has to connect to at least one other node).

If there is no possible solution that should be detected.

Is there an efficient algorithm to solve this?

Thanks!

Answer 1

It's a node cycles coverage problem. It can be solved as Maximum matchings in bipartite graphs.

In short:

1. Split every node in two, each in one partition of a graph, so that all edges go from partition P1 to partition P2. In your sample, nodes A and D will turn into nodes A1, D1 in partition P1 and A2, D2 in P2. Edge A-D will turn into A1-D2, and D-A - to D1-A2.
2. Then find a maximum matching, some algorithms exist.
3. Then merge the nodes back, and you got a cycle coverage.

Answer 2

You're trying to decompose a graph into a set of cycles.

This link points you to Tarjan's algorithm for finding cycles in a graph.

After that, you'll need some search strategy (some choices of cycles may not lead to a solution given your constraints).