Network::residualNetwork
-- computes the residual network
IntroductionNetwork::residualNetworkG, 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.
Call(s)Network::residualNetwork(G, f <, Extended>)
ParametersG |
- | network |
f |
- | flow |
OptionsExtended |
- | include edges with zero capacities |
ReturnsA Network
DetailsNetwork::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.
Example
1
>> 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 )
)
Example
2>> 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