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()

对于此示例数据，我最终得到以下图表：

样本图

从这个小样本中，很容易看出一些节点 ([z,n],[x,m][v,p]) 是只有两个节点的树。我想检测并消除这些，因为我只关心大于两个节点的树。我敢肯定有很多方法可以做，任何人都可以提出建议或举个例子吗？

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

您可以使用 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()

这将产生唯一符合要求的图表：

在此处输入图像描述

请注意，这是确定具有最长路径（就距离而言）的图形的一般方法的简化。因此，如果您创建包含权重的图表，您可以在更改权重的符号后应用 bellman ford：

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 回答
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()

我读取了两次文件，您可以通过将值存储在列表中来重构代码以读取一次。

顺便说一句，我希望该示例的解决方案包含：

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