無向グラフのすべてのサイクルベースを識別するアルゴリズム

StackOverflow https://stackoverflow.com/questions/1607124

  •  05-07-2019
  •  | 
  •  

質問

頂点 V およびEdge E の無向グラフがあります。そのグラフのすべてのサイクルベースを識別するアルゴリズムを探しています。

タージャンアルゴリズムは良いスタートだと思います。しかし、参照は、 サイクル のすべてを見つけることです、 サイクルベース ではありません（定義上、他のサイクルの結合では構築できないサイクルです）。

たとえば、下のグラフを見てください：

したがって、アルゴリズムが役立ちます。既存の実装（C＃が望ましい）がある場合は、さらに優れています！

役に立ちましたか？

解決

私が知ることができることから、ブライアンの予感が得られるだけでなく、さらに強力な命題が成り立ちます：最小スパニングツリーにない各エッジは、ちょうど1つの新しい「ベースサイクル」を追加します。

これを見るために、MSTにないエッジEを追加するとどうなるか見てみましょう。物事を複雑にして表記を追加するためのお気に入りの数学的な方法をやってみましょう;）元のグラフG、E G 'を追加する前のグラフ、およびE G' 'を追加した後のグラフを呼び出します。そのため、「基本サイクルカウント」がどのようにカウントされるかを調べる必要があります。 G 'からG' 'に変更します。

Eを追加すると、少なくとも1サイクル閉じる必要があります（それ以外の場合、Eは最初にGのMSTにあります）。したがって、少なくとも1つの「基本サイクル」を追加する必要があることは明らかです。 G 'に既に存在するものに。しかし、それは複数を追加しますか？

2つを超えるベースサイクルのメンバーになるエッジはないため、3つ以上追加することはできません。しかし、Eが2つの基本サイクルのメンバーである場合、「結合」はこれら2つの基本サイクルのうち、G 'の基本サイクルである必要があります。そのため、サイクル数の変更はまだ1つであることがわかります。

エルゴ、MSTにない各エッジに対して、新しいベースサイクルを取得します。したがって、「カウント」は一部は簡単です。各基本サイクルのすべてのエッジを見つけるのは少し難しいですが、上記の理由に従うと、これはそれを行うことができると思います（擬似Pythonで）：

for v in vertices[G]:
    cycles[v] = []

for e in (edges[G] \ mst[G]):
    cycle_to_split = intersect(cycles[e.node1], cycles[e.node2])
    if cycle_to_split == None:
        # we're adding a completely new cycle
        path = find_path(e.node1, e.node2, mst[G])
        for vertex on path:
            cycles[vertex].append(path + [e]) 
        cycles
    else:
        # we're splitting an existing base cycle
        cycle1, cycle2 = split(cycle_to_split, e)
        for vertex on cycle_to_split:
            cycles[vertex].remove(cycle_to_split)
            if vertex on cycle1:
                cycles[vertex].append(cycle1)
            if vertex on cycle2:
                cycles[vertex].append(cycle2)

base_cycles = set(cycles)

編集：コードは、グラフ内のすべての基本サイクル（下部に設定されたbase_cycles）を見つける必要があります。前提は、次の方法を知っていることです。

  • グラフの最小全域木を見つける（mst [G]）
  • 2つのリストの違いを見つける（edges \ mst [G]）
  • 2つのリストの共通部分を見つける
  • MST上の2つの頂点間のパスを見つける
  • 追加のエッジを追加してサイクルを2つに分割します（分割関数）

そして、主に上記の議論に従います。 MSTにない各エッジには、2つのケースがあります。完全に新しい基本サイクルをもたらすか、既存のサイクルを2つに分割します。 2つのうちどちらが該当するかを追跡するために、頂点が含まれるすべての基本サイクルを追跡します（サイクル辞書を使用）。

他のヒント

頭上から、最小スパニングツリーアルゴリズム（Prim、Kruskalなど）を調べることから始めます。 MSTにないエッジよりも多くのベースサイクルはありえません（正しく理解できれば）。

これらはすべての「基本サイクル」を見つけるための実際の未テストのC＃コードです。

public HashSet<List<EdgeT>> FindBaseCycles(ICollection<VertexT> connectedComponent)
{
   Dictionary<VertexT, HashSet<List<EdgeT>>> cycles =
       new Dictionary<VertexT, HashSet<List<EdgeT>>>();

   // For each vertex, initialize the dictionary with empty sets of lists of
   // edges
   foreach (VertexT vertex in connectedComponent)
       cycles.Add(vertex, new HashSet<List<EdgeT>>());

   HashSet<EdgeT> spanningTree = FindSpanningTree(connectedComponent);

   foreach (EdgeT edgeNotInMST in
           GetIncidentEdges(connectedComponent).Except(spanningTree)) {
       // Find one cycle to split, the HashSet resulted from the intersection
       // operation will contain just one cycle
       HashSet<List<EdgeT>> cycleToSplitSet =
           cycles[(VertexT)edgeNotInMST.StartPoint]
               .Intersect(cycles[(VertexT)edgeNotInMST.EndPoint]);

       if (cycleToSplitSet.Count == 0) {
           // Find the path between the current edge not in ST enpoints using
           // the spanning tree itself
           List<EdgeT> path =
               FindPath(
                   (VertexT)edgeNotInMST.StartPoint,
                   (VertexT)edgeNotInMST.EndPoint,
                   spanningTree);

           // The found path plus the current edge becomes a cycle
           path.Add(edgeNotInMST);

           foreach (VertexT vertexInCycle in VerticesInPathSet(path))
               cycles[vertexInCycle].Add(path);
       } else {
            // Get the cycle to split from the set produced before
            List<EdgeT> cycleToSplit = cycleToSplitSet.GetEnumerator().Current;
            List<EdgeT> cycle1 = new List<EdgeT>();
            List<EdgeT> cycle2 = new List<EdgeT>();
            SplitCycle(cycleToSplit, edgeNotInMST, cycle1, cycle2);

            // Remove the cycle that has been splitted from the vertices in the
            // same cicle and add the results from the split operation to them 
            foreach (VertexT vertex in VerticesInPathSet(cycleToSplit)) {
                cycles[vertex].Remove(cycleToSplit);
                if (VerticesInPathSet(cycle1).Contains(vertex))
                     cycles[vertex].Add(cycle1);
                     if (VerticesInPathSet(cycle2).Contains(vertex))
                         cycles[vertex].Add(cycle2); ;
            }
       }
   }
   HashSet<List<EdgeT>> ret = new HashSet<List<EdgeT>>();
   // Create the set of cycles, in each vertex should be remained only one
   // incident cycle
       foreach (HashSet<List<EdgeT>> remainingCycle in cycles.Values)
           ret.AddAll(remainingCycle);

       return ret;
}

Oggy's コードは非常に良好で明確でしたが、エラーが含まれていると確信しています、またはあなたの擬似Pythonコードを理解していないのは私です：）

cycles[v] = []

エッジのリストの頂点インデックス付き辞書にすることはできません。私の意見では、それはエッジのリストのセットの頂点インデックス付き辞書でなければなりません。

そして、精度を追加するには：

for vertex on cycle_to_split:

cycle-to-splitはおそらくエッジの順序付けのリストなので、頂点を反復処理するには、頂点のセットで変換する必要があります。ここでの注文はごくわずかであるため、非常に単純なアルゴリズムです。

繰り返しますが、これは未テストおよび未完了のコードですが、一歩前進しています。適切なグラフ構造（私は偶発的なリストを使用）とCormenのような教科書で見つけることができる多くのグラフアルゴリズムが必要です。私は教科書でFindPath（）とSplitCycle（）を見つけることができませんでした。グラフのエッジ数と頂点数の線形時間でそれらをコーディングするのは非常に困難です。それらをテストするときにここで報告します。

Oggyに感謝します！

サイクルを検出する標準的な方法は、2つの反復子を使用することです。反復ごとに、1つは1ステップ進み、他は2つ進みます。サイクルがある場合、それらはある時点でお互いにポイントします。

このアプローチを拡張して、見つかったサイクルを記録し、先に進むことができます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top