Menu
My problem is very simple but I don't really know its name and therefore, it's hard to find a solution by myself :
How to simplify a dependency graph like (where -> means depends):
A -> B -> C & A -> C
to
A -> B -> C
999
A dependency graph is a data structure formed by a directed graph that describes the dependency of an entity in the system on the other entities of the same system. The underlying structure of a dependency graph is a directed graph where each node points to the node on which it depends.
A dependency graph is used to represent the flow of information among the attributes in a parse tree. In a parse tree, a dependency graph basically helps to determine the evaluation order for the attributes.
In mathematics, computer science and digital electronics, a dependency graph is a directed graph representing dependencies of several objects towards each other. It is possible to derive an evaluation order or the absence of an evaluation order that respects the given dependencies from the dependency graph.
You are looking for transitive reduction.
For a discussion of algorithms, see Transitive Closure and Reduction.
198
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
