Przekształcanie Directed Acyclic Graph (DAG) na drzewo

Question

Próbuję zastosować algorytm do konwersji Direct Acyclic Graph na drzewo (dla zabawy, nauki, kata, nazwij go). Więc pochodzić z węzła struktury danych:

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

To całkiem proste. Metody:

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

i testy:

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

Co więcej, struktura danych potrzebują improvment:

• Zastępowanie GetHash, toString równy, == operatora
• wykonawczych IComparable
• LinkedList to prawdopodobnie lepszy wybór

Również przed konwersją istnieją certian thigs, które muszą być sprawdzone:

• Multigraphs
• Jeśli to DAG (cykle)
• Diamnods w DAG
• Wiele korzenie w DAG

W sumie zawęża się do kilku pytań: Jak mogę poprawić konwersję? Ponieważ jest to recurion, możliwe jest wysadzenie stosu. Mogę dodać stos, żeby go zapamiętać. Czy jeśli będę robić styl kontynuacji, czy będę bardziej wydajny?

Uważam, że niezmienna struktura danych w tym przypadku byłaby lepsza. Czy to jest poprawne?

Czy Childs to właściwa nazwa? :)

Answer 1

Algorytm:

• Jak można zaobserwować, niektóre węzły pojawiają się dwukrotnie na wyjściu. Jeśli węzeł 2 miał dzieci, cały poddrzewo pojawiłoby się dwa razy.Jeśli chcesz, aby każdy węzeł pojawiać się tylko raz, wymień

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

  z

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

• I nie byłoby zbyt zaniepokojeni rozmiarem stosu lub wykonywania rekursji. Możesz jednak zamienić pierwsze wyszukiwanie na głębokie na Breadth-first-search, co spowoduje, że węzły staną się bliższe pierwszemu odwiedzanemu rootowi, dzięki czemu powstanie bardziej "naturalne" drzewo (na obrazku już numerowane są węzły w kolejności 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); 
      } 
  } 
  

  Algorytm obsługuje diamenty i cykle.

• Wiele korzenie

  Wystarczy zadeklarować wykres klasa, która będzie zawierać wszystkie wierzchołki

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

---

Kod:

• Hashset można nazwać seenNodes.

• Zamiast

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

  zapisu

  foreach (var child in root.Childs) 
  

• w Traverse, użytkownik jest zupełnie niepotrzebne. Można raczej metody, które dają wszystkie węzły drzewa (w biegu porządkowego robi) i to od użytkownika, aby zrobić cokolwiek z węzłami:

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

• Jeśli przesłonić GetHashCode i równa, algorytm nie będzie już w stanie odróżnić dwóch różnych węzłów o tej samej wartości, co prawdopodobnie nie jest tym, czego potrzebujesz.

• Nie widzę żadnego powodu, dla którego obiekt LinkedList byłby lepszy niż Lista, z wyjątkiem realokacji (Pojemność 2,4,8,16, ...), którą Listuje podczas dodawania węzłów.

Answer 2

1. to lepiej pisał w CodeReview
2. Childs jest źle => Dzieci

3. nie trzeba używać HashSet, można mieć łatwo wykorzystane listy>, ponieważ tylko sprawdzanie referencji wystarczy tutaj. (i dlatego nie jest wymagany kod GetHashCode, wartość równań i operatorów))

4. sposób ułatwienia polega na serializacji klasy, a następnie ponownemu wprowadzeniu jej do drugiego obiektu za pomocą XmlSerializer. podczas Serialized and Deserialized, 1 obiekt o którym mowa 2 razy stanie się 2 obiektami z różnymi referencjami.