Constrained short path algorithm in networkx?

Question

I am using networkx to work on shortest path problems. I am mostly using shortest_path. I was wondering if, with the current version of networkx, it is possible to constrain the shortest path calculation?

The example below generated these two shortest paths between A and G:

The picture on the left shows the best route when minimizing a 'length' attribute and the one on the right, when minimizing a 'height' attribute.

If we compute the stats for these routes we got:

Best route by length: ['A', 'B', 'E', 'F', 'D', 'G']
Best route by height: ['A', 'C', 'E', 'G']
Stats best routes: {
                   'by_length': {'length': 13.7, 'height': 373.0}, 
                   'by_height': {'length': 24.8, 'height': 115.0}
                   }

Is there a way to add a constrain when calculating the shortest path? (e.g. calculate the shortest path by minimizing the length attribute but also keeping height<300

Code to compute the graph network:

import matplotlib.pyplot as plt
from itertools import combinations, groupby
import os
import numpy as np
import networkx as nx
import random


# 1. Define test network 
MG = nx.MultiDiGraph()
MG.add_edges_from([("B", "A", {"length": 0.8}), ("A", "B", {"length": 1.}), ("D", "G", {"length": 3.5}),
                   ("B", "D", {"length": 20.8}), ("A", "C", {"length": 9.7}), ("D", "C", {"length": 0.3}),
                   ("B", "E", {"length": 4.8}), ("D", "E", {"length": 0.05}), ("C", "E", {"length": 0.1}),          
                   ("E", "C", {"length": 0.7}), ("E", "F", {"length": 0.4}), ("E", "G", {"length": 15.}),           
                   ("F", "C", {"length": 0.9}), ("F", "D", {"length": 4.}),                       
                  ])
attrs = {'B': {"x": -20., "y": 60.}, 'A': {"x": 28., "y":55.},
         'C': {"x": -12., "y": 40.}, 'D': {"x": 40., "y":45.},
         'E': {"x": 8., "y": 35.}, 'F': {"x": -8., "y":15.},    
         'G': {"x": 21., "y":5.},    
        }

for num, (k,v) in enumerate(attrs.items()):
    attrs[k]={**v,
             }  
nx.set_node_attributes(MG, attrs)

rng = np.random.default_rng(seed=42)
random_height = list(rng.uniform(low=0, high=100, size=len(MG.edges)).round(0))
attrs={}
for num, edge in enumerate(MG.edges):
    attrs[edge]={'height': random_height[num]}
nx.set_edge_attributes(MG, attrs)


# 2. Calculate shortest route
best_route_by_length = nx.shortest_path(MG, "A", "G",weight="length")
print(f"Best route by length: {best_route_by_length}")

best_route_by_height = nx.shortest_path(MG, "A", "G",weight="height")
print(f"Best route by height: {best_route_by_height}")

# 3. Get stats for each route

def get_route_edge_attributes(
    G, route, attribute=None, minimize_key="length", retrieve_default=None
):
    """
    """
    attribute_values = []
    for u, v in zip(route[:-1], route[1:]):
        # if there are parallel edges between two nodes, select the one with the
        # lowest value of minimize_key
        data = min(G.get_edge_data(u, v).values(), key=lambda x: x[minimize_key])
        if attribute is None:
            attribute_value = data
        elif retrieve_default is not None:
            attribute_value = data.get(attribute, retrieve_default(u, v))
        else:
            attribute_value = data[attribute]
        attribute_values.append(attribute_value)
    return attribute_values


stats_best_route={}
stats_best_route['by_length']={'length': sum(get_route_edge_attributes(MG,
                                                                   best_route_by_length,
                                                                  'length')),
                              'height': sum(get_route_edge_attributes(MG,
                                                                   best_route_by_length,
                                                                  'height'))}
stats_best_route['by_height']={'length': sum(get_route_edge_attributes(MG,
                                                                   best_route_by_height,
                                                                  'length')),
                              'height': sum(get_route_edge_attributes(MG,
                                                                   best_route_by_height,
                                                                  'height'))}

print(f"Stats best routes: {stats_best_route}")

Edit 07/06/21

My problem is potentially too large to be able to use a brute force solution.

I also opened a post in the networkx discussion page, it seems possible to implement a special class that acts numerical in single_source_dijkstra. However, this solution is not perfect: if there are two admissible short paths (in height), the algorithm will find the shorter one regardless of its height. This can make it look impossible to reach a destination node, when an admissable path exists... (more details here: https://github.com/networkx/networkx/discussions/4832#discussioncomment-778358)

Diffract

Answer 1

Approximate solution:

• run shortest by length
• if height within contraint then DONE
• remove link in path with greatest height
• repeat until DONE.

Snags:

• if path link with greatest height is critical, removing it will make the destination unreachable. If this happens, it will be neccessary to go back, replace the highest link and remove second highest ...

• finding optimim path is not guaranteed.

Calder

Answer 2

Is your true problem small enough that you could use brute force with all_simple_paths()?

from networkx.algorithms.simple_paths import all_simple_paths

shortest_paths_constrained = []
for path in all_simple_paths(MG, "A", "G"):
    if sum(get_route_edge_attributes(MG, path, 'height')) < 300:
        path_length = sum(get_route_edge_attributes(MG, path, 'length'))
        result = (path, path_length)
        if not shortest_paths_constrained:
            shortest_paths_constrained.append(result)
        elif path_length == shortest_paths_constrained[0][1]:
            shortest_paths_constrained.append(result)
        elif path_length < shortest_paths_constrained[0][1]:
            shortest_paths_constrained = [result]

which gives shortest_paths_constrained as

[(['A', 'C', 'E', 'F', 'D', 'G'], 17.7)]

Inefficient -- but, if practical, it will definitely give the correct solution. Note that if it's important to your problem, it should also return all ties for shortest by length within the height constraint. Up to you how you want to break possible ties if needed.

The good news is that all_simple_paths() returns a generator rather than attempting to find all paths at once, so fitting all paths in memory isn't a concern. How long it takes to finish computing is a much bigger mystery however...

Lentigo

Thank you but my problem can be too large to be able to use brut_force. I added more information in my original post. – Diffract