<div dir="auto">Hi Vladimir </div><div dir="auto"><br></div><div dir="auto">You are totally right. I made a mistake in my orignal post. In fact, b and c can run in parallel (not b and d). </div><div dir="auto"><br></div><div dir="auto">Thus, the adjacency lists is what I’m looking for:</div><div dir="auto"><div style="font-size:1rem;word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto"><div style="font-size:1rem;border-color:rgb(49,49,49)" dir="auto"><br></div><div style="font-size:1rem;border-color:rgb(49,49,49)">Deps = [{V, digraph:out_neighbours(G, V)} || V <- digraph_utils:topsort(G)].<br></div></div><span style="word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)">[{a,[d,c,b]},{b,[]},{c,[d]},{</span><span style="word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)">d,[]}]</span><br></div><div dir="auto"><span style="word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)"><br></span></div><div dir="auto"><span style="word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)"><span style="word-spacing:0px;border-color:rgb(0,0,0);color:rgb(0,0,0)">This result requires a little twist to solve my issue.</span></span></div><div dir="auto"><span style="word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)"><br></span></div><div dir="auto"><span style="word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)">We know that c depends on d. So, can we use digraph to drop d from a’s dependencies list. To get  something ike this:</span></div><div dir="auto"><span style="font-size:1rem;word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)">[{a,[c,b]},{b,[]},{c,[d]},{</span><span style="font-size:1rem;word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)">d,[]}]</span><br></div><div dir="auto"><span style="font-size:1rem;word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)"><br></span></div><div dir="auto"><span style="font-size:1rem;word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)">Thanks</span></div><div dir="auto"><span style="font-size:1rem;word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)">/Frank</span></div><div><br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;padding-left:1ex;border-left-color:rgb(204,204,204)"><div dir="ltr"><br>Did you mean the desired output should be this (with the "d" present as an "a" dependency)? Like this:<div><br></div><div> [{a, [b, c, d]}, {b, []}, {c, [d]}, {d, []}]<div> <br>You can just look up the adjacency lists for each node in the already sorted list:</div><div><br>Deps = [{V, digraph:out_neighbours(G, V)} || V <- digraph_utils:topsort(G)].<br></div></div>[{a,[d,c,b]},{b,[]},{c,[d]},{d,[]}]<div><br></div><div>It looks like it will still be difficult to determine that "b" and "d" can run in parallel here without re-scanning the entire list for visited child nodes since you would have to skip over the "c" node if you scan backwards or the "a" node if you scan forward. And then again in the next round.<div><br></div><div>If I understand your case, a normal DFS would be more efficient.</div></div></div><br><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Nov 23, 2021 at 9:41 PM Frank Muller <<a href="mailto:frank.muller.erl@gmail.com" target="_blank">frank.muller.erl@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;padding-left:1ex;border-left-color:rgb(204,204,204)"><span style="word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)">Hi everyone,</span><div style="word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto"><br></div><div style="font-size:1rem;word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto">I’m trying to use “digraph” and related modules to find dependencies between tasks.</div><div style="word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto"><br></div><div style="font-size:1rem;word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto">Here’s an example:</div><div style="word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto"><a href="https://dreampuf.github.io/GraphvizOnline/#digraph%20G%20%7B%0A%20%20a%20-%3E%20b%3B%0A%20%20a%20-%3E%20c%3B%0A%20%20a%20-%3E%20d%3B%0A%20%20c%20-%3E%20d%3B%0A%7D" style="font-size:1rem;border-color:rgb(66,133,244)" target="_blank">https://dreampuf.github.io/GraphvizOnline/#digraph%20G%20%7B%0A%20%20a%20-%3E%20b%3B%0A%20%20a%20-%3E%20c%3B%0A%20%20a%20-%3E%20d%3B%0A%20%20c%20-%3E%20d%3B%0A%7D</a></div><div style="word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto"><br></div><div style="font-size:1rem;word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto">Using digraph:</div><div style="word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto"><br></div><div style="word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto"><pre style="white-space:pre-wrap;box-sizing:inherit;margin-top:4px;margin-bottom:4px;padding:8px;line-height:1.50001;font-variant-ligatures:none;word-break:normal;border-top-left-radius:4px;border-top-right-radius:4px;border-bottom-right-radius:4px;border-bottom-left-radius:4px;font-family:Monaco,Menlo,Consolas,"Courier New",monospace;font-size:1rem;border:rgb(55,56,58);background-color:rgba(29,28,29,0.04);color:rgb(55,56,58)">G = digraph:new(),
digraph:add_vertex(G, a),
digraph:add_vertex(G, b),
digraph:add_vertex(G, c),
digraph:add_vertex(G, d),

digraph:add_edge(G, a, b),
digraph:add_edge(G, a, c),
digraph:add_edge(G, a, d),
digraph:add_edge(G, c, d),

digraph_utils:topsort(G).
[a,b,c,d]
</pre><div style="border-color:rgb(49,49,49)"><br></div></div><div style="font-size:1rem;word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto">Would it be possible to get the following "topological ordering” instead?</div><div style="word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto"><br></div><div style="word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto"><pre style="white-space:pre-wrap;box-sizing:inherit;margin-top:4px;margin-bottom:4px;padding:8px;line-height:1.50001;font-variant-ligatures:none;word-break:normal;border-top-left-radius:4px;border-top-right-radius:4px;border-bottom-right-radius:4px;border-bottom-left-radius:4px;font-family:Monaco,Menlo,Consolas,"Courier New",monospace;font-size:1rem;border:rgb(55,56,58);background-color:rgba(29,28,29,0.04);color:rgb(55,56,58)">[{a, [b, c]}, {b, []}, {c, [d]}, {d, []}]</pre><div style="border-color:rgb(49,49,49)"><br></div></div><div style="font-size:1rem;word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto">This way, I can easily schedule and order my tasks:</div><div style="font-size:1rem;word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto">1. task “a" has to be performed after “c" and “d” are completed</div><div style="font-size:1rem;word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto">2. similarly, “c" has to be done after “d”</div><div style="font-size:1rem;word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto">3. finally, “b" and “d" can be run first, in parallel and without any constraint</div><div style="word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto"><br></div><div style="font-size:1rem;word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto">Thanks</div><div style="font-size:1rem;word-spacing:1px;border-color:rgb(49,49,49);color:rgb(49,49,49)" dir="auto">/F.</div>
</blockquote></div>
</blockquote></div></div>