javascript - How to ignore cycles in a topological sort? - Stack Overflow

admin管理员组

文章数量:1316818

I am using this library to perform a topological sort on a graph in JS. The problem is that in some rare cases the graph will contain cycles. Those are a minor part of the structure, so dropping a few edges would not affect the final result considerably. Yet the algorithm just breaks when they appear. What is the most efficient way to update it so it won't crash if there is a cycle or two?

I am using this library to perform a topological sort on a graph in JS. The problem is that in some rare cases the graph will contain cycles. Those are a minor part of the structure, so dropping a few edges would not affect the final result considerably. Yet the algorithm just breaks when they appear. What is the most efficient way to update it so it won't crash if there is a cycle or two?

• javascript
• algorithm
• sorting
• graph

Share Improve this question Follow asked Aug 17, 2013 at 8:12 MaiaVictorMaiaVictor 53.1k4747 gold badges157157 silver badges301301 bronze badges

Add a ment  | 

2 Answers 2

Sorted by: Reset to default 9

According to wikipedia:

A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).

Thus, you can not find a valid topsort if the graph contains cycles. I guess the library you've used has a requirement on the input graph to be a DAG. Consequently, the algorithm breaks because of that requirement.

However, if you still want to find some topsort, you can do one of the following modifications of the graph: 1) Construct a random spanning tree of the graph. In this way, you would modify the graph to be a DAG and you can run the topsort algorithm on the new graph.

2) Find the strongly connected ponents of the graph (with Tarjan's strongly connected ponents algorithm). The new graph is a DAG and therefore you can run on it the topsort algorithm.

I'm suggesting you those two options as there will be at least a couple of JavaScript libraries which have those algorithms (for 1. you can use an library which constructs the minimal spanning tree of the graph (MST)). Optimally implemented, both algorithms have a linear plexity.

In addition, you can run your own modified DFS algorithm, which deletes a single edge of every graph cycle it finds.

The problem of minimizing the number of arcs removed to leave an acyclic graph is called feedback arc set. The topological sort to which you linked uses the algorithm that repeatedly finds a vertex of in-degree 0 and removes it. It's not far to the Eades–Lin–Smyth heuristic for feedback arc set, which can be summarized as follows. If there is a vertex v of in-degree 0, remove it, recurse on the residual graph, and prepend v to the order. If there is a vertex v of out-degree 0, remove it, recurse on the residual graph, and append v to the order. Otherwise, let v have maximum out-degree minus in-degree, remove all of its ining arcs, and continue.

本文标签： javascriptHow to ignore cycles in a topological sortStack Overflow