1

csvファイルに次のようなデータがあります。

a,b,50
b,c,60
b,e,25
e,f,20
z,n,10
x,m,25
v,p,15

NetworkXとMatplotlibを使用してデータをグラフ化しようとしていますが、私のcsvには、グラフから意味をなすために非常に多くの行/ノードがあります。

プロットに使用しているコードの重要な部分は次のとおりです。

import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()

f = open("test_data.csv", "r")

for line in f:
    node1, node2, weight1 = line.split(",")
    G.add_edge(node1, node2)

nx.draw(G)
plt.show()

このサンプルデータの場合、次のグラフになります。

sample_plot

この小さなサンプルから、一部のノード（[z、n]、[x、m] [v、p]）が2つのノードしかないツリーであることが簡単にわかります。私は2ノードを超えるツリーのみを対象としているため、これらを検出して排除したいと思います。いくつかの方法があると確信していますが、誰かが提案したり、例を挙げたりすることはできますか？

4

3 に答える 3

1

特定のケースでは、エッジリストを反復処理して、ターゲットノード自体に隣接ノードがあるかどうかをグラフに問い合わせてみてください（たとえば、ターゲットが別のエッジのソースである場合）。ターゲットに他のネイバーが含まれていない場合、それは基準を満たしています。

コード：

for src, trg in G.edges():
    if G.neighbors(trg) == []:
        G.remove_edge(*(src,trg)) # Need the * to unpack the edge nodes

Gには、エッジ（a、b）、（b、e）のみを含める必要があります:(以下のipython出力を参照）

In [35]: G.edges()
Out[35]: [('a', 'b'), ('b', 'e')]

頑張ってください！

于 2012-12-31T06:41:55.227 に答える
1

nx APIがわからないので、G digraphオブジェクトを使用してこれを解決するのではなく、dictだけを使用してこれを解決します

import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()

f = open("test_data.csv", "r")

blocs_by_node = {}
for line in f:
    node1, node2, weight1 = line.split(",")
    if node1 not in blocs_by_node and node2 not in blocs_by_node :
        bloc = [node1, node2]
        blocs_by_node[node1] = bloc
        blocs_by_node[node2] = bloc
    elif node1 not in blocs_by_node and node2 in blocs_by_node :
        bloc = blocs_by_node[node2]
        bloc.append(node1)
        blocs_by_node[node1] = bloc
    elif node1 in blocs_by_node and node2 not in blocs_by_node :
        bloc = blocs_by_node[node1]
        bloc.append(node2)
        blocs_by_node[node2] = bloc
    elif blocs_by_node[node1] is not blocs_by_node[node2] :
        bloc = blocs_by_node[node1]
        for node in blocs_by_node[node2] :
            bloc.append(node)
            blocs_by_node[node] = bloc

f.close()

f = open("test_data.csv", "r")

for line in f:
    node1, node2, weight1 = line.split(",")
    if len(blocs_by_node[node1]) > 2 :
        G.add_edge(node1, node2)

f.close()

nx.draw(G)
plt.show()

ファイルを2回読み取りました。値をリストに保存することで、コードをリファクタリングして1回読み取ることができます。

ちなみに、この例のソリューションには次のものが含まれていると思います。

[('a', 'b'), ('b', 'c'), ('b', 'e'), ('e', 'f')]
于 2012-12-31T07:45:35.300 に答える
1

networkX bellman_fordメソッドを使用して、指定された最小値よりも長いパスを見つけることができます。このためには、重みが-1に設定された有向グラフ（またはグラフ）Gが必要です。

次のコードは、このスレッドに基づいています。

import networkx as nx
import matplotlib.pyplot as plt

data = (('a','b',50), ('b','c',60), ('b','e',25),
        ('e','f',20), ('z','n',10), ('x','m',25),
        ('v','p',15))

G = nx.DiGraph()
for node1, node2, weight1 in data:
    G.add_edge(node1, node2, weight=-1)

min_lenght = 2
F = nx.DiGraph()   #filtered graphs

# check all edges with bellman_ford
for u, v in G.edges():
    vals, distances = nx.bellman_ford(G, u)
    if min(distances.values()) < - min_lenght:
        for u, v in vals.items():
            if v:
                F.add_edge(v, u)

nx.draw(F)
plt.show()

これにより、要件に準拠する唯一のグラフが生成されます。

ここに画像の説明を入力してください

これは、（距離の観点から）最長のパスを持つグラフを決定するための一般的な方法を単純化したものであることに注意してください。したがって、重みを含むグラフを作成する場合は、重みの符号を変更した後にベルマンフォードを適用できます。

G = nx.DiGraph()
for node1, node2, weight1 in data:
    G.add_edge(node1, node2, weight=weight1)

min_lenght = 100  

H = nx.DiGraph(G)  # intermediate graph
# change sign of weights
for u, v in H.edges():
    H[u][v]['weight'] *= -1

# check all edges with bellman_ford
for u, v in G.edges():
    vals, distances = nx.bellman_ford(H, u)
    if min(distances.values()) < - min_lenght:
        #--- whatever ----
于 2012-12-31T10:04:17.460 に答える