Topological ordering to schedule tasks (digraph)

[Vladimir Ralev]

Did you mean the desired output should be this (with the "d" present as an
"a" dependency)? Like this:

 [{a, [b, c, d]}, {b, []}, {c, [d]}, {d, []}]

You can just look up the adjacency lists for each node in the already
sorted list:

Deps = [{V, digraph:out_neighbours(G, V)} || V <- digraph_utils:topsort(G)].
[{a,[d,c,b]},{b,[]},{c,[d]},{d,[]}]

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.

If I understand your case, a normal DFS would be more efficient.


On Tue, Nov 23, 2021 at 9:41 PM Frank Muller <frank.muller.erl@REDACTED>
wrote:

> Hi everyone,
>
> I’m trying to use “digraph” and related modules to find dependencies
> between tasks.
>
> Here’s an example:
>
> 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
>
> Using digraph:
>
> 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]
>
>
> Would it be possible to get the following "topological ordering” instead?
>
> [{a, [b, c]}, {b, []}, {c, [d]}, {d, []}]
>
>
> This way, I can easily schedule and order my tasks:
> 1. task “a" has to be performed after “c" and “d” are completed
> 2. similarly, “c" has to be done after “d”
> 3. finally, “b" and “d" can be run first, in parallel and without any
> constraint
>
> Thanks
> /F.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20211123/f449ba70/attachment.htm>