Previous Page Next Page Contents

Network::convertSSQ -- converts a network into a single source single sink network

Introduction

Network::convertSSQ(G, q, s) augments the network G so that q is the single source and s is the single sink of the new network.

Call(s)

Network::convertSSQ(G, q, s)

Parameters

q,s - nodes not contained in the network
G - a network

Returns

the augmented network

Details

Example 1

This is an ugly example. We should make up a better one and explain it.

>> V := [1,2,3,4]:
   Vw := [4,0,0,-4]:
   Ed := [[1,2], [1,3], [2,3], [2,4], [3,4]]:
   Ew := [2,2,1,3,1]:
   Ecap := [4,2,2,3,5]:
   N1 := Network(V,Ed,Vweight=Vw,Capacity=Ecap,Eweight=Ew):
   N2 := Network::convertSSQ(N1,q,s):
   Network::printGraph(N2)
                       Vertices: [1, 2, 3, 4, q, s]
      
      Edges: [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4], [q, 1], [4, s]]
      
              Vertex weights: table(s=-4,q=4,4=0,3=0,2=0,1=0)
      
      Edge capacities: table([4, s]=4,[q, 1]=4,[3, 4]=5,[2, 4]=3,[2,\
       3]=2,[1, 3]=2,[1, 2]=4)
      
      Edge weights: table([4, s]=0,[q, 1]=0,[3, 4]=1,[2, 4]=3,[2, 3]\
      =1,[1, 3]=2,[1, 2]=2)
      
      Adjacency list (out): table(s=[],q=[1],4=[s],3=[4],2=[3, 4],1=\
      [2, 3])
      
      Adjacency list (in): table(s=[4],q=[],4=[2, 3],3=[1, 2],2=[1],\
      1=[q])

Changes




Do you have questions or comments?


Copyright © SciFace Software GmbH & Co. KG 2000