I have problem that’s quite different to many questions about DAGs and am thus having a hard time finding answers. That may mean that it’s just very simple.
Background: I have to build the Terraform DAG in Python by parsing the statefile. The graph is known to be acyclic and all nodes are connected to a single root in my implementation. All nodes store the full list of their ancestors as a flat list.
So the question is not about the specific programming implementation but about the algorithm I would need to use for this. I’ve been using different sample graphs for myself and can’t say for sure that they cover all potential problems but I’ve found some that stumped me even there.
They essentially all boil down to deciding whether there is something directly between two nodes.
Example.
Forward ("deps of") Reverse ("depends on")
g --> a <-------. a = [] a = [bcdefghi]
^ ^^ | b = [aefi] b = [c]
| | \ | c = [abdfi] c = []
h | \ | d = [afi] d = [c]
b-> e | e = [afi] e = [b]
^ | | f = [ai] f = [bcde]
| v | g = [a] g = [h]
c f --> i h = [ag] h = []
| ^ i = [a] i = [bcdef]
v |
d---'
Given only the two columns on the right, how can I derive the DAG on the left? Is there maybe a standard algorithm for this that I’m unaware of?
(I sincerely hope I didn’t make any confusing mistakes in the graph or lists but I’ve staring at these things for way too long by now.)
>Solution :
In your example, you could add an edge from h to a. It would change the graph (while keeping it a DAG), but it would not change either of those columns.
The task is impossible.