将有向无环图（DAG）转换为树

|| 我正在尝试实现算法，将有向无环图转换为树（以娱乐，学习，kata命名）。所以我想出了数据结构Node：

/// <summary>
/// Represeting a node in DAG or Tree
/// </summary>
/// <typeparam name=\"T\">Value of the node</typeparam>
public class Node<T> 
{
    /// <summary>
    /// creats a node with no child nodes
    /// </summary>
    /// <param name=\"value\">Value of the node</param>
    public Node(T value)
    {
        Value = value;
        ChildNodes = new List<Node<T>>();
    }

    /// <summary>
    /// Creates a node with given value and copy the collection of child nodes
    /// </summary>
    /// <param name=\"value\">value of the node</param>
    /// <param name=\"childNodes\">collection of child nodes</param>
    public Node(T value, IEnumerable<Node<T>> childNodes)
    {
        if (childNodes == null)
        {
            throw new ArgumentNullException(\"childNodes\");
        }
        ChildNodes = new List<Node<T>>(childNodes);
        Value = value;
    }

    /// <summary>
    /// Determines if the node has any child node
    /// </summary>
    /// <returns>true if has any</returns>
    public bool HasChildNodes
    {
        get { return this.ChildNodes.Count != 0; }
    }


    /// <summary>
    /// Travearse the Graph recursively
    /// </summary>
    /// <param name=\"root\">root node</param>
    /// <param name=\"visitor\">visitor for each node</param>
    public void Traverse(Node<T> root, Action<Node<T>> visitor)
    {
        if (root == null)
        {
            throw new ArgumentNullException(\"root\");
        }
        if (visitor == null)
        {
            throw new ArgumentNullException(\"visitor\");
        }

        visitor(root); 
        foreach (var node in root.ChildNodes)
        {
            Traverse(node, visitor);
        }
    }

    /// <summary>
    /// Value of the node
    /// </summary>
    public T Value { get; private set; }

    /// <summary>
    /// List of all child nodes
    /// </summary>
    public List<Node<T>> ChildNodes { get; private set; }
}

非常简单。方法：

/// <summary>
/// Helper class for Node 
/// </summary>
/// <typeparam name=\"T\">Value of a node</typeparam>
public static class NodeHelper
{
    /// <summary>
    /// Converts Directed Acyclic Graph to Tree data structure using recursion.
    /// </summary>
    /// <param name=\"root\">root of DAG</param>
    /// <param name=\"seenNodes\">keep track of child elements to find multiple connections (f.e. A connects with B and C and B also connects with C)</param>
    /// <returns>root node of the tree</returns>
    public static Node<T> DAG2TreeRec<T>(this Node<T> root, HashSet<Node<T>> seenNodes)
    {
        if (root == null)
        {
            throw new ArgumentNullException(\"root\");
        }
        if (seenNodes == null)
        {
            throw new ArgumentNullException(\"seenNodes\");
        }

        var length = root.ChildNodes.Count;
        for (int i = 0; i < length; ++i)
        {
            var node = root.ChildNodes[i];
            if (seenNodes.Contains(node))
            {
                var nodeClone = new Node<T>(node.Value, node.ChildNodes);
                node = nodeClone;
            }
            else
            {
                seenNodes.Add(node);
            }
            DAG2TreeRec(node, seenNodes);
        }
        return root;
    }
    /// <summary>
    /// Converts Directed Acyclic Graph to Tree data structure using explicite stack.
    /// </summary>
    /// <param name=\"root\">root of DAG</param>
    /// <param name=\"seenNodes\">keep track of child elements to find multiple connections (f.e. A connects with B and C and B also connects with C)</param>
    /// <returns>root node of the tree</returns>
    public static Node<T> DAG2Tree<T>(this Node<T> root, HashSet<Node<T>> seenNodes)
    {
        if (root == null)
        {
            throw new ArgumentNullException(\"root\");
        }
        if (seenNodes == null)
        {
            throw new ArgumentNullException(\"seenNodes\");
        }

        var stack = new Stack<Node<T>>();
        stack.Push(root);

        while (stack.Count > 0) 
        {
            var tempNode = stack.Pop();
            var length = tempNode.ChildNodes.Count;
            for (int i = 0; i < length; ++i)
            {
                var node = tempNode.ChildNodes[i];
                if (seenNodes.Contains(node))
                {
                    var nodeClone = new Node<T>(node.Value, node.ChildNodes);
                    node = nodeClone;
                }
                else
                {
                    seenNodes.Add(node);
                }
               stack.Push(node);
            }
        } 
        return root;
    }
}

并测试：

    static void Main(string[] args)
    {
        // Jitter preheat
        Dag2TreeTest();
        Dag2TreeRecTest();

        Console.WriteLine(\"Running time \");
        Dag2TreeTest();
        Dag2TreeRecTest();

        Console.ReadKey();
    }

    public static void Dag2TreeTest()
    {
        HashSet<Node<int>> hashSet = new HashSet<Node<int>>();

        Node<int> root = BulidDummyDAG();

        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();
        var treeNode = root.DAG2Tree<int>(hashSet);
        stopwatch.Stop();

        Console.WriteLine(string.Format(\"Dag 2 Tree = {0}ms\",stopwatch.ElapsedMilliseconds));

    }

    private static Node<int> BulidDummyDAG()
    {
        Node<int> node2 = new Node<int>(2);
        Node<int> node4 = new Node<int>(4);
        Node<int> node3 = new Node<int>(3);
        Node<int> node5 = new Node<int>(5);
        Node<int> node6 = new Node<int>(6);
        Node<int> node7 = new Node<int>(7);
        Node<int> node8 = new Node<int>(8);
        Node<int> node9 = new Node<int>(9);
        Node<int> node10 = new Node<int>(10);
        Node<int> root  = new Node<int>(1);

        //making DAG                   
        root.ChildNodes.Add(node2);    
        root.ChildNodes.Add(node3);    
        node3.ChildNodes.Add(node2);   
        node3.ChildNodes.Add(node4);   
        root.ChildNodes.Add(node5);    
        node4.ChildNodes.Add(node6);   
        node4.ChildNodes.Add(node7);
        node5.ChildNodes.Add(node8);
        node2.ChildNodes.Add(node9);
        node9.ChildNodes.Add(node8);
        node9.ChildNodes.Add(node10);

        var length = 10000;
        Node<int> tempRoot = node10; 
        for (int i = 0; i < length; i++)
        {
            var nextChildNode = new Node<int>(11 + i);
            tempRoot.ChildNodes.Add(nextChildNode);
            tempRoot = nextChildNode;
        }

        return root;
    }

    public static void Dag2TreeRecTest()
    {
        HashSet<Node<int>> hashSet = new HashSet<Node<int>>();

        Node<int> root = BulidDummyDAG();

        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();
        var treeNode = root.DAG2TreeRec<int>(hashSet);
        stopwatch.Stop();

        Console.WriteLine(string.Format(\"Dag 2 Tree Rec = {0}ms\",stopwatch.ElapsedMilliseconds));
    }

此外，数据结构需要一些改进：覆盖GetHash，toString，等于，==运算符实现IComparable LinkedList可能是一个更好的选择另外，在转换之前，需要检查certig thig：多图如果是DAG（周期） DAG中的二价 DAG中的多个根总而言之，它缩小为几个问题：如何改善转换率？由于这是递归操作，因此有可能破坏堆栈。我可以添加堆栈来记住它。如果我采用延续传递风格，我会更有效率吗？我觉得在这种情况下不变的数据结构会更好。这是对的吗？孩子的名字正确吗？ :)

已邀请:

2 个回复

谦响局豢报

算法：如您所见，某些节点在输出中出现两次。如果节点2有子节点，则整个子树将出现两次。如果您希望每个节点仅出现一次，请替换

if (hashSet.Contains(node))
{
    var nodeClone = new Node<T>(node.Value, node.Childs);
    node = nodeClone;
}

与

if (hashSet.Contains(node))
{
    // node already seen -> do nothing
}

我不会太担心堆栈的大小或递归的性能。但是，您可以用“广度优先”搜索替换“深度优先”搜索，这将导致更接近根的节点被更早地访问，从而产生更多的“自然”树（在您的图片中，您已经为节点编号了） BFS订单）。

 var seenNodes = new HashSet<Node>();
 var q = new Queue<Node>();
 q.Enqueue(root);
 seenNodes.Add(root);   

 while (q.Count > 0) {
     var node = q.Dequeue();
     foreach (var child in node.Childs) {
         if (!seenNodes.Contains(child )) {
             seenNodes.Add(child);
             q.Enqueue(child);
     }
 }

该算法处理菱形和循环。多根只需声明一个包含所有顶点的Graph类

class Graph
{
    public List<Node> Nodes { get; private set; }
    public Graph()
    {
        Nodes = new List<Node>();
    }    
}

码： hashSet可以命名为seenNodes。代替

var length = root.Childs.Count;
for (int i = 0; i < length; ++i)
{
    var node = root.Childs[i];

写

foreach (var child in root.Childs)

在Traverse中，访客是不必要的。您可能宁愿有一个方法来产生树的所有节点（以相同的遍历顺序进行），并且由用户决定如何对节点做任何事情：

foreach(var node in root.TraverseRecursive())
{
    Console.WriteLine(node.Value);
}

如果覆盖GetHashCode和Equals，则该算法将不再能够区分具有相同值的两个不同Node，这可能不是您想要的。我没有看到LinkedList比List更好的任何原因，除了List在添加节点时进行的重新分配（容量2、4、8、16，...）。

可扇胆

你最好在CodeReview中发布小孩错了=>小孩您不必使用HashSet，可以轻松使用List>，因为在这里仅检查引用就足够了。（因此不需要GetHashCode，Equals和操作符覆盖）更简单的方法是序列化您的类，然后使用XmlSerializer将其再次反序列化为第二个对象。而序列化和反序列化时，引用2次的1个对象将成为引用不同的2个对象。

要回复问题请先登录或注册

将有向无环图（DAG）转换为树

2 个回复

发起人

c#

data_structures

tree

directed_acyclic_graphs

recursion

问题状态

将有向无环图（DAG）转换为树

与内容相关的链接

2 个回复

发起人

c#

data_structures

tree

directed_acyclic_graphs

recursion

问题状态