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 <kpe...@inf.elte.hu
<mailto:kpe...@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@lemon.cs.elte.hu <mailto:Lemon-user@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



_______________________________________________
Lemon-user mailing list
Lemon-user@lemon.cs.elte.hu
http://lemon.cs.elte.hu/mailman/listinfo/lemon-user

Reply via email to