CODEWITHSUNDEEP
graphcombinatoricstopological-sort
Jean-Baptiste
Jean-Baptiste

Reputation: 31

Dependency Multi-Graph: Topological Sort and evaluation of graphs with duplicate edges

I have a dependency graph where one of the nodes requires two copies of a previous node to be satisfied. I want to use the topological ordering to get an evaluation order, but the problem is that the topological sort ignores the parallel/multi edges, and just treats it as one dependency. Am i modeling things wrong, or do i need a specific toposort that works with multigraphs?

Upvotes: 5

Views: 990

Answers (1)

Ante
Ante

Reputation: 5448

It can be done with modification of topological sort algorithm.

Original algorithm stores set of all nodes with no incoming edges (S), and main step is to take one node from S, removes it from S, and remove all of it's edges from graph and check are there other nodes without incoming edges.

Changing that to: take one node from S, remove one instance of edge to each neighbour, if node doesn't have outgoing edges remove it from S, check are there other nodes without incoming edges.

Code of original from Wikipedia:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S

Changed algorithm:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    take a node n from S
    add n to tail of L
    for each neighbouring node m of n
        remove ONE edge (m,n) from the graph
        if m has no other incoming edges then
            insert m into S
    if n doesn't have outgoing edges
       remove n from S

Upvotes: 3

Related Questions