私は(時々サイクルを持っているかもしれません)有向グラフにおける最小スパニングツリー(あるいは森)を見つけたいです。説明したものhereは多少の誤差があります。 Pythonで実際に動作するこのアルゴリズムのパッケージ/コードはありますか?私はそれを使用していないにもかかわらず(有向グラフの場合)チュウ劉エドモンドのアルゴリズム
1
A
答えて
1
、GitHubのからhereの実装。 私は以下のことの本質を添付しました。 それはGitHubのリポジトリなので、それはそれがそこからコードを使用することが好ましいです変更することができます。 これを使用する場合は、作者に信用を与えてください:Martin-Louis Bright。
import sys
def _input(filename):
prices = {}
names = {}
for line in file(filename).readlines():
(name, src, dst, price) = line.rstrip().split()
name = int(name.replace('M',''))
src = int(src.replace('C',''))
dst = int(dst.replace('C',''))
price = int(price)
t = (src,dst)
if t in prices and prices[t] <= price:
continue
prices[t] = price
names[t] = name
return prices,names
def _load(arcs,weights):
g = {}
for (src,dst) in arcs:
if src in g:
g[src][dst] = weights[(src,dst)]
else:
g[src] = { dst : weights[(src,dst)] }
return g
def _reverse(graph):
r = {}
for src in graph:
for (dst,c) in graph[src].items():
if dst in r:
r[dst][src] = c
else:
r[dst] = { src : c }
return r
def _getCycle(n,g,visited=set(),cycle=[]):
visited.add(n)
cycle += [n]
if n not in g:
return cycle
for e in g[n]:
if e not in visited:
cycle = _getCycle(e,g,visited,cycle)
return cycle
def _mergeCycles(cycle,G,RG,g,rg):
allInEdges = []
minInternal = None
minInternalWeight = sys.maxint
# find minimal internal edge weight
for n in cycle:
for e in RG[n]:
if e in cycle:
if minInternal is None or RG[n][e] < minInternalWeight:
minInternal = (n,e)
minInternalWeight = RG[n][e]
continue
else:
allInEdges.append((n,e))
# find the incoming edge with minimum modified cost
minExternal = None
minModifiedWeight = 0
for s,t in allInEdges:
u,v = rg[s].popitem()
rg[s][u] = v
w = RG[s][t] - (v - minInternalWeight)
if minExternal is None or minModifiedWeight > w:
minExternal = (s,t)
minModifiedWeight = w
u,w = rg[minExternal[0]].popitem()
rem = (minExternal[0],u)
rg[minExternal[0]].clear()
if minExternal[1] in rg:
rg[minExternal[1]][minExternal[0]] = w
else:
rg[minExternal[1]] = { minExternal[0] : w }
if rem[1] in g:
if rem[0] in g[rem[1]]:
del g[rem[1]][rem[0]]
if minExternal[1] in g:
g[minExternal[1]][minExternal[0]] = w
else:
g[minExternal[1]] = { minExternal[0] : w }
def mst(root,G):
RG = _reverse(G)
if root in RG:
RG[root] = {}
g = {}
for n in RG:
if len(RG[n]) == 0:
continue
minimum = sys.maxint
s,d = None,None
for e in RG[n]:
if RG[n][e] < minimum:
minimum = RG[n][e]
s,d = n,e
if d in g:
g[d][s] = RG[s][d]
else:
g[d] = { s : RG[s][d] }
cycles = []
visited = set()
for n in g:
if n not in visited:
cycle = _getCycle(n,g,visited)
cycles.append(cycle)
rg = _reverse(g)
for cycle in cycles:
if root in cycle:
continue
_mergeCycles(cycle, G, RG, g, rg)
return g
if __name__ == "__main__":
try:
filename = sys.argv[1]
root = sys.argv[2]
except IndexError:
sys.stderr.write('no input and/or root node specified\n')
sys.stderr.write('usage: python edmonds.py <file> <root>\n')
sys.exit(1)
prices,names = _input(filename)
g = _load(prices,prices)
h = mst(int(root),g)
for s in h:
for t in h[s]:
print "%d-%d" % (s,t)
+1
更新しました。コメントありがとうございます。 – user3693922
関連する問題
- 1. アルゴリズムは有向グラフで
- 2. 有向グラフのリーダーの選出アルゴリズム
- 3. ワンパス力有向グラフ描画アルゴリズム
- 4. 無向グラフのアルゴリズム*
- 5. アルゴリズム設計、有向グラフのアルゴリズムを実装
- 6. 有向グラフによる有向パスの類似性を比較するアルゴリズム
- 7. 有向グラフのすべての弱結合成分を見つけるアルゴリズム
- 8. 有向グラフと無向グラフの区別
- 9. 有向グラフの制約付き最大スパニングサブツリーの近似アルゴリズム
- 10. 有向グラフの固有ベクトル
- 11. オイラーパス、有向グラフ
- 12. プロローグ内の有向グラフ
- 13. 有向グラフのPrologルート
- 14. 重み付き有向グラフ
- 15. 有向非巡回グラフ
- 16. プロローグ内の有向グラフのサイクル
- 17. 有向グラフ内のすべてのルート
- 18. Java/GWT用のNoSQL DB(有向グラフ)?
- 19. QuickGraphライブラリの重み付き有向グラフ
- 20. D3強制有向グラフの設定
- 21. Matlabの有向グラフ最短サイクル
- 22. 無向グラフのパスの衝突をテストするアルゴリズム
- 23. グラフ(グラフ)アルゴリズム
- 24. Dijkstraのアルゴリズムを無向グラフに変更する
- 25. NetworkXは、私はそのようなことをネットワークXに有向グラフGがあると有向グラフ
- 26. 実際の有向グラフからErdős-Rényiモデルを使って有向グラフを生成する
- 27. 加重無向グラフの合計ペアワイズコスト
- 28. 有向グラフで島を見つける
- 29. DAG(有向非循環グラフ) - QAbstractItemModel
- 30. D3 4.0有向エッジとラベル付きグラフ
すべてのヘルプは高く評価されます。 – Erin