Network::convertSSQ
--
converts a network into a single source single sink network
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.
Network::convertSSQ(G, q, s)
q,s |
- | nodes not contained in the network |
G |
- | a network |
the augmented network
Network::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.
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])
Network::ConvertSSQ