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

[John Lagerquist]

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


-- 
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/17d30a72/attachment.html>