Computes the residual graph
This functionality does not run in MATLAB.
Graph::residualGraph(G
, f
, <Extended>)
Graph::residualGraph(G, flow)
computes the
residual of the graph G
with respect to the flow flow
,
meaning the graph that remains when the flow flow
is
"subtracted" from G
.
Graph::residualGraph
computes the residual
graph with respect to a given flow. A flow in a Graph is a table tbl
,
where tbl[[i,j]]
gives the number of units flowing
from vertex i
to vertex j
.
If the optional argument Extended
is given,
then also those edges with a zero residual capacity are considered,
otherwise these edges are omitted.
In the following call, G2
is the graph consisting
of the remaining transport capacities after a given flow:
G1 := Graph::createCompleteGraph(3): G2 := Graph::residualGraph(G1, table( [1, 2] = 1, [2, 1] = 1/2, [1, 3] = 0, [3, 1] = 0.5, [2, 3] = 1, [3, 2] = 0 ) ): Graph::getEdgeWeights(G2)
The algorithm detects the lack of edge weights and edge costs and sets all edge weights and costs to default values of 1.
The resulting graph depends on whether the option Extended
is
used:
V := [1, 2, 3, q, s]: Edge := [[q, 1], [1, 2], [1, 3], [2, 3], [3, s]]: up := [5, 4, 4, 2, 5]: G := Graph(V,Edge,EdgeWeights = up, Directed): flow := table([q, 1] = 5, [3, s] = 5, [1, 2] = 1, [1, 3] = 4, [2, 3] = 1): G1 := Graph::residualGraph(G, flow): Graph::printGraphInformation(G1);
Vertices: [1, 2, 3, q, s] Edges: [[2, 1], [3, 1], [3, 2], [s, 3], [1, q], [1, 2], [2, 3]] Vertex weights: no vertex weights. Edge descriptions: no edge descriptions. Edge weights: [1, 2] = 3, [2, 3] = 1, [2, 1] = 1, [3, 1] = 4, [3, 2] = 1, \ [s, 3] = 5, [1, q] = 5 (other existing edges have no weight) Edge costs: [1, 2] = 1, [2, 3] = 1, [2, 1] = 3, [3, 1] = 0, [3, 2] = 1, \ [s, 3] = 0, [1, q] = 0 (other existing edges have costs zero) Adjacency list (out): 1 = [2, q], 2 = [1, 3], 3 = [1, 2], q = [], s = [3] Adjacency list (in): 1 = [2, 3], 2 = [1, 3], 3 = [2, s], q = [1], s = [] Graph is directed.
Edge Weights contain the residual graph with all the flows. Edge Costs show the flow that was subtracted or added. For example edge [1, 2] had weight 4. After a flow of 3 was sent over it, the residual edge [2, 1] contains the flow of 3 and the residual edge [1, 2] contains the flow of 1. Since the negative flow of the reverted edge plus the flow of the edge in the residual graph have to sum up to the flow it shows that the flow is calculated correctly. ( ( 3) + 1 = 4)
G1 := Graph::residualGraph(G, flow, Extended): Graph::printGraphInformation(G1);
Vertices: [1, 2, 3, q, s] Edges: [[2, 1], [3, 1], [3, 2], [s, 3], [1, q], [1, 2], [1, 3], [2, 3], [3\ , s], [q, 1]] Vertex weights: no vertex weights. Edge descriptions: no edge descriptions. Edge weights: [q, 1] = 5, [1, 2] = 4, [1, 3] = 4, [2, 3] = 2, [3, s] = 5, \ [2, 1] = 4, [3, 1] = 4, [3, 2] = 2, [s, 3] = 5, [1, q] = 5 (other exi\ sting edges have no weight) Edge costs: [1, 2] = 3, [1, 3] = 0, [2, 3] = 1, [3, s] = 0, [q, 1] = 0, [2\ , 1] = 1, [3, 1] = 4, [3, 2] = 1, [s, 3] = 5, [1, q] = 5 (other existing e\ dges have costs zero) Adjacency list (out): 1 = [2, 3, q], 2 = [1, 3], 3 = [1, 2, s], q = [1], s\ = [3] Adjacency list (in): 1 = [2, 3, q], 2 = [1, 3], 3 = [1, 2, s], q = [1], s \ = [3] Graph is directed.

Graph 

The predefined flow 

Include edges with zero capacities 
Graph