Contents

Graph::residualGraph

Computes the residual graph

Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

Syntax

Graph::residualGraph(G, f, <Extended>)

Description

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.

Examples

Example 1

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.

Example 2

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 substracted 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 existing 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 edges 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.

Parameters

G

Graph

flow

The predefined flow

Options

Extended

Include edges with zero capacities

Return Values

Graph

Was this topic helpful?