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

[Péter Kovács]

Hi John,

Thanks for the quick answer. Then I hope the code I sent will help you.

Péter


2017.08.10. 23:40 keltezéssel, John Lagerquist írta:
> I use a DAG to represent a flow language that I am working on.  I am
> trying to optimize the node order to minimize resource usage in a
> micro-controller, I am very RAM limited.  Fortunately my "programs" are
> quite simple and it won't take long to simulate each ordering's resource
> usage and pick the best choice.
>
>
>
> On Thu, Aug 10, 2017 at 3:30 PM, Péter Kovács <kpeter at inf.elte.hu
> <mailto:kpeter at inf.elte.hu>> wrote:
>
>     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 <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 <mailto:Lemon-user at lemon.cs.elte.hu>
>         http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>         <http://lemon.cs.elte.hu/mailman/listinfo/lemon-user>
>
>
>
>
> --
> John Lagerquist
> Chief Engineer
> RallyTronics LLC
> 801-866-5981
>
>