von der Quelle zum Ziel über alle Kanten

Question

Ich habe einen gerichteten Graphen. Ich möchte alle möglichen Wege von der Quelle zum Ziel finden, die alle Übergänge abdecken. Dies unterscheidet sich von "alle möglichen Pfade, die alle Knoten abdecken". Der Graph wird genau einen Startknoten haben und mehrere Endknoten haben. Ein Knoten ist ein Endknoten, wenn er keinen ausgehenden Übergang hat. Ein Pfad in der Gruppe kann doppelte Übergänge enthalten, aber keine doppelten Scheitelpunkte. Ein Beispiel für einen gerichteten Graph ist beigefügt. Vertex a (schwarz) ist der Anfangspunkt und Scheitelpunkt e und f sind die Endknoten (gelb). Die Lösung für dieses Diagramm ist wie folgt.

a-f 
a-b-f 
a-b-c-e 
a-b-c-d-e 
a-b-c-d-b-f 

können Sie sehen, dass der letzte Weg b zweimal hat. Dies ist gültig. ein Pfad kann den gleichen Eckpunkt mehr als einmal haben. Die entsprechenden Übergänge sind

t18 
t1-t7 
t1-t2-t3 
t1-t2-t4-t5 
t1-t2-t4-t6-t7 

Sie können sehen, dass kein Pfad doppelte Übergänge hat. Ich brauche ein Java-Programm, um das zu tun. Ich habe ein Programm geschrieben, um das zu lösen. Aber es gibt mir alle Wege ohne doppelte Scheitelpunkte. Daher fehlen mir einige Kanten, obwohl sie alle Knoten abdeckt. Der Code, den ich schrieb unter

private Stack<Vertex> path = new Stack<Vertex>(); // the current path 
private Set<Vertex> onPath = new HashSet<Vertex>(); // the set of vertices 
public void AllPaths(Vertex s) { 
    enumerate2(s); 
} 

private void enumerate(Vertex v) { 
    // add node v to current path from source 
    path.push(v); 
    onPath.add(v); 
    if (v.getOutgoings().size() == 0) { 
     printPath(path); 
     addToRawPaths(path); 
    } 

    // consider all neighbors that would continue path with repeating a node 
    else { 
     EList<Transition> ts = v.getOutgoings(); 
     for (Transition w : ts) { 
      if (!onPath.contains(w.getTarget())) { // !onPath.contains(w.getTarget()) 
       enumerate(w.getTarget()); 
      } 
     } 
    } 

    // done exploring from v, so remove from path 
    path.pop(); 
    onPath.remove(v); 
} 

Mit dieser gegeben ist, erhalte ich

a-f 
a-b-f 
a-b-c-e 
a-b-c-d-e 

Aber ich brauche etwas, wie ich oben beschrieben. Sie können davon ausgehen, dass diese API in diesem Code verwendet wird, oder Sie können neue implementieren. Sogar psudocode ist in Ordnung. Ich brauche die Lösung, um in einem modellbasierten Testwerkzeug Testfälle zu generieren. Vielen Dank.

Answer 1

Derzeit Sie Aufzählen stoppen, wenn Sie einen Vertex finden, die bereits in onPath enthalten ist. Dies sollte in Ihrem Fall nicht die Regel sein. Im Gegensatz dazu sollten Sie Aufzählen stoppen, wenn das Paar currentVertex v, nextCandidateVertex w.getTarget() Sie auf Ihrem aktuellen Pfad nach dem anderen existieren.

Um dies zu erreichen, würde ich eine HashSet<VertexPair> der aufeinander folgenden Vertices anstelle einer HashSet<Vertex> verwenden. Ich denke, Ihre Transition Objekte zu einem VertexPair entsprechen; Wenn dies zutrifft, können Sie direkt HashSet<Transition> verwenden.

Eigentlich können Sie die gleiche Funktionalität mit Ihrem path Stack erreichen, aber die Suche nach einem bestehenden Paar kann erfordern O (n) VS amortisierten O (1) mit dem vorgeschlagenen Ansatz HashSet<VertexPair>.