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?
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