开发者

Graphing Algorithm To Match Nodes

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:

Graphing Algorithm To Match Nodes

And this would be a valid output graph:

Graphing Algorithm To Match Nodes

This is valid because:

  • It cont开发者_如何学Goains 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!


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.


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

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜