views:

109

answers:

2

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
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
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
Does it have to be the largest? Could you use a heuristic that finds a large sub-graph?
ConcernedOfTunbridgeWells
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
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
A: 

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

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