Menu
Given an array arr[] of size N. There is an edge from i to arr[i]. The task is to convert this directed graph into tree by changing some of the edges. If for some i, arr[i] = i then i represents the root of the tree.
A polytree (or directed tree or oriented tree or singly connected network) is a directed acyclic graph (DAG) whose underlying undirected graph is a tree. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is both connected and acyclic.
A Tree is just a restricted form of a Graph. Trees have direction (parent / child relationships) and don't contain cycles. They fit with in the category of Directed Acyclic Graphs (or a DAG). So Trees are DAGs with the restriction that a child can only have one parent.
A directed graph is a forest (or tree) if when all edges are converted to undirected edges it is undirected forest (or tree). A rooted tree is a tree with one vertex designated as the root. For a directed graph the edges are typically all directed toward the root or away from the root.
I have been looking for C# examples to transform a DAG into a Tree.
Does anyone have an examples or pointers in the right direction?
Clarification Update
I have a graph that contains a list of modules that my application is required to load. Each module has a list of modules it depends on. For example here are my modules, A, B C, D and E
I want resolve dependencies and generate a tree that looks like this...
--A
--+--B
-----+--C
---------+--D
--+--E
Topological Sort
Thanks for the information, if I perform a Topological sort and reverse the output i will have the following order
I want to maintain the hierarchical structure so that my modules are loaded into the correct context, for example... module E should be in the same container as B
Thanks
Rohan
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