Previous Page Next Page Contents

Network::residualNetwork -- computes the residual network

Introduction

Network::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>)

Parameters

G - network
f - flow

Options

Extended - include edges with zero capacities

Returns

A Network

Details

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])

Changes




Do you have questions or comments?


Copyright © SciFace Software GmbH & Co. KG 2000