[Lemon-user] all possible topological sorts of a DAG

[Péter Kovács]

Hi John,

LEMON does not provide a method for finding all topological orderings. 
However, it is relatively easy to implement it by combining any 
topological ordering method and backtracking.

I wrote a simple implementation that you can try, see the attached code. 
It builds a DAG, finds all topological orderings and prints them. The 
algorithm uses Kahn's well-known topological sorting method 
(https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm) 
combined with backtracking.

However, please keep in mind that a DAG may have a huge number of 
topological orderings. For example, the attached code builds a graph 
that has 2K+2 nodes and (2K)!/(K!*K!) distinct topological orderings. 
The attached version uses K=3, for which 20 orderings are found, but it 
is 184756 for K=10 and about 10^29 for K=50.

Anyway, why do you need this?

Best regards,
Péter


> Is there a method to get all possible topological sorts of a DAG?
>
>
>
> --
> John Lagerquist
> Chief Engineer
> RallyTronics LLC
> 801-866-5981
>
>
>
>
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dag.cpp
Type: text/x-c++src
Size: 3111 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20170810/c81f71b4/attachment.cpp>