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

[John Lagerquist]

I am sure it will, thanks!

lemon is a great tool

On Thu, Aug 10, 2017 at 3:44 PM, Péter Kovács <kpeter at inf.elte.hu> wrote:

> 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
>>
>>
>>
>


-- 
John Lagerquist
Chief Engineer
RallyTronics LLC
801-866-5981
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20170810/7d04ce28/attachment.html>