## `Network::residualNetwork` -- computes the residual network

#### Introduction

`Network::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`.

#### Call(s)

`Network::residualNetwork(G, f <, Extended>)`

#### Parameters

`G` | - | network
`f` | - | flow

#### Options

`Extended` | - | include edges with zero capacities

#### Returns

A `Network`

#### Details

- `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`.
- If the optional argument `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])

#### Changes

- used to be called `Network::ResidualNetwork`

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000