Network::residualNetwork
-- computes the residual networkNetwork::residualNetwork
G, f
computes the
residual of the network G
with respect to the flow
f
, i.e., loosely speaking, the network that remains when
the flow f
is ``subtracted'' from G
.
Network::residualNetwork(G, f <, Extended>)
G |
- | network |
f |
- | flow |
Extended |
- | include edges with zero capacities |
A Network
Network::residualNetwork
computes the residual network
with respect to a given flow. A flow in a network is a table
t
, where t[[i,j]]
gives the number of units
flowing from node i
to node j
.Extended
is given, then also
those edges with a zero residual capacity are contained. Otherwise
those edges are omitted.>> N1 := Network::complete(3): N2 := Network::residualNetwork(N1, table( [1, 2] = 1, [2, 1] = 1/2, [1, 3] = 0, [3, 1] = 0.5, [2, 3] = 1, [3, 2] = 0 ) ): Network::eCapacity(N1), Network::eCapacity(N2)
table( [3, 2] = 1, table( [3, 1] = 1, [3, 2] = 1, [2, 3] = 1,, [3, 1] = 0.5, [2, 1] = 1, [2, 1] = 1/2, [1, 3] = 1, [1, 3] = 1 [1, 2] = 1 ) )
>> V := [1,2,3,q,s]: Edge := [[q,1], [1,2], [1,3], [2,3], [3,s]]: up := [5, 4, 4, 2, 5]: N := Network(V,Edge,Capacity=up): flow := table([q, 1]=5,[3, s]=5,[1, 2]=1,[1, 3]=4,[2, 3]=1): N1 := Network::residualNetwork(N, flow): Network::printGraph(N1);
Vertices: [1, 2, 3, q, s] Edges: [[1, 2], [2, 3], [1, q], [2, 1], [3, 1], [3, 2], [s, 3]] Vertex weights: table(s=0,q=0,3=0,2=0,1=0) Edge capacities: table([s, 3]=5,[3, 2]=1,[3, 1]=4,[2, 1]=1,[1,\ q]=5,[2, 3]=1,[1, 2]=3) Edge weights: table([s, 3]=-1,[3, 2]=-1,[3, 1]=-1,[2, 1]=-1,[1\ , q]=-1,[2, 3]=1,[1, 2]=1) Adjacency list (out): table(s=[3],q=[],3=[1, 2],2=[3, 1],1=[2,\ q]) Adjacency list (in): table(s=[],q=[1],3=[2, s],2=[1, 3],1=[2, \ 3])
>> N1 := Network::residualNetwork(N, flow, Extended): Network::printGraph(N1);
Vertices: [1, 2, 3, q, s] Edges: [[q, 1], [1, 2], [1, 3], [2, 3], [3, s], [1, q], [2, 1]\ , [3, 1], [3, 2], [s, 3]] Vertex weights: table(s=0,q=0,3=0,2=0,1=0) Edge capacities: table([s, 3]=5,[3, 2]=1,[3, 1]=4,[2, 1]=1,[1,\ q]=5,[3, s]=0,[2, 3]=1,[1, 3]=0,[1, 2]=3,[q, 1]=0) Edge weights: table([s, 3]=-1,[3, 2]=-1,[3, 1]=-1,[2, 1]=-1,[1\ , q]=-1,[3, s]=1,[2, 3]=1,[1, 3]=1,[1, 2]=1,[q, 1]=1) Adjacency list (out): table(s=[3],q=[1],3=[s, 1, 2],2=[3, 1],1\ =[2, 3, q]) Adjacency list (in): table(s=[3],q=[1],3=[1, 2, s],2=[1, 3],1=\ [q, 2, 3])
Network::ResidualNetwork