7

我正在使用networkx（python库来处理图形）。我基本上有具有各种边缘的节点，但想看看如果使用连接最多的节点，路径会是什么样子。

我可以使用这个命令来查看连接数：

len(G.edges(CurrentNode))

我可以得到边的数量，但我不知道如何将它作为路径应用到列表中。例如，我可以将此数字添加为属性，但我认为在查找路径时不会考虑属性，并且因为我是在连接边缘之后添加它，所以我无法将权重添加到边缘本身。另一个问题是分数越高，我越想要遵循的路径，但是对于边缘，我认为它遵循最低的加权边缘。

我想知道其他人根据节点的某些特征采取什么方法来查找路径？如果有人知道如何为 networkx 做到这一点，那就太好了！但我认为 networkx 有很多特性，所以如果我能得到理论或一般方法，我相信我可以找到一种在 python 中做到这一点的方法。

更新：对不起，我可能解释错了。我知道我可以向节点添加属性，但我不确定如何根据这些属性做出路径决策。因此，就我而言，根据某些条件，我在节点之间添加边。每组节点代表不同的一天（day1data.., day2data.., day3data..），所以只有在某些规则匹配的情况下，我才会将第 1 天的几个节点连接到第 2 天的节点。一旦我连接了边缘，我希望在选择路径时更加重视这些边缘。所以我为当天的每个节点添加了一个属性“权重”，它基本上是连接该节点的边的总数。我的问题是，在任何路径决策中都没有使用 weight 属性，因为它是我创建并标记自己的属性（我可以创建一个名为 'abc'=' 的标签 hello world'，它将将该属性应用于节点）。创建路径时如何考虑这个权重（边缘已经创建，所以我认为我不能回去重新创建它们）？

4

3 回答 3

6

您当然可以在 NetworkX 中为边添加权重。事实上，您可以为边设置任意数据，因为它基本上是一个dict.

In [30]: import networkx as nx

In [31]: G = nx.Graph()

In [32]: G.add_edge(1, 2, weight=3, type="green")

In [33]: G[1][2]
Out[33]: {'type': 'green', 'weight': 3}

In [34]: G[1][2]["weight"]
Out[34]: 3

此外，您可以在添加边（或节点）后更改它们的参数。

In [35]: G[1][2]["weight"] = 5

In [36]: del G[1][2]["type"]

In [37]: G[1][2]["color"] = "green"

In [38]: G[1][2]
Out[38]: {'color': 'green', 'weight': 5}

您当然可以根据权重（或权重参数中指定的任何其他属性）计算路径。

In [39]: G.add_edge(1, 3, weight=1)

In [40]: G.add_edge(2, 3, weight=2)

In [41]: G.edges()
Out[41]: [(1, 2), (1, 3), (2, 3)]

In [42]: nx.shortest_path(G, source=1, target=2, weight="weight")
Out[42]: [1, 3, 2]

对于您的情况，确定边缘权重可能很棘手。请记住，加权最短路径通常使用Djikstra 算法计算，并且它倾向于较小的权重。它还需要正权重。一种可能的解决方案是1/max(k_i,k_j)为边缘分配权重，(i,j)其中是节点和的度数。k_ik_jij

计算转移概率上的最短路径的正确方法是将边权重转换为表示意外：即概率的负对数。这导致权重为正，然后任何给定的最短路径都被解释为最小化意外。而且由于 Dijkstra 的算法对权重求和，所以它是在对数空间中进行的，这意味着它实际上是在乘以概率。然后，要恢复观察任何给定最短路径的联合概率，您只需采用负意外的指数即可。

于 2011-10-20T23:36:10.327 回答
0

来自NetworkX 教程

>>> G.add_edge(1, 2, weight=4.7 )
>>> G.add_edges_from([(3,4),(4,5)], color='red')
>>> G.add_edges_from([(1,2,{'color':'blue'}), (2,3,{'weight':8})])
>>> G[1][2]['weight'] = 4.7
>>> G.edge[1][2]['weight'] = 4

看起来可以在事后添加权重。

于 2011-10-20T23:20:30.390 回答
0

我考虑自制的唯一方法是attribute在框架本身中编辑文件。

您要查找的文件是networkx/algorithms/shortest_paths/weighted.py

里面会有一个get_weight function看起来像这样的 lambda 声明：

if G.is_multigraph():
    get_weight = lambda u, v, data: min(
        eattr.get(weight, 1) for eattr in data.values())
else:
    get_weight = lambda u, v, data: data.get(weight, 1)

我想给我的nodesa 一定的权重，所以我这样修改它：

if G.is_multigraph():
    get_weight = lambda u, v, data: min(
        eattr.get(weight, 1) for eattr in data.values())
else:
    get_weight = lambda u, v, data: (data.get(weight,0) + nx.get_node_attributes(G, "node_weight").get(v,0))

我将默认边权重设置为 0：data: data.get(weight,0)并添加了我自己的属性“node_weight”的值（默认为 0）。

data: (data.get(weight,0) + nx.get_node_attributes(G, "node_weight").get(v,0))

v是图中下一个可达node的。

现在您可以attribute在创建图表后进行设置。

nx.set_node_attributes(G, "node_weight", {1:3.5, 2:56})
于 2017-11-10T13:59:10.693 回答