How to represent a dependency graph with alternative paths
I am having trouble presenting and manipulating dependency plots in this scenario:
- a node has some dependencies that need to be addressed.
- Each path must not have dependency loops (for example, in DAG diagrams).
- each dependency can be solved by more than one other node
I start at the target node and loop through its dependencies recursively, but must have the above properties, specifically the third one.
Here's just a small example:
I would like to have a graph similar to the following
(A)
/ \
/ \
/ \
[(B),(C),(D)] (E)
/\ \
/ \ (H)
(F) (G)
which means:
- F, G, C, H, E have no dependencies
- D depends on H
- B depends on F and G
- A depends on E and
- B or
- C or
- D
So, if I write down all the possible topologically sorted paths to A, I should have:
- E → F → G → B → A
- E → C → A
- E → H → D → A
How do I simulate a graph with these properties? Which data structure is more suitable for this?
source to share
You should use a regular adjacency list with an additional property where node knows its other nodes, which will also satisfy the same dependency. This means that B, C, D must know that they belong to the same equivalence class. You can achieve this by inserting them all into a set.
Node:
List<Node> adjacencyList
Set<Node> equivalentDependencies
To use this data structure in a toposort, whenever you remove the original code and remove all of its outgoing edges, also remove the nodes in the equivalence class, their outgoing edges, and recursively remove the nodes that point to them, 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 o in the equivalency class of n <===removing equivalent dependencies
remove j from S
for each node k with an edge e from j to k do
remove edge e from the graph
if k has no other incoming edges then
insert k into S
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
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
This algorithm will give you one of the modified topologically sorted paths.
source to share