DijkstraとA Starアルゴリズム（有向ネットワークXグラフ）を使って2点間の最短経路を計算しようとしています。NetworkXグラフの特定のパスを制限する方法は？
現時点では正常に動作し、私は計算されたパスを見ることができますが、私は制限特定パスの方法を見つけるしたいと思います。例えば
我々は以下ている場合、ノード：これらのエッジに
ノード= [1,2,3,4]
：
エッジ=（（1,2）、（2 > - 2 - > 3 & 1 - - > 2> 3それでも2を許可する、3）、（3,4））
は1制限/遮断の方法があります。
これはそれを意味します：
1から2
に旅行は2から3
にの旅行は1〜3の旅行することはできませんすることができます直接的または間接的に（すなわち、1-> 2-> 3経路を制限する）。
これはNetworkXで達成できますか？これを可能にする別のグラフライブラリがPythonにはありますか？
ありがとうございました。
興味深い質問がありましたが、おそらく私はこのトピックで多くの背景やNetworkXの経験はあまりないので、この問題について聞いたことはありません。しかし、私はアルゴリズムのアイデアを持っています。これはこれを行うための最も素朴な方法かもしれませんし、私はより精巧なアルゴリズムについて聞いてうれしいです。
制限ルールを使用して、次のアルゴリズムを使用して、すべてのエッジが有効な新しいグラフにグラフを変換することができます。あなたが来た場合は、のままに（1,2）を除去する（2,3）
経路（1,2,3）の制限は、二つのルールに分割することができ（2,3）を削除してから（1,2）を削除する。
これをグラフに挿入するには、ノード2のコピーをそれぞれのケースに挿入することができます。それぞれのケースで有効なエッジの後に、新しいノードを1_2と2_3と呼びます。両方のノードで、すべての着信エッジと発信エッジから制限されたエッジを除いたものをコピーします。例えば
：
Nodes = [1,2,3,4]
Edges = [(1,2),(2,3),(4,2)]
有効なパスのみ4-> 2-> 3ない1-> 2-> 3でなければなりません。グラフを展開します：
Nodes = [1,1_2,2_3,3,4] # insert the two states of 2
Edges = [ # first case: no (1_2,3) because of the restriction
(1,1_2), (4, 1_2)
# 2nd case, no (1,2_3)
(2_3,3), (4,2_3)]
このグラフの唯一の有効なパスは4-> 2_3-> 3です。これは、元のグラフの4-> 2-> 3に単純に対応します。
既存の解決策が見つからない場合は、少なくともこの回答が役立つことを願っています。制限ルールが長くなると、ノード数が急激に増加するため、このアルゴリズムは単純すぎるか、問題は難しくなります;-)
私は非常に滑らかに見えますが、私はあなたのアプローチを完全に理解しているかどうかはわかりません。だから、1_2とany_2は2_2のようにすべての着信/発信エッジを持ちますが、1_2は1_2-> 3であり、any_2は1 - > any_2はありません。私は2つのエッジ1-> 2と2-> 3の治療の間にある程度の非対称性があるように思われるので、これを求めている。 – yosukesabai
私が疑問に思っているもう一つの問題は、問題が1-> 2-> 3だけでなく、間接的にも**を許さないということです。あなたのセットアップでは、1-> 2-> 5-> 6-> 7-> 3-> 4のようなパスが1から4へのパスを見つける方法は禁止されていますか？このパスには、間接的に1-> 2-> 3が含まれます。 – yosukesabai
@yosukesabai：良い点、私はあなたの最初の点を修正したと思う。 2番目のコメントに関して、私は問題を中間ノードのない1つの制限されたパスだけを除外すると解釈した。私はそれがどのように中間体でうまくいくのか分かりません。 –
ノードのデータ{color = ['blue' ]}ノード1の場合、ノード2は{color = ['red'、 'blue']}を持ち、node3は{color = ['red']}です。次に、networkx.algorithmsを使用します。 astar_path（）アプローチ設定が
これはNetworkX内で実行できるのかどうかわかりませんが、（概念的には）簡単な方法はノード1を監視し、使用されている場合はノード3を完全に削除することです。 – Wilduck