Menu
I'm looking for a data structure that will store any DAG, but can efficiently (i.e., sub-linearly in the number of edges/vertices) detect if adding an edge would create a cycle (and thus prevent you from breaking the acyclic invariant). Does anyone know of such a thing?
Thanks!
321
A DAG is an information or data structure which can be utilized to demonstrate diverse problems. It is an acyclic graph in topological ordering. Each directed edge has a certain order followed by the node. Every DAG starts from a node that has no parents and end with one that has no kids.
Since a DAG is defined by Python code, there is no need for it to be purely declarative; you are free to use loops, functions, and more to define your DAG.
The Directed Acyclic Graph (DAG) is used to represent the structure of basic blocks, to visualize the flow of values between basic blocks, and to provide optimization techniques in the basic block.
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles.
You could maintain a datastructure about the graph's transitive closure. Then checking whether adding an edge causes cycles is done in constant time; if you want to add edge (i,j), check if there is already a path from j to i. However, updating the datastructure could be more costly in general (see e.g. La Poutré and van Leeuwen).
175
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
