Stable topological order gives unexpected result

[maximebuyse]

Here is a code snippet that builds a graph and prints the vertices in stable topological order:

module G = Graph.Persistent.Digraph.Concrete (String)

let g0 = G.empty 

let g1 = G.add_edge g0 "a" "b"
let g2 = G.add_edge g1 "a" "c" 
let g = G.add_edge g2 "c" "a" 

module Topo = Graph.Topological.Make_stable (G)

let () = Topo.iter (fun v -> print_endline v) g

The graph created here can be represented as b <- a <-> c, and the topological order given by ocamlgraph is: a, b, c.

It seems to me that this is not a valid topological order because b comes before c and the definition given in the doc is: if vertex x is visited before vertex y then either there is a path from x to y, or there is no path from y to x. Here there is no path from b to c but there is a path from c to b. So my understanding is that c should come before b. The stable order is supposed to take the comparison function (here alphabetical order) only between vertices that are topologically equivalent which I believe b and c are not in this example.

Note that if one uses the classic topological order (Make instead of Make_stable) the order is a, c, b

[maximebuyse]

The problem seems to be that when dealing with a cycle, all vertices of the cycles are added to the queue. When treating a vertex from the queue, its successors are added to the queue (if they have degree 0) and can later bypass the other vertices of the cycle that are still in the queue (because we don't take order of insertion into account when dequeuing).

A possible fix could be to treat all vertices of the cycles at the same time without using the queue. I implemented this and it seems to work (at least on the example above). I opened a PR with the change.