Wie konvertiert man ein Diagramm, das nicht DAG ist, in ein Diagramm, das DAG ist?

Guten Tag,Wie konvertiert man ein Diagramm, das nicht DAG ist, in ein Diagramm, das DAG ist?

Gibt es allgemeine Algorithmen, die einen nicht DAG (gerichteter azyklischer Graph) als Eingabe verwenden und einen gerichteten azyklischen Graphen ausgeben.

Momentan bin ich nicht sicher, welche Datenstrukturen ich für meine Grafik verwenden werde. Aber ich suche gerade nach dem Algorithmus an diesem Punkt.

Ich hoffe, Sie können mich über die Angelegenheit informieren.

Prost ~

ich von diesem gehen wollen:

Um dies:

NEW GRAPH GRAPH DIES IST NUR FÜR DIE LÖSUNG BeyelerStudios

bereitgestellt

Quelle

2016-06-28 TheQ

Sie könnten alle besuchten Kanten und Unterbrechungszyklen steuern ... aber was wollen Sie eigentlich hier erreichen? Sie ändern die Eigenschaft des Eingabediagramms. Was sind Ihre Absichten? – BeyelerStudios

Es gibt keinen einzigen gut definierten Weg, eine solche "Umwandlung" zu machen ist in einem bestimmten Kontext falsch, da es sich nicht um eine echte Konvertierung handelt. Sie machen ein völlig neues Diagramm, das einige Eigenschaften teilt das Original, aber nicht alle. Also, was willst du eigentlich das Ergebnis sein? – harold

@BeyelerStudios Nun, für die Bedürfnisse meiner Forschung in Bayes'schen Netzwerken haben wir eine Menge Daten aus dem Genregulationsnetzwerk, und wir organisieren diese Daten in einer Art ungerichteten zyklischen Graphen. Meine Aufgabe besteht darin, diesen Graphen zu einem gerichteten zyklischen Graphen zu machen, ungeachtet dessen, ob einige Knoten verloren gehen könnten, wenn man versucht, den Graphen zyklisch zu machen. Und dann die Kanten, die nicht umgekehrt werden können, möchte ich sperren, so dass wir in zukünftigen Fällen diesen zyklischen Graph hinzufügen können, ohne die DAG-Einschränkung zu brechen. – TheQ

Sie können immer einfach einige Kanten Flip ein azyklischer Graph von einem zyklischen ein (Graph G mit den Eckpunkten V und Kanten E) zu erhalten:

input: G(V,E), n = |V| 

visited <- empty set 
queue <- empty queue 
for each node in V 
    // skip visited nodes 
    if visited.find(node) 
     continue 
    // push a dummy edge (node is unvisited) 
    queue.push(edge(inf, node)) 
    while !queue.empty() 
     edge <- queue.pop() 
     if visited.find(edge.stop) 
      // potential cycle detected 
      if edge.start != edge.stop 
       // eliminate loops, if any 
       E.flip(edge) 
     else 
      visited.insert(edge.stop) 
      for each outgoing edge e at edge.stop 
       queue.push(e)

Abhängig von der Warteschlange, die Sie Sie ein anderes Verhalten bekommen verwenden:

ein Stapel (LIFO-Warteschlange) zu depth-first-Traversal
ein FIFO-Warteschlange Ergebnisse in Breiten erste Traversierung
ein Prioritäts-Warteschlange führt zu einem DAG seine Spanning tree (s) enthaltenden

Es gibt ein caviat im obigen Code: potenzieller Zyklus erkannt. Stellen Sie sich einen Graphen mit den Vertices A, B, C und den Kanten A->B, A->C, C->B vor. Das obige Snippet erkennt einen möglichen Zyklus bei der letzten Verarbeitung von C->B. Wenn Sie gültige Kanten von Kanten unterscheiden wollen, die an dieser Stelle Zyklen einführen, müssen Sie anzeigen, dass es noch keine Pfade von B bis C gibt. Dies ist eine viel schwierigere Aufgabe und es gibt einige gute Antworten (und Hinweise) in this answer here: im Grunde müssten Sie eine andere Graph Traversal durchführen, um einen solchen widersprüchlichen Pfad zu erkennen (oder auszuschließen).

Quelle

2016-06-29 10:14:49 BeyelerStudios

Wie konvertiert man ein Diagramm, das nicht DAG ist, in ein Diagramm, das DAG ist?

Antwort

Verwandte Themen