Topological ordering to schedule tasks (digraph)

[Frank Muller]

Hi Vladimir

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

Thus, the adjacency lists is what I’m looking for:

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

This result requires a little twist to solve my issue.

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:
[{a,[c,b]},{b,[]},{c,[d]},{d,[]}]

Thanks
/Frank


> 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/8003963e/attachment.htm>