Search code examples
pythongraphnetworkxtraversal

Specify depth for edge in NetworkX graph

I have an undirected graph for which I'd like to find the shortest path without knowing the source and sink. NeworkX's all_pairs_dijkstra_path allows the discovery of all shortest paths without knowing source and sink, as long as it is given a length cutoff (measuring the depth of traversal).

Currently, every edge traversed adds +1 to depth. Is there a way to specify the edge attributes such that

  • each edge carries a weight w by which the path length (and shortest path) is evaluted
  • each edge also carries a depth d by which a specified total depth terminates the path search?

enter image description here

Solution

  • When creating the graph, you need to give each edge an attribute representing your distance:

    G.add_edge(0, 1, distance=0.4)

    When computing shortest paths, you can then specify that attribute such that the weighted shortest path is computed:

    paths = nx.shortest_path(G, weight='distance')

    all_pairs_shortest_paths only computes the unweighted case; however, shortest_path computes all pairs, too, if you don't specify the source and target node.

    Edit

    There isn't anything in networkx that fits the bill (AFAIK). However, you can create a generator for all paths between two nodes ordered in terms of total "depth" using nx.simple_paths.shortest_simple_paths, and then compute the shortest path based on weight:

    import itertools
import networkx as nx
import numpy as np

def path_cost(G, path, attr='weight'):
    return sum([G[path[i]][path[i+1]][attr] for i in range(len(path)-1)])

G = ...

cutoff = 3
output = dict()
for source, target in itertools.combinations(list(G.nodes), 2):
    minimum_cost = np.inf
    for path in nx.simple_paths.shortest_simple_paths(G, source, target, weight='depth'):
        if path_cost(G, path, 'depth') > cutoff:
            continue # to next source, target pair
        else:
            if path_cost(G, path, 'weight') < minimum_cost:
                output[(source, target)] = path