| | |
- changeSolutionAlongPath(N, x, path, value)
- Change x along path by value; path might use backward arcs.
- completeSolution(N, x)
- Completes a solution x with 0 values for every a not present in x.
- computeFloydWarshall(N, S, T)
- Return the shortest path between any node in S and any node in T, by
computing Floyd-Warshall.
- computePathWeight(N, path)
- Return the sum of 'weight' for arcs on path.
- computeShortestPath(N, S, T)
- Return the shortest path between any node in S and any node in T.
Used approach differs depending on the size of the larger set compared to
nodes overall. If it is large, compute single-source Dijkstra for all nodes
in the smaller set. Else, compute pairwise bidirectional Dijkstra.
- computeShortestPathBidirectional(N, S, T)
- Return the shortest path between any node in S and any node in T, by
computing bidirectional Dijkstra for all node pairs in S and T.
- computeShortestPathFloyd(N, S, T)
- Return the shortest path between any node in S and any node in T.
Used approach differs depending on the size of the larger set compared to
nodes overall. If it is large, compute Floyd-Warshall.
Else, compute pairwise bidirectional Dijkstra.
- computeShortestPathSingleSource(N, S, T)
- Return the shortest path between any node in S and any node in T, by
computing single-source Dijkstra for all nodes in the smaller set.
- coverFromSolution(N, x)
- Return a cover made of all bounds violated by x.
- coverFromSolutionResidual(N, x)
- Return a cover made of bounds violated by x; x is supposed to come from a
residual network, i.e., all original arcs have a value and negative flow in
x is given on reverse arc.
- coverFromSolutionUndirected(N, x, edges)
- Return a cover made of bounds on "edges" violated by x; "edges" can be
undirected and negative flow in x is given on reverse arc.
- emptyMap(N)
- Return a dictionary with every node as a key and None as value.
- emptySolutionDict(N)
- Return a solution dict which contains an empty dict for every node.
- flowExcessAtNode(N, x, v)
- Return $b_v - x_{(v,w)} + x_{(w,v)}$.
- joinCovers(C1, C2)
- Replace C1 with the union of C1 and C2.
- sizeOfCover(C)
- Return the number of bounds in C.
- solutionFromResidualGraph(N, R)
- Return a solution dict, picked from "flow" values in R.
- solutionFromResidualSolution(N, x)
- Return a solution on the original graph, build from a solution on the
residual graph, where negative flow is given on the reversed arc.
- unsaturatedSets(N, x)
- Return list of two node-lists with unsaturated supply/demand by x.
- xBFlowFeasible(N, x)
- Return true if flow conservation is met in x.
- xBoundFeasible(N, x)
- Return true if 0 <= x <= u.
|