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:
///<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 sogarChildNodes
. - "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, weilChilds
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?
Du musst angemeldet sein, um einen Kommentar abzugeben.
Algorithmus:
Als Sie beobachtet, einige Knoten zweimal in die Ausgabe. Wenn der Knoten 2 Kinder hatte, der gesamte Teilbaum würde doppelt angezeigt. Wenn Sie möchten, dass jeder Knoten erscheinen nur einmal, ersetzen
mit
Wäre ich nicht allzu besorgt über die Größe des Stapels oder der Leistung von Rekursion. Sie können jedoch ersetzen Sie Ihre Tiefe-zuerst-Suche mit Breite-zuerst-Suche dazu führen würde, dass die Knoten näher an die Wurzel besucht wird früher und damit zu einer "natürlichen" Struktur (in Ihrem Bild, das Sie bereits nummeriert die Knoten in BFS-Ordnung).
Den Algorithmus verarbeitet Diamanten und Zyklen.
Mehrere Wurzeln
Nur deklarieren Sie eine Klasse Graph, die enthalten alle Eckpunkte
Code:
den hashSet bezeichnet werden können seenNodes.
Statt
schreiben
In der Traverse, der Besucher ist völlig unnötig. Sie könnte sich eher eine Methode, die liefert alle Knoten des Baumes (in der gleichen Reihenfolge Durchlaufen hat) und es ist bis zum Benutzer, zu tun, was mit den Knoten:
Wenn Sie GetHashCode überschreiben, und Gleich ist, wird der Algorithmus nicht mehr in der Lage sein, zu unterscheiden zwischen zwei verschiedenen Knoten mit dem gleichen Wert, das ist wahrscheinlich nicht das, was Sie wollen.
Ich sehe keinen Grund, warum LinkedList wäre hier besser als Liste, mit Ausnahme der Umschichtungen (Kapazität 2,4,8,16,...), die Liste wird beim hinzufügen von Knoten.
du nicht in ein HashSet, Sie könnte leicht verwendet werden, eine Liste>, da das überprüfen der Referenzen nur ist hier genug. (und so keine GetHashCode, Equals und Operatoren überschreiben ist erforderlich)
easeier Weg ist Serialisieren der Klasse und dann Deserialisiert Sie wieder in die zweite objectwith XmlSerializer.
während Serialisiert und Deserialisiert, 1 Objekt verwiesen wird 2-mal werden 2 Objekte mit verschiedenen Referenzen.