<div dir="ltr"><div class="gmail_default" style="font-family:trebuchet ms,sans-serif">I am sure it will, thanks!</div><div class="gmail_default" style="font-family:trebuchet ms,sans-serif"><br></div><div class="gmail_default" style="font-family:trebuchet ms,sans-serif">lemon is a great tool</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Aug 10, 2017 at 3:44 PM, Péter Kovács <span dir="ltr"><<a href="mailto:kpeter@inf.elte.hu" target="_blank">kpeter@inf.elte.hu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi John,<br>
<br>
Thanks for the quick answer. Then I hope the code I sent will help you.<br>
<br>
Péter<span class=""><br>
<br>
<br>
2017.08.10. 23:40 keltezéssel, John Lagerquist írta:<br>
</span><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">
I use a DAG to represent a flow language that I am working on. I am<br>
trying to optimize the node order to minimize resource usage in a<br>
micro-controller, I am very RAM limited. Fortunately my "programs" are<br>
quite simple and it won't take long to simulate each ordering's resource<br>
usage and pick the best choice.<br>
<br>
<br>
<br>
On Thu, Aug 10, 2017 at 3:30 PM, Péter Kovács <<a href="mailto:kpeter@inf.elte.hu" target="_blank">kpeter@inf.elte.hu</a><br></span><span class="">
<mailto:<a href="mailto:kpeter@inf.elte.hu" target="_blank">kpeter@inf.elte.hu</a>>> wrote:<br>
<br>
Hi John,<br>
<br>
LEMON does not provide a method for finding all topological<br>
orderings. However, it is relatively easy to implement it by<br>
combining any topological ordering method and backtracking.<br>
<br>
I wrote a simple implementation that you can try, see the attached<br>
code. It builds a DAG, finds all topological orderings and prints<br>
them. The algorithm uses Kahn's well-known topological sorting<br>
method<br></span>
(<a href="https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm" rel="noreferrer" target="_blank">https://en.wikipedia.org/wiki<wbr>/Topological_sorting#Kahn.27s_<wbr>algorithm</a> <<a href="https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm" rel="noreferrer" target="_blank">https://en.wikipedia.org/wiki<wbr>/Topological_sorting#Kahn.27s_<wbr>algorithm</a>>)<span class=""><br>
combined with backtracking.<br>
<br>
However, please keep in mind that a DAG may have a huge number of<br>
topological orderings. For example, the attached code builds a graph<br>
that has 2K+2 nodes and (2K)!/(K!*K!) distinct topological<br>
orderings. The attached version uses K=3, for which 20 orderings are<br>
found, but it is 184756 for K=10 and about 10^29 for K=50.<br>
<br>
Anyway, why do you need this?<br>
<br>
Best regards,<br>
Péter<br>
<br>
<br>
Is there a method to get all possible topological sorts of a DAG?<br>
<br>
<br>
<br>
--<br>
John Lagerquist<br>
Chief Engineer<br>
RallyTronics LLC<br>
801-866-5981<br>
<br>
<br>
<br>
<br>
______________________________<wbr>_________________<br>
Lemon-user mailing list<br></span>
<a href="mailto:Lemon-user@lemon.cs.elte.hu" target="_blank">Lemon-user@lemon.cs.elte.hu</a> <mailto:<a href="mailto:Lemon-user@lemon.cs.elte.hu" target="_blank">Lemon-user@lemon.cs.el<wbr>te.hu</a>><br>
<a href="http://lemon.cs.elte.hu/mailman/listinfo/lemon-user" rel="noreferrer" target="_blank">http://lemon.cs.elte.hu/mailma<wbr>n/listinfo/lemon-user</a><span class=""><br>
<<a href="http://lemon.cs.elte.hu/mailman/listinfo/lemon-user" rel="noreferrer" target="_blank">http://lemon.cs.elte.hu/mailm<wbr>an/listinfo/lemon-user</a>><br>
<br>
<br>
<br>
<br>
--<br>
John Lagerquist<br>
Chief Engineer<br>
RallyTronics LLC<br>
801-866-5981<br>
<br>
<br>
</span></blockquote>
<br>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature" data-smartmail="gmail_signature">John Lagerquist<div>Chief Engineer<br><div>RallyTronics LLC</div><div>801-866-5981</div><div><br></div><div><br></div></div></div>
</div>