Sorting a graph to make as many arrows point forward as possible

views:

109

answers:

Sorting a graph to make as many arrows point forward as possible

I need to sort the nodes of a directed graph such that the number of arrows that flow backwards (against the sorting order) is minimal.

I can think of algorithms (e.g. keep swapping nodes until no swap will improve things) but I'm not sure how fast they run or whether they arrive at the best solution.

What is the name and complexity of this problem?

+2 A:

Sorting nodes in order of depth can be done with a topological sort. However, this will only work with graphs that contain no cycles. Your problem sounds like there are cycles in the graph. One option would be to find the cycles (see the Tortoise and Hare algorithm for a method of doing this) and break the cycle, recording where you broke it. Then sort the nodes and re-link.

If you are doing this for visualisation purposes there is a graph rendering library called GraphViz that does something very similar to what you are describing and then lays out the nodes. It is easy to integrate and use and will render to the screen or a variety of different output formats.

ConcernedOfTunbridgeWells 2009-04-21 08:18:11

Thanks. Topological sort can be generalised to work with cycles, basically using your idea, but that doesn't quite give me the ordering I'm looking for. We do feed these graphs to GraphViz by the way, but I need to sort them as well.

reinierpost 2009-04-21 23:05:28

PS I thought about it some more and what I really want is to find a largest acyclic subgraph within the graph, then topsort that. And the first problem is NP-hard :-(

reinierpost 2009-06-09 15:50:24

Does it have to be the largest? Could you use a heuristic that finds a large sub-graph?

ConcernedOfTunbridgeWells 2009-06-10 11:32:24

Yes, in principle; I suppose an incremental algorithm would be best, that just tries to find larger subgraphs until some limit is exceeded that is passed as an argument.

reinierpost 2009-06-15 07:10:15

You can use integer programming as a heuristic to solve travelling salesman problems. It won't necessarily find an optimal path (something to do with local minima I expect) but it will usually find a good one. There are other heuristics that can be used as well. Maybe something like this can be adapted to your problem.

ConcernedOfTunbridgeWells 2009-06-15 09:03:29

After some thought I realized that the problem can be split in two:

determine a largest acyclic subgraph of a graph (which is NP-hard)
topologically sort it (which is a lot easier)

reinierpost 2009-07-22 08:23:20

ansaurus

tags:

views:

answers:

Sorting a graph to make as many arrows point forward as possible

related questions