Konvertieren von Gerichteten Azyklischen Graphen (DAG) - zu-Baum -

Ich versuche, umzusetzen algoritm zu konvertieren Gerichteten Azyklischen Graph-Struktur (zum Spaß, learining, kata, name it). Also ich komm mit der Daten-Struktur-Knoten:

Konvertieren von Gerichteten Azyklischen Graphen (DAG) - zu-Baum -

///<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; }
}

Es ist ziemlich einfach. Methoden:

///<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;
    }
}

und test:

    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));
    }

Was ist mehr, der Struktur der Daten müssen einige improvment:

  • Überschreiben GetHash, toString, Equals, = = - operator
  • Implementierung von IComparable
  • LinkedList ist wahrscheinlich die bessere Wahl

Auch, vor dem Umbau gibt es bestimmter thigs, die untersucht werden müssen:

  • Multigraphs
  • Wenn es DAG (Zyklen)
  • Diamnods in DAG
  • Mehrere Wurzeln in DAG

Alles in allem, es verengt sich auf ein paar Fragen:
Wie kann ich die Konvertierung? Da dies eine recurion ist es möglich, die Luft zu sprengen den stack. Ich kann hinzufügen-stack, um es auswendig zu lernen. Wenn ich continuation-passing-style, werde ich effizienter?

Ich das Gefühl, dass immutable Datenstruktur in diesem Fall besser wäre. Ist es richtig?

Childs ist der richtige name ? 🙂

  • In Antwort auf Ihre Frage, " Childs Ist der richtige name?', Children wäre ein besserer name, oder sogar ChildNodes.
  • "Kinder" ist besser 🙂
  • 100% sicher ist, dass Kinder, die Knoten sind im Baum. Diagrammen (alle Arten) haben childern Knoten?
  • in der Graphentheorie, die Sie normalerweise sprechen Sie über die vertices (Knoten) und Kanten. Wo ein Eckpunkt repräsentieren, was Sie nennen einen Knoten und eine Kante repräsentiert die "Verbindung" zwischen zwei Eckpunkten. Children ist besser, weil Childs existiert nicht in der englischen Sprache.
  • Die korrekte Bezeichnung für eine Reihe von direkt an Scheitelpunkten wäre Neighbors.
  • Können Sie bitte schreiben Sie den pseudo-code des Algorithmus, den Sie verwendet?

InformationsquelleAutor Lukasz Madon | 2011-06-18
Schreibe einen Kommentar