All shortest paths in networkx subject to routing criteria

Question

I have a weighted undirected graph (~90 nodes, ~120 edges) in which I want to find the shortest path between all combinations of a subset of nodes, stored as list 'endPoints'. The shortest paths are subject to a few criteria:

1. For each combination of (s)ource and (d)estination nodes in endPoints there is a different set of intermediary nodes in the graph that I require the shortest path to include.
2. For each combination of s and d there is a different set of intermediary nodes that I require the shortest path to exclude.
3. For each combination of s and d any other node in the graph not specified in either 1) or 2) can optionally be traversed.

e.g. For a graph containing nodes A-E I want to find the shortest paths between AB, AC, AD, AE, BC, BD, BE, CD, CE, DE. For AE the path must go via B and C but must not pass through D; For BD the path must go via A, must not go via C, can optionally go via E, etc.

I think the approach to use is to find all simple paths in the graph between each s and d, then to iterate over them excluding those that do not meet criteria 1) and 2) and then to find the shortest path for each remaining s and d combination using nx.shortest_path.

Finding all simple paths returns generator objects for each s-d pair and I'm not sure how to iterate over these s,d generators to apply criteria 1) and 2)

Can anyone help with next steps (or suggest an alternative approach) please?

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

You could do something like this:

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

EDIT: If you want to to collect the length of the paths too, then you could pack both, path and length, into a tuple:

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

Assumptions:

• The required "inclusions"/"exclusions" are stored in dictionaries called includes/excludes.
• The path length is the sum of the edge weights (edge attribute "weight") and can therefore be calculated by nx.path_weight. If that's not the case then adjust accordingly (e.g. by replacing nx.path_weight(...) with len(path) etc.).

The following example will hopefully illustrate that:

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

Result is

{(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]]}

or with length

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