すべてのエッジをカバーするソースからデスティネーションまでのすべての可能なパスのセットを見つける

Question

私は有向グラフを持っています。私はすべての遷移をカバーするソースからデスティネーションまでのすべての可能なパスを探したい。これは、「すべての頂点をカバーするすべての可能なパス」とは異なります。グラフはちょうど1つの開始頂点を持ち、いくつかの終了頂点を持つことができます。ノードは、出力遷移がない場合、エンドノードです。セット内のパスは重複したトランジションを持つことがありますが、重複した頂点を持つことはできません。有向グラフの例が添付されています。頂点（黒） F開始頂点と頂点Eとは、エンドノード（黄色）がされています。 このグラフの解は以下の通りです。

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

あなたは、最後のパスがB 2回を持っていることがわかります。これは有効です。すなわち、パスは同じ頂点を2回以上有することができる。対応するトランジションは

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

です。重複するトランジションがないパスがあることがわかります。私はそれを行うためにJavaプログラムが必要です。 私はこれを解決するプログラムを書いた。しかし、それは私に重複する頂点なしですべてのパスを与えます。したがって、すべてのノードを対象としていますが、いくつかのエッジが欠落しています。私が書いたコードがこれを使用して

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

の下に与えられて、私は

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

を取得しています。しかし、私は、上記のようなものを必要とします。このコードで使用したこれらのAPIを前提とすることも、新しいAPIを実装することもできます。 psudocodeでも大丈夫です。私は、テストケースを生成するためのモデルベースのテストツールに適用するソリューションが必要です。どうもありがとうございました。

Answer 1

現在、あなたはすでにonPathに含まれていますVertexを見つけたときに列挙停止します。これはあなたの場合のルールではありません。対照的に、currentVertexのペアv、nextCandidateVertex w.getTarget(）が現在のパスに順番に存在するときは、列挙を停止する必要があります。

これを達成するには、HashSet<Vertex>ではなく、連続する頂点のHashSet<VertexPair>を使用します。あなたのTransitionオブジェクトはVertexPairに対応しています。これが当てはまる場合は、HashSet<Transition>を直接使用することができます。

実際には、pathスタックを使用して同じ機能を実現できますが、既存のペアを探すには、提案手法をHashSet<VertexPair>としてO（n）VS償却O（1）が必要な場合があります。