networkx 中所有符合路由标准的最短路径

Question

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

对于端点中的（s）源节点和（d）目的地节点的每个组合，图中有一组不同的中间节点，我需要到 include 的最短路径.
对于 s 和 d 的每个组合，都有一组不同的中间节点，我需要最短路径到 exclude。
对于 s 和 d 的每个组合，可以选择遍历图中未在 1) 或 2) 中指定的任何其他节点。

例如对于包含节点 A-E 的图，我想找到 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.

为每个 s-d 对找到所有简单路径 returns 生成器对象，我不确定如何迭代这些 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

returns

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

Answer 1

你可以这样做：

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)]}

networkx 中所有符合路由标准的最短路径

All shortest paths in networkx subject to routing criteria

python

graph-databases

networkx