python - networkx 中的所有最短路径均受路由标准约束

问题描述

我有一个加权无向图（~90 个节点，~120 个边），我想在其中找到节点子集的所有组合之间的最短路径，存储为列表“endPoints”。最短路径受以下几个标准的约束：

对于 endPoints 中 (s)ource 和 (d)estination 节点的每种组合，图中都有一组不同的中间节点，我需要最短路径来包含它们。
对于 s 和 d 的每种组合，都有一组不同的中间节点，我需要最短路径来排除它们。
对于 s 和 d 的每个组合，可以选择遍历图中未在 1) 或 2) 中指定的任何其他节点。

例如，对于包含节点 AE 的图，我想找到 AB、AC、AD、AE、BC、BD、BE、CD、CE、DE 之间的最短路径。对于 AE，路径必须经过 B 和 C，但不能经过 D；对于 BD，路径必须经过 A，不得经过 C，可以选择经过 E，等等。

我认为使用的方法是在图中找到每个 s 和 d 之间的所有简单路径，然后对它们进行迭代，排除那些不符合标准 1) 和 2) 的路径，然后为每个剩余的 s 和d 组合使用 nx.shortest_path。

查找所有简单路径会返回每个 sd 对的生成器对象，我不确定如何迭代这些 s,d 生成器以应用标准 1) 和 2)

任何人都可以帮助下一步（或建议替代方法）吗？

from itertools import combinations

allPaths = []
for s, d in combinations(endPoints, 2):
    allPaths.append((s, d, nx.all_simple_paths(G, s, d, cutoff=999)))

allPaths

[('ep01',
  'ep02',
  <generator object _all_simple_paths_graph at 0x0000025656C91BC8>),
 ('ep01',
  'ep03',
  <generator object _all_simple_paths_graph at 0x0000025656C91C48>),
 etc.

标签： pythonnetworkxgraph-databases

解决方案

你可以这样做：

import networkx as nx
from itertools import combinations

def check_criteria(path, include, exclude):
    path_set = set(path)
    return include <= path_set and exclude.isdisjoint(path_set)

min_paths = {}
for s, d in combinations(end_points, 2):
    min_len = None
    paths = []
    for path in nx.all_simple_paths(G, s, d):
        if check_criteria(path, includes[s, d], excludes[s, d]):
            path_len = nx.path_weight(G, path, "weight")
            if min_len is None:
                min_len = path_len
            if path_len == min_len:
                paths.append(path)
            elif path_len < min_len:
                paths = [path]
                min_len = path_len
    min_paths[s, d] = paths

编辑：如果您也想收集路径的长度，那么您可以将路径和长度都打包到一个元组中：

            ...
            if path_len == min_len:
                paths.append((path, path_len))
            elif path_len < min_len:
                paths = [(path, path_len)]
            ...

假设：

所需的“包含”/“排除”存储在名为includes/的字典中excludes。
路径长度是边缘权重（边缘属性"weight"）的总和，因此可以通过计算nx.path_weight。如果不是这种情况，则相应地进行调整（例如，通过替换nx.path_weight(...)等len(path)）。

以下示例有望说明这一点：

import networkx as nx
from itertools import combinations
from random import seed, random, sample, randint

seed(12345)
n = 20
G = nx.gnp_random_graph(n, 0.2, seed=12345)
for edge in G.edges:
    G.edges[edge]["weight"] = random()
end_points = [0, 1, 2]
combos = list(combinations(end_points, 2))
nodes = set(G.nodes)
includes = {
    c: set(sample(nodes - set(c), randint(1, 3))) for c in combos
}
excludes = {
    c: set(sample(nodes - includes[c].union(c), randint(1, 3))) for c in combos
}

includes = {(0, 1): {10}, (0, 2): {18, 6, 15}, (1, 2): {7}}
excludes = {(0, 1): {2, 6}, (0, 2): {8}, (1, 2): {8, 9, 13}}

结果是

{(0, 1): [[0, 9, 11, 10, 7, 4, 1]],
 (0, 2): [[0, 6, 15, 1, 4, 18, 2]],
 (1, 2): [[1, 4, 7, 5, 11, 18, 2]]}

或长度

{(0, 1): [([0, 9, 11, 10, 7, 4, 1], 2.062744452478362)],
 (0, 2): [([0, 6, 15, 1, 4, 18, 2], 1.2822628572757941)],
 (1, 2): [([1, 4, 7, 5, 11, 18, 2], 1.2624381263403164)]}

python - networkx 中的所有最短路径均受路由标准约束

问题描述

解决方案

推荐阅读