6

NetworkXグラフがあります。複数のノード間でエッジ収縮を行う方法を知りたいのですが。

たとえば、X、Y、Zを契約したい場合：

         _ node A _
       _/    |     \_
node X --- node Y --- node Z

になります

           node A 
             |     
           node XYZ (or whatever X/Y/Z)

グラフの作成は問題ではありません。できます。同じ「意味」を持つノードをマージしてグラフを縮小したいと思います。「endlvl」（ノード名の長さは7に等しい）と呼び、互いにリンクされているノードです。

NetworkXで凝縮関数を見つけたので、それを使用してみました。

# edge contraction for same nodes
# for each node, get the links to other nodes "end lvl"
# if there is such a link, it means that these node are
# the sames
#
# copy graph
I = G
for n,d in G.nodes(data=True):
    if n in I.nodes():
        if len(n) == 7:
            # list of nodes adjacent to n : filter only "end lvl" nodes
            neighbors = [ node for node in I.neighbors(n) if len(node) == 7 ]
            nodes_to_merges = neighbors.append(n)
            I = nx.condensation(I,scc=nodes_to_merges)

JSONに変換したときに得たものは次のとおりです。

{"directed": true, "graph": [], "nodes": [{"id": 0}], "links": [], "multigraph": false}

ご覧のとおり問題があります...

関数への参照はここにあります。

4

2 に答える 2

4

どうですか：

add_node(XYZ)
add_edge(XYZ, A)
for edge incident on (X, Y, Z):
    v = nodes in edge not in (X, Y, Z, A)
    if v:
       remove_edge(edge)
       add_edge(v, XYZ)
for node in (X, Y, Z):
    remove_node(node)
于 2013-03-26T15:38:09.737 に答える
0

nx.condensation（一般にノードのグループではなく、強く接続されたコンポーネントを縮小するためのもの）を使用しようとする代わりに、次の関数を使用します。

http://networkx.readthedocs.io/en/stable/reference/classes.graph.html#adding-and-removing-nodes-and-edges

折りたたまれたノードの1つを除くすべてを削除し、それらのノードを再配線します。

于 2013-03-27T09:13:06.207 に答える