CODEWITHSUNDEEP
pythongraphnetworkxtraversal
batlike
batlike

Reputation: 698

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

enter image description here

Upvotes: 0

Views: 409

Answers (1)

Paul Brodersen
Paul Brodersen

Reputation: 13031

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

Upvotes: 1

Related Questions