エッジの集合がループを形成するかどうかを調べる

Question

エッジの集合が閉ループを形成するかどうかを調べる最良のコードを探しています。

入力データはエッジの配列であり、各エッジ（=線分）は2つの端点で定義されます。たとえば、[[1,2],[2,3],[3,4],[4,1]]は、最初の接続点1（2など）の4つのエッジを表します。1,2、...は、各点に固有のラベルです（1は、(1,1,2)を表します）。

上記の例は閉ループです。異なる例があります：[[44,52],[69,71],[8,101],[52,77],[71,77],[69,8]は、点44から開始してから、44->52->77->71->69->8->101が44で終了しないと接続するため、閉ループを表しません。また、各辺は任意の順序で2つの点を持つことができ、辺の順番もランダムです（もちろんソートすることもできます）。

私は、ループが閉じているかどうかを判断するための最良のコードを探しています。 「ベスト」は効率も最大にする必要があります。アプリケーションはメッシュ生成であり、それぞれが100個の頂点からなる多数の異なるエッジセットのループ/非ループを決定する必要があります。

ありがとうございました！

編集

私の試み：それは閉ループだ場合は、各ポイントのようなものが二回表示されます。だから一般的には、リストを平坦化し、頂点が一度しか現れないかどうかをチェックします。しかし、私は（最大エッジ大きさを調整し、このついて行くには最良の方法は、大きなサイズの配列を作成することであるかもしれません

flat = [x for sublist in pts for x in sublist] 
single = [x for x in flat if flat.count(x) == 1] 
if len(single) > 0: 
    # Not a closed loop.... 

Answer 1

これは（支店？など）を表示され、他の構造を妨げないわかりません）ここで、すべての値は最初に-1です。フォーム[a,b]の端を取得したら、array[a] = bと設定します。

ループがあるかどうかを調べるときは、値が-1でないインデックスから開始し、その値に従います。

したがって、array[a]= bから、array[b] = cに移動します。今後の値のいずれかが-1の場合は開ループですが、開始位置に戻ると閉ループになります。

Answer 2

以下のプロセスは、サイクルがあるかどうかをテストします。

キーを頂点とし、その値を隣接する頂点のリストとして持つ辞書を考えてみましょう。 [1：2,4]、2：[1,3]、3：[2、3] 4]、4：[1,3]}。

キーのリストから各頂点を処理します。 隣接する頂点が1つしかない最初の頂点を見つけます。 辞書から削除して、隣接する頂点を見ます。 隣接頂点は持っている場合：

• 1隣接あなたはエンドポイントを発見した頂点ひとつはを除去した後に残るように、
• 2隣接頂点を、それを削除し、残りの頂点リストに戻ります 葉、隣接する頂点に残り、 辞書から削除します。
• 3つ以上の隣接する頂点は、その頂点の接続リスト から頂点を削除し、残りの頂点リストに戻ります。 残りの頂点リストを返すと、隣接する頂点が1つしかない最初の頂点を見つけます。辞書が空の場合、元のグラフにはサイクルがありません。 1つの隣接頂点を持つ頂点が見つからない場合、つまり、すべての頂点が2つ以上の隣接点を持つ場合、元のグラフはサイクルを持ちます。

削除されたときにリストにエッジを収集すると、ループまたはサイクルの一部ではないエッジのリストを生成することもできます。サブグラフが空のリストで終了する場合、削除されたエッジリストもループまたはサイクルに接続されません。

このプロセスは、エッジセットを3つのサブセットの1つに分割します。ループから切り離されたぶら下がっている文字列と枝の一部のエッジ、ループ/サイクルに接続されているがループの一部ではないもの、残りのセット。

この残りの辞書には、1つ以上のサイクルの一部であるか、2つのループを接続するパスの一部であるエッジが含まれています。 2つのループは、頂点の経路によってダンベルの形で接続されていると考えてください。最後のウェイトはループで、バーはループ間の頂点のストリングです。各頂点には2つ以上の隣接頂点がありますが、グラフにはループの一部ではない辺が含まれています。

サイクル間の接続の終点にある頂点は、奇数個の隣接する頂点を持つ頂点の中で起こる可能性が高くなりますが、これは固有のプロパティまたは必要なプロパティではありません。 1つのコンテキスト内のループを接続するパスは、別のコンテキスト内のループの一部であってもよい。サイクル間またはサイクル内の接続経路におけるメンバーシップは、エッジの相対的かつ排他的な特性である。このグラフを考える：

1->2->3->4->5->6->7->8->6 
     4->1  7->9->10->2 

ループ2-> 3-> 4-> 5-> 6> 7> 8> 9> - > 2> 10-は頂点4-経路を含むであろうループ1-> 2-> 3-> 4-> 1と6-> 7-> 8-> 6との間で> 5-> 6となる。また、頂点2,4,6および7は3つの隣接する頂点を有する。

サイクル間のパスにありますが、どのサイクルでもないエッジのリストを生成するには、より困難な問題があります。すべてのサイクルのリストを生成し、各エッジが属するサイクル数を数え、ゼロサイクルにあるエッジを削除することができます。あるいは、カウントする代わりにセットを使用する方が効率的かもしれません。各サイクルでエッジのセットを作成し、すべてのエッジのセットからそれらのセットのそれぞれを減算すると、サイクル/ループ間の接続にあるエッジが残されます。

どちらの場合も、すべてのサイクルを見つける必要があります。サイクルのセットを見つけるには、グラフを歩くことが必要です。すべてのサイクルを見つけ出す過程で、頂点への訪問回数とエッジのトラバース回数で回答を見つけることができます。

その他の考え： 効率を考えると、実際にあなたが上流に取り組んでいるものによって決まります。 スーパーセットのプロパティ、サブセット、およびサブセットの選択方法は明確ではなく、最も効率的なソリューションを見つける上で重要です。各ステップで最も効率的ではありませんが、RAM /処理時間のトレードオフが常にあります。

サブセットのように見える接続サブセットを見つける作業を行うには、エッジを追跡する必要があります。そのため、頂点のスーパーセットでアルゴリズムを使用してから、エッジの各サブセットを接続されたエッジの2つのサブセットを生成します。 1つはループを含み、もう1つは文字列と木を含む。

総プロセスの各ステップで、デバッグやコードの探索的な分析ブランチにカウントとコレクションを配置すると、良い解決策を見つけるのに役立ちます。このためのアプローチの1つは、関数visit（頂点）、トラバース（エッジ）、クラスメソッドvertex.visit（）、edge.traverse（）を使用し、キーワード引数、デコレータ、または特殊化によってコレクション、クラスのまた、マルチプロセスのmap-reduceソリューションもあります。 グラフの表現。 2つの頂点の間にエッジが1つしかなければ、メッシュはマルチグラフではなくグラフにマッピングされ、異なる表現をマッピングする複雑さが増します。 グラフは、頂点のセットとその間のエッジのセットです。グラフを表すことができる3つの主な方法は、次のとおり

1. 頂点のセット、および頂点の 対として各エッジを表すエッジの集合。 （グラフが接続されたグラフの場合、頂点の集合 は、エッジのリストに暗黙的に含まれる可能性があります）。
2. 各頂点に隣接する頂点のリストと頂点のリスト。
3. nxn行列.nは頂点の数です。行列は通常、頂点が辺で接続されている場合は0×偽の場合は 1、真の場合は です。

各表現によって、異なるプロパティに素早くアクセスできるようになります。

頂点とエッジのセットは、双方向グラフで最も効率的です。順序は関係ありませんし、両方がセット{1,2}であるため[1,2] = [2,1]にすることができるので、エッジを2つの要素セットとして表すことができます。

双方向グラフのマトリックスまたは隣接リストの表現が冗長になります。各辺は、両方の頂点の隣接リストに、または行列の対角線に沿った反射として表されます。頂点aが頂点bに隣接する場合、頂点bは頂点aにも隣接し、行列Gに対してはG [a、b] = G [b、a]である。メッシュG [a、a] = 0（リフレクティブグラフのエッジなし）からマップされたグラフの場合

トラバーサルカウントの場合、辞書キーにいくつかの制限があります。ハッシュ可能な値は辞書キーとして使用できます。ほとんどの場合、キーを不変に保つことが最善です。つまり、リスト、セット、辞書は有効な辞書キーではありません。代わりに、プリミティブ型の対応するタプルを使用できます。不変セットタイプも使用できます。

あなたの問題は、networkxのようなライブラリを含むことを保証するのに十分な複雑さがあるかもしれません。

テストがより速くなる場合があります。サイクルを見つけるアルゴリズムを提案すれば、メッシュからマップされたグラフの制約を使用した方がよいかもしれません。 グラフ内のすべてのサイクルの検索は自明ではなく、さらなる研究が必要です。 グラフ理論のループは、しばしば反射的なエッジを指します。これは、頂点からそれ自身へのエッジです。グラフ理論の多くの定理は、これらのタイプのエッジのないグラフのサブセットを探索します。その理由から、ループではなくサイクルを検索することがより役に立ちます。

すべてのサイクルを見つけるには多くの方法があります。また、数学の質問サイトを試してみることもできます。私は、この説明が、例えば、私が慣れ親しんだ用語のいくつかを区別していることを発見しました。 What is the difference between a loop, cycle and strongly connected components in Graph Theory?

Answer 3

はここNetworkXを使用したアプローチです：

import networkx as nx 

edges = [[1,2], [2,3], [3,4], [4,1]] 
g = nx.Graph() 
g.add_edges_from(edges) 

try: 
    cycle = nx.find_cycle(g) 
    cycle = set(map(frozenset, cycle)) 
    edges = set(map(frozenset, edges)) 
    if cycle == edges: 
     print("The edges form a loop") 
    else: print("The edges don't form a loop") 
except nx.exception.NetworkXNoCycle: 
    print("No cycle found") 

私たちは、無向グラフを作成し、サイクルを探します。見つけた場合は、ループを構成するエッジと入力エッジを比較します。一致した場合、入力辺はループを形成します。

これらの行：

cycle = set(map(frozenset, cycle)) 
edges = set(map(frozenset, edges)) 

は、独立して自分のための、あなたがエッジを比較することができます。

nx.find_cycleは見つかった最初のサイクルのみを返すため、このソリューションは完璧ではありません。したがって、偽陰性が発生する可能性があります。少なくとも、例外がスローされた場合、エッジがループを形成しないことを確実に知ることができます。

入力エッジに一致するものが見つかるまで、すべてのサイクルをループすることができますが、大きなエッジセットの効率がどれくらいか分かりません。 NetworkXを使用してグラフ内のすべてのサイクルを見つける方法については、this gistを参照してください。たぶん、find_all_cyclesをジェネレータ関数に変換するのでしょうか？