Find All Paths With Cumulative Edge Weight Upper Limit

[seanlaw]

Once a graph (with different edge weights) has been defined, what is the best way to obtain the top-k paths that have a (summed) edge weight that is less than or equal to, say, 30?

[takemaru]

Use linear_constraints option for GraphSet.graphs method.

from graphillion import GraphSet
import graphillion.tutorial as tl

# Create 3x3 grid graph
N = 3
E = list(tl.grid(N - 1, N - 1))
GraphSet.set_universe(E)

# Obtain the set of paths between vertices 1 and 9
paths = GraphSet.paths(1, 9)
print(paths.len())  # 12

# Restrict the set to the paths whose weight is at most 5.0 assuming all edges have a weight of 1.0
weights = [(u, v, 1.0) for u, v in E]
bounds = [0, 5.0]
restricted_paths = GraphSet.graphs(
    graphset=paths,
    linear_constraints=[(weights, bounds)],
)
print(restricted_paths.len())  # 6