Network::convertSSQ --
converts a network into a single source single sink network
Introduction augments the
network Network::convertSSQ(G, q, s)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)
Parametersq,s |
- | nodes not contained in the network |
G |
- | a network |
Returnsthe augmented network
DetailsNetwork::convertSSQ(G, q, s) converts the
network G into a single source single sink network. The
specified nodes q and s are added to the
network. It is an error if they are already contained. Otherwise they
are connected to the other nodes of the network in the following way:
A new edge [q,i] is added for every vertex
i with a positive weight. A new edge [i,s] is
added for every vertex i with a negative weight. The
capacities of these edges are in each case the weight of node
i. The edge weights are zero.
Example
1This 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])
Network::ConvertSSQ