netmic.algorithmic_utility

Auxiliary function concerning solutions for flow networks.

 
Modules
       
math
netmic.network_utility
networkx

 
Functions
       
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.