3

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:

Starting input graph

And this would be a valid output graph:

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!

Adam
  • 43,763
  • 16
  • 104
  • 144

2 Answers2

5

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.
Victor Sergienko
  • 13,115
  • 3
  • 57
  • 91
  • What are some of the algorithms that exist? – Adam Dec 14 '10 at 22:07
  • I believe, Wikipedia article links to some, see link to "Maximum flow problem". "Perfect matching in bipartitive graph" is a special case of maximum flow problem, if you add a source node to P1 and sink to P2, with all edges' weight of 1. I recommend Ford–Fulkerson algorithm, it's pretty simple to implement. – Victor Sergienko Dec 14 '10 at 22:18
  • Where can I learn how to implement one of these algorithms in Java? The wikipedia articles use Graph Theory mathematical notation and terminology which is difficult for me to understand. Is there a place where I can see the algorithms implemented in Java or at least explained in pseudo code? – Adam Dec 14 '10 at 22:44
0

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).

Community
  • 1
  • 1
Rafe
  • 5,237
  • 3
  • 23
  • 26