SECURE MESSAGE PASSING IN NETWORKS
by
William G. Trobaugh
B.S.E.E., University of Kentucky, 1968
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements of the degree of
Master of Science
Computer Science
2000
mi
*tVs
This thesis for the Master of Science
degree by
William G. Trobaugh
has been approved
by
7/2?/ QO
Date
Mike Radenkovic
Trobaugh, William George (M.S., Computer Science)
Secure Message Passing in Networks
Thesis directed by Professor Tom Altman
ABSTRACT
In this thesis we discuss message passing methods for computer/control
networks whose architectures can be represented via weighted directed or
undirected graphs.
First, we introduce the concept of network reliability. Second, we present
several algorithms for determining network reliability. Third, we look at an
algorithm for determining network reliability via computation of the max flow in
a network. We give the implementation and address the performance of this
algorithm. We then derive two important (and original) NPCompleteness results
dealing with the construction of biconnected networks. In particular, we show
that the problems of finding a spanning biconnected subgraph of a weighted graph
G = (V,E) of weight equal to integer K, as well as of weight bounded by integers
C and D, are both NPComplete.
This abstract accurately represents the content of the candidates thesis. I
recommend its publication.
Signed
in
Tom Altman
CONTENTS
Figures...................................................................vi
<
Chapter
1. Introduction...........................................................1
1.1 Network flows..........................................................1
1.2 Residual networks.....................................................3
1.3 Augmenting paths......................................................3
1.4 Max flow min cut....................................................4
1.5 The maxflow mincut theorem..........................................5
1.6 Computing max flow with the FordFulkerson method.....................6
1.7 Connectivity in a graph...............................................6
1.8 Internally disjoint paths and vertex connectivity.....................8
1.9 Constructing reliable networks........................................8
1.10 Maxmin duality and Mengers theorem................................10
1.11 Connectivity algorithms.............................................11
1.12 Edge connectivity of a graph........................................12
1.13 Transmitting messages over networks.................................13
2. Literature survey.....................................................16
2.1 Finding biconnected components........................................16
2.1.1 Finding biconnected components in O(n) time for a class of graphs..16
IV
2.2 Network flow and graph connectivity
17
2.3 Disjoint Paths......................................................18
2.3.1 Discussion of the approach to computing disjoint paths...........19
3. Algorithm for computing vertex connectivity from max flow in a network.... 21
3.1 Basic FordFulkerson algorithm....................................21
3.2 A more refined FordFulkerson method..............................22
3.2.1 Labeling of the FordFulkerson algorithm..........................23
4. Two NPComplete problems related to vertex connectivity.............24
4.1 The SUBSET SUM problem............................................24
4.2 Finding a spanning biconnected subgraph (SBS).....................24
4.2.1 Computing SBS of cost K is NPComplete...........................25
4.2.2 Computing SBS of cost between C and D is NPComplete..............26
Appendix................................................................28
References..............................................................46
v
FIGURES
Figure
1.1 A flow network, G=(V,E)..............................................2
1.4 A cut (S,T) in a flow network.........................................4
1.11 S disconnects G as well as v and j...................................12
2.3.1 Example with two nodedisjoint paths................................19
2.3.2 Difference between P2 and PI in Figure 2.3.1........................20
4.2 The graph and SBS corresponding to the Subset Sum instance..........27
vi
1. Introduction
In message passing along communications networks, we desire reliable
transmission of the information from some source to some destination. We
therefore desire that the network over which we transmit the information be
difficult to disrupt. We want to insure that the network service is preserved by
insuring that even in the presence of disruptions, the network remains connected.
In addition, since communications links are expensive, we want to achieve this
goal with as few links as possible.
There is a correlation between the edge or node connectivity of a computer
network and the minimum number of communications links that would still leave
the network connected if removed. We speak of a cut in a graph that is a
partitioning of the vertices of a graph. The maximum number of disjoint node
paths is equal to the minimum number of nodes in any cut of a graph. In addition,
the maximum number of edge disjoint paths between nodes is equal to the edge
connectivity between nodes.
One measure for determining the node and edge connectivity in a graph is
based on Mengers theorem. Mengers theorem introduces a way to determine
the maximum number of internally disjoint paths in a graph or network [1]. We
will look at Mengers theorem later in this thesis.
1.1 Network flows
We define a network as a graph, G=(V,E), in which a flow or transmission
occurs along the edges of the graph. There are distinguished nodes in the network
called the source and the sink. An analogy of a network is a system of pipes
through which a fluid such as oil or water flows. The water would emanate from
a source and would flow through pipes via the nodes or vertices of the network.
We now give a graphtheoretic definition of network flows. We will
discuss the properties of flow networks and define the maximum flow problem
formally. First, a flow network, G=(V,E), is a directed graph in which each edge
(u,v) E E has a nonnegative capacity, c(u,v) > 0. There are two vertices in this
1
network that are distinguished from the rest. These are designated as a source, s,
and a sink, t. Figure 1.1 shows a typical flow network with the capacities labeled
on the edges.
Figure 1.1 A flow network, G=(V,E).
The flow in G is a realvalued function, fVxVtR that satisfies the
following properties [2]:
1. Capacity constraint: For all u, v e V,f(u,v)
2. Skew symmetry: For all u,ve V,f(u,v) = f\v,u)
3. Flow conservation: For all u e V {s,t}, f(u,v) = 0
That is, the flow out of a vertex u e V{s,t} is equal to the flow into
the vertex.
If an edge has a flow capacity of zero, c(u,v)=0, removing the edge from
the network does not alter the flow in the network.
We may interpret the edge weights as limits on the capacities of the edges
to transmit a good of some type (a message, traffic, oil, etc). The determination
of the maximum amount of traffic that can be transmitted between a given pair of
vertices (source and sink) in a network, G=(V,E), is called the max flow problem.
2
1.2 Residual networks
Informally, a residual network consists of edges in a network, G=(V,E)
that can admit more net flow. Formally, let G=(V,E) be a flow network with a
source, s and a sink, t. Let/be a flow in G, and consider a pair of vertices, u, v e
V. The amount of additional net flow that can be pushed from u to v up to the
capacity c(u,v) is the residual capacity of (u,v), or,
c/u,v) = c(u,v) f(u,v).
Thus, given a flow network, G=(V,E), and a flow / the residual network
of G is G/= (V,Ef), where,
E/{ (u,v) e VxV:c/u,v) > 0 }.
1.3 Augmenting paths
Informally, an augmenting path in a flow network, G=(V,E) with a flow,/,
is a simple path from the source, s to the sink, t in the residual network, G/=
(V,Ef). Therefore, each edge (u,v) on an augmenting path can admit additional
positive net flow from u to v and still be under the capacity constraint.
Property 1.3.1
Let G=(V,E) be a flow network,/be a flow in G, and p be an augmenting
path in G/. If we define a function fp: VxV > R by
cf(p) if (u,v)ison p
fp(u,v)= cf(p) if {v,u)isonp
0 otherwise
then, fp is a flow in G/with value \fp\ = cfp)>0.
Property 1.3.2
Let G=(V,E) be a flow network,/be a flow in G, and p be an augmenting
path in G/. Let fp be defined as above. We define a function/: VxV > R by
/=/+/. Then,/ is a flow in G with value l/=[/1+[/p > \f\
3
1.4 Max flow min cut
We may define a cut, (S,T), of a flow network, G=(V,E), as a partition of
Vinto 5 and T=VS, such that s e S and t e T. If/is a flow, then the net flow
across the cut (S,T) is defined to be f(S,T). The capacity of the cut (S,T) is c(S,T).
Figure 1.4 shows a typical cut in a flow network. The dashed line shows the
partition, S,T of the cut.
Figure 1.4 A cut (S,T) in a flow network.
In this cut, S = fs, vy, V2J, and T = ft, vy, V4}. The flow and capacities for
each edge are labeled as x/y, where x is the flow and y is the capacity. For
example, the flow across edge (Vy, vy) is 12. The net flow across (S,T) is
f(S,T)\9, and the capacity is c(S,T)=26. A minimum cut of a network is a cut
with the minimum capacity.
We will need the following identities to demonstrate some of the
properties of network flow [3]:
Properties 1.4.1
Let G=(V,E) be a flow network, and let/be a flow in G. Then, forX c V,
1. f(X,X)=0
ForX, YcV,
2. f(X,Y)=f(Y,X)
ForX, Y,Z (i V with XnY = 0,
3. f(X uY,Z)=f(X,Z) +f(Y, Z)
and,
4. f(Z,XuY)=f(Z,X)+f(Z,Y)
4
Lemma 1.4.1
Let/be a flow in a network G=(V,E) with source, s and sink, f, and let
(S,T) be a cut of G. Then, the flow across (S,T) is f(S,T)=\f\.
Proof (using Properties 1.4.1)
f(S,T) =f(S,V)f(S,S)
= f(S,V)
=f(s,V) +f(Ss, V)
=f(s,V)
= i/i
Corollary 1.4.1
The value of any flow,/in a network, G=(V,E) is bounded above by the
capacity of any cut of G.
Proof
Let (S,T) be any cut of G and let/be any flow. By Lemma 1.4.1 and
capacity constraints,
1/1 =fiS,T)
= X. Xr/<'v>
X.rc<'v>
= c(S,T).
1.5 The maxflow mincut theorem
In the max flow problem, we are seeking to maximize the total flow from
a source to a sink. This problem also applies to networks with multiple sources
and sinks. We simply convert this problem to one with a single source, s and a
single sink, t with edges having infinite capacity [4].
Maxflow min cut theorem
In every network, the maximum value of a feasible flow equals the
minimum capacity of a source/sink cut.
(For a proof, see [4]).
In addition, the following conditions are equivalent:
1. /is a maximum flow in G.
5
2. The residua] network, G/contains no augmenting paths.
3. [/] = c(S,T) for some cut (S,T) of G.
1.6 Computing maximum flow with
the FordFulkerson method
The FordFulkerson method is iterative. Starting with zero flow, the
method is applied repeatedly until the maximum flow of the network is obtained.
Once the initial flow is set to zero, the method iterates by increasing the flow
along augmenting paths. The iteration stops once there are no longer any
augmenting paths. We will look into this method in more detail in Chapter 3.
1.7 Connectivity in a graph
We have two parameters for measuring the connectedness in a graph,
G=(V,E). These are vertexconnectivity which we shall denote as VC(G), and
edge connectivity, which we shall denote as EC(G). We define the following to
elucidate our understanding of the connectivity of a graph [5]:
Definition 1.7.1
A vertex cut in a graph, G is a vertex set, U such that GU has more
components than G.
Definition 1.7.2
A cut vertex (or cutpoint) is a vertex cut consisting of a single vertex.
Definition 1.7.3
An edge cut in a graph, G is a set of edges, D such that GD has more
components than G.
Definition 1.7.4
A cut edge (or bridge) is an edge cut consisting of a single edge.
Definition 1.7.5
The vertex connectivity of a connected graph G (denoted VC(G)) is the
minimum number of vertices whose removal can either disconnect G or reduce it
to a 1vertex graph.
6
Definition 1.7.6
A graph, G is kconnected if G is connected and VC(G)>k. If G has non
adjacent vertices, then G is kconnected if every vertex cut has at least k vertices.
Definition 1.7.7
The edge connectivity of a graph, G (denoted EC(G)) is the minimum
number of edges whose removal can disconnect G.
Definition 1.7.8
A graph is kedge connected if G is connected and every edge cut has at
least k edges; that is, EC(G)>k.
We speak of the connectivities, VC(G) and EC(G), as the measures for
determining network survivability, which is the capacity of a network to retain
connections among its nodes after some edges or nodes have been removed. It is
these measures that determine the diversity of routing in the graph, that is, the
number of node or edge disjoint paths between pairs of vertices [6].
If u and v are nonadjacent vertices in G, we define a vertexdisconnecting
set (or vertex separator) between u and v in G as a set of vertices S in V(G) such
that u and v are in different components of GS. S is said to disconnect (or
separate) the pair of vertices u and v. An edgedisconnecting set between a pair of
vertices and u and v in G is similarly defined as a set of edges T in E(G) such that
u and v are in different components of GT for nonadjacent vertices u and v.
In a survivable network, it is more important that we consider the vertex
connectivity than the edge connectivity. For example, considering the vertices of
a network as computer stations and the edges as the links between stations, it is
more critical that we determine the vertex connectivity, since for any G, VC(G) <
EC(G). Now, how can we determine the vertex connectivity in a graph? One
method is to compute the maximum network flow,/over all pairs of vertices u, v
eV(G) (where u represents the source and v represents the sink) then take the
minimum of these flows. While computing the maximum flows,/we assign a
weight value of 1 to each edge (u,v) e E(G).
7
1.8 Internally disjoint paths
and vertex connectivity
We say that a communications network is fault tolerant if it has at least
two different nodedisjoint paths between each pair of vertices. Now, this
precisely describes a biconnected graph. In other words, the removal of any
vertex in a connected graph will still leave the graph connected. Whitneys
theorem addresses the issue of biconnectivity which we state shortly. First, we
say a vertex of a path, P, is an internal vertex of P if it is neither the source nor
the terminal vertex of that path.
Definition 1.8.1
Let u and v be two vertices in a graph, G. A set of uv paths in G is said to
be internally disjoint if no two paths in the set have an internal vertex in common.
Theorem 1.8.1 [Whitney, 1932]
Let G be a connected graph with three or more vertices. Then G is 2
connected (biconnected) if and only if for each pair of vertices in G, there are two
internally disjoint paths between them. (See [7] for a proof).
The following conditions are equivalent with respect to biconnected graphs:
1. The graph, G, is biconnected.
2. For any two vertices of G, there is a cycle containing both.
3. For any vertex and any edge of G, there is a cycle containing both.
4. For any two edges of G, there is a cycle containing both.
5. For any two vertices and one edge of G, there is a path containing all
three.
6. For any three distinct vertices of G, there is a path containing all three.
7. For any three distinct vertices of G, there is a path containing any two of
them which does not contain the third.
1.9 Constructing reliable networks
Various methods exist for the construction of graphs with a specified
vertex connectivity. These constructions are the basis for reliable networks. We
have,
Whitneys synthesis of 2connected graphs.
Tuttles synthesis of 3connected graphs.
Hararys construction of an optimal ^connected graph.
8
Whitney gives a method for synthesizing biconnected graphs. His method
is based on a series of path additions.
Definition 1.9.1
A path addition to a graph, G is the addition to G of a path between two
existing vertices of G, such that edges and internal vertices of the path are not in
G.
Definition 1.9.2
A Whitney synthesis of a graph G from a graph H is a sequence of graphs,
Go, G], ...,Gi, where Go=H, G/=G and G, is the result of a path addition to G,./, for
i=l,...,/.
Lemma 1.9.1
Let H be a biconnected graph. The graph G that results from a path
addition to H is biconnected.
Lemma 1.9.2
Let H be a subgraph of a biconnected graph G, and let e be any edge in the
graph GEh. Then there is a path addition to H that includes edge e.
Theorem 1.9.1 [Whitney, 1932]
A graph, G is biconnected if and only if G is a cycle or a Whitney
synthesis from a cycle (See [7], page 182 for a proof)
Harary gives a procedure for constructing ^connected graphs [8]. The
following is his algorithm for this construction.
Constructing an optimal kconnected nvertex graph
Input: positive integers k and n with k < n
Output: the Harary graph, Hk,n with the standard 0based labeling
Initialize graph H to be n isolated vertices labeled 0, ....,
Let rim]
for i=0 to n2
for ji+l to n1
if ji
Create an edge between vertices i and j
II This completes construction of H2r,n
if k is even
return graph H
9
else
if n is even
for i=0 to n/2 1
Create an edge between vertex i and vertex (i+n/2)
else
Create an edge from vertex 0 to vertex (nl)/2
Create an edge from vertex 0 to vertex (n+l)/2
for i=l to (n3)/2
Create an edge between vertex i and vertex (i +(n+l)/2)
return graph H
1.10 Maxmin duality and Mengers theorem
The basis for Mengers theorem is that there is a strong duality between
two optimization problems in graph theory. These are:
Maximization problem: Determine the maximum number of internally disjoint u
v paths in graph G.
Minimization problem: Determine the minimum number of vertices of graph G
needed to separate the vertices u and v.
Definition 1.10.1
Let u and v be distinct vertices in a connected graph, G. A vertex subset
(or edge subset) 5 is uv separating if the vertices u and v lie in different
components of the deletion subgraph, GS.
Proposition 1.10.1 (weak duality)
Let u and v be any two nonadjacent vertices of a connected graph, G. Let
Puv be a collection of internally disjoint uv paths in G, and let Suv be a uv
separating set of vertices in G. Then, PUV <  Suv\.
Proposition 1.10.2
Let h and v be any two nonadjacent vertices of a connected graph G.
Then the maximum number of internally disjoint uv paths in G is less than or
equivalent to the minimum size of a uv separating set of vertices in G.
Mengers theorem states that the maximization and minimization problems
are in fact equivalent. There are many variations of this theorem with respect to
10
maxmin duality for graphs and networks. In fact, Whitneys theorem given
previously is a variation of Mengers Theorem.
Theorem 1.10.1 (Menger, 1927)
Let u and v be distinct, nonadjacent vertices in a connected graph, G.
Then, the maximum number of internally disjoint uv paths in G equals the
minimum number of vertices needed to separate u and v.
1.11 Connectivity algorithms
We can compute the vertex connectivity, VC(G) of a graph by computing
the maximum network flow problem. We will look at the FordFulkerson method
for computing the max network flow in order to compute vertex connectivity.
Here is an outline of another procedure to compute vertex connectivity, VC(G).
Function VC (G)
(Returns in VC the Vertex connectivity of G)
Var G: Graph
i,j: 1..V(G)
VC: integer function
set VCtoV(G)[l
if G is complete then return
for i=l to V (G) do
for 7 = i + 1 to V (G)  do
if i and j not adjacent
then set VC to min {VC, VC (G, i, j)}
If i > VC then return
End_Function_VC
Theorem 1.11.1
Function VC(G) correctly determines the vertex connectivity of a graph.
Proof
If G is complete, the procedure is trivially correct. Otherwise, if G is not
complete, the first calculation of VC(G,i,j) with i and j not adjacent already forces
VC to be at most V2. Therefore, the procedure must terminate with an explicit
return at least by the time the outer loop is executed with i= V)1. Consequently,
upon termination,
VC < i.
11
Since VC(G) is the minimum of the nonadjacent pairwise connectivities,
VC is always at least as large as VC(G); therefore,
VC(G) + 1 < VC + 1 < i.
Since VC(G) is the cardinality of a minimum cardinality vertex
disconnecting set S for G and since i exceeds VC on termination, at least one
vertex7 in 1....i cannot lie in S. Since j is not in S,j is separated from some other
vertex v by the disconnecting set S (refer to figure 1.11). Necessarily, VC(G,j,v) <
S. Since S is a disconnecting set of minimum cardinality, VC(G,j,v) must equal
S, that is, VC(G). Therefore, VC will receive its correct value when the
algorithm calculates VC(G,j,v).
Figure 1.11 S disconnects G as well as v and j.
1.12 Edge Connectivity of a Graph
The algorithm shown below finds the edgeconnectivity EC{G) of an
undirected graph G. EC(G) denotes the edgeconnectivity of an arbitrary graph G
= (V,E), and G denotes the digraph obtained by replacing each edge of G by two
antiparallel edges, each of unit capacity. The algorithm finds the value of a
maximum flow F for the network consisting of G with a source x and a sink y.
The running time of this algorithm is Oin  E ).
12
Algorithm:
Input G and construct G
Specify u
EC
for all v e V {} do
begin
find F for (G with x = u and y = v)
if F < EC then EC
end
Output K.
But, since we intend to concentrate our efforts on vertex connectivity, no
further discussion of this algorithm is needed. For more details, see [25].
1.13 Transmitting messages over networks
In this thesis, we express a network by a graph, where a node can be a
processor or relay station, and an edge is a communication link. If two nodes are
connected by an edge, they are called adjacent. If every pair of nodes in a
network is connected by an edge, the network is said to be a complete network.
Otherwise, it is called an incomplete network or a general network.
Broadcasting is a process of disseminating a message from a source node
to all other nodes. Since not every pair of nodes has a link connecting them,
broadcasting can be achieved in the way that each node repeatedly receives and
forwards the messages. When only one node has a message to disseminate, it is
called onetoall broadcasting.
If every node has a message to disseminate to all other nodes, it is called
alltoall broadcasting. For broadcasting, no secrecy is required. That is, we need
not keep the message secret from any node. The only matter of concern is
correctness, i.e., every good node should correctly receive the message broadcast
by the source node before the broadcasting is finished. For alltoall broadcasting,
we require that every good node can correctly receive the messages broadcast by
good nodes. The goal of alltoall broadcasting can be formalized as follows:
Let pi, p2,......p be all the processors (nodes) of the network. Denote
m[i] the message broadcast by p, and nij [/] the message received by pj from p,, for
i,j =1,2,....., n. The broadcasting is said to be successful if m[i] = mj [i] for
every pair of i and j such that p, and pj are good processors [9].
13
We always assume that the source node of broadcasting is good and
honest. That is, the source node always sends a correct message to its neighbors
(adjacent nodes). However, it is sometimes possible that the source node itself is
faulty, while in this situation all other nodes must agree on some value as to what
the source node broadcasts. This problem is called Byzantine agreement. Hence,
the difference between faulttolerant broadcasting and Byzantine agreement can
be stated like this: Faulttolerant broadcasting always has a good source while in
Byzantine agreement broadcasting, there may be a faulty source. We formalize
the goal of Byzantine agreement as follows:
Let pi,p2,........Pn be all nodes of the network. Suppose that pj is a
source node and has a message m to send to all other /?, s. At the end of the
execution of a Byzantine agreement protocol, every pi decides a message m,. We
require that mi = my for every pair of i and j such that pt and pj are good
processors. Furthermore, if pi is good, mj=m for all the good p,s.
Byzantine agreement is one of the most important tasks in distributed
systems. By applying Byzantine agreement protocols, we perform as if there
exists a broadcasting channel while there actually is not. The Byzantine
agreement problem has been thoroughly studied. Many protocols for Byzantine
agreement have been proposed. Although Byzantine agreement is usually studied
on complete networks, it can be implemented for general networks. The most
basic operation used in Byzantine agreement protocols is faulttolerant
broadcasting: the message broadcast by good nodes can be correctly received by
all other good nodes. For example, the simplest protocol for Byzantine
agreement, EIG (exponential information gathering) just exploits t + 1 rounds of
alltoall broadcasting. Hence, the study on how to raise the efficiency and
reliability of broadcasting helps to raise the efficiency of realizing Byzantine
agreement in general networks.
Only reliability is concerned in the study of broadcasting, whereas both
correctness and secrecy are concerned in secure message transmission. In a
secure message transmission setting, one node (processor), called a sender, has a
secret message 5 to send to another node, called a receiver. We require that the
receiver can correctly obtain the message s whereas all other nodes obtain nothing
about s. We always assume that all the good nodes execute the protocol honestly.
We also assume that every node knows the topology of the underlying network in
advance and that the network is synchronized by a global clock. Thus, all the
processors can implement one step of a protocol concurrently in a specified time
unit.
14
The basic idea of secure message transmission is to exploit disjoint paths
between a sender and a receiver. When the distance between a sender and a
receiver is large, the transmitted messages could possibly suffer from both
corruption and leakage.
15
2. Literature Survey
A survey of the literature was conducted to discover various approaches
for reliable information passing in networks. Message passing algorithms
basically translate into algorithms for determining the vertex connectivity of a
network, which is a measure of network reliability. We now look at some of the
literature available on determining the vertex connectivity or nodal disjoint paths
in networks and graphs. We will also see how we can determine graph
connectivity by computing the max flow in a network.
2.1 Finding biconnected components
We say that a connected, undirected graph, G(V,E), is biconnected if there
are no vertices whose removal disconnects the rest of the graph [11]. According
to Whitney (1932), an undirected graph G, having at least three vertices, is
biconnected if and only if each pair of edges, u,v e V(G), is connected by a pair of
intemallydisjoint u,v paths in G [12]. The problem of finding biconnected
components was investigated by Y. Liang and Rhee [13].
2.1.1 Finding biconnected components in
O(n) time for a class of graphs [11]
A rooted tree is called a single branch tree if there is exactly one nonleaf
vertex on each level except the bottom level of three. This paper discusses an
0{ri) time algorithm for finding biconnected components in a graph G, assuming
that a single branch breadthfirst search tree of any connected induced subgraph
of G can be found in 0(n) time. It is shown that such trees can be found for the
interval graphs and the permutation graphs in 0(n) time. Hence, the biconnected
components in these graphs can be obtained in O(n) time, while finding
biconnected components in a general graph of n vertices and m edges takes
O(m+ri) time.
An undirected graph G = (V,E) is connected if there is a path between
every pair of vertices in the graph. A connected component (CC) of G is a
16
maximal connected subgraph of G. A graph is called biconnected if for any two
vertices, there exist two vertex disjoint paths connecting them. A biconnected
component (BC) of G is a maximal biconnected subgraph of G. The problem of
developing efficient algorithms for finding BCs of undirected graphs has received
considerable attention in the literature owing to its applicability to many other
graph problems. Recently, Hochbaum [13] showed that for several graph
optimization problems, including the weighted vertex cover and independent set
problems, it suffices to know how to solve the problems on each biconnected
component of the graph. The additional work required to obtain a solution for the
whole graph can be done in O(m+ri) time.
We let T be a spanning tree of a connected graph, G = (V,E) rooted at an
arbitrary vertex. Then T is called a breadthfirst search (BFS) tree if for each edge
e e E, the difference of the levels of the two vertices incident with e is no more
than 1, where the level of a vertex in T is the distance from the root to the vertex.
It is wellknown that the problem of finding a BFS tree can be solved in 0(n+m)
time for a general graph. A tree is called a singlebranch breadthfirst tree if at
most one nonleaf vertex exists on each level. The paper shows that biconnected
components can be found in O(n) time by exploring the structural properties of
these trees of G.
2.2 Network flow and graph connectivity
Basically, the determination of vertex connectivity or disjoint node paths
in a network reduces to the problem of finding the max flow in the network.
There are wellknown algorithms for determining the max flow. In a paper by S.
Even and E. Tarjan [14], the results of computing network flow are used to test
the vertex connectivity of a graph in 0(Vj1/2 \E\2) time. The algorithm used to
compute the max flow is by Dinic [15], The algorithm requires 0(\Vf73 IE])
assuming that the vertex capacities are all equal to one. In an undirected graph,
G=(V,E) with no selfloops, let the maximum flow be equal to N(a,b), where a set
of vertices, S is called an (a,b) vertex separator if {a,b} c VS and every path
connecting a and b passes through at least one vertex of S. By Dinic, the max
flow is computed in at most 0(\V\1/2 \E\) steps. We let the vertex connectivity be
denoted by c, and define it as follows:
(i) If graph G is completely connected, then c=Vl
(ii) If G is not completely connected, then c=mina,bN(a,b).
17
If G is not completely connected, then the min value of P(a,b) where
P(a,b) is the max number of vertexdisjoint paths connecting a and b, will be
equal to minaibN(a,b). Then, to find c, we compute N(a,b) for all pairs, a,b which
are not connected by an edge. This requires at most 0(j V2) computations and
each requires at most 0(j V\1/2 Â£j) steps. So, there are at most 0(jVj2'5 \E\) steps
to compute c. The paper then goes on to show that this can be improved to the
bounds stated earlier.
2.3 Disjoint Paths
Smith [16] discusses the reliability of transmission in networks based on
the node disjoint paths in the networks. Links between two given nodes of a
network are called diversified if they are nodedisjoint, except at the source and
destination. Diversified links are required for reliability in communication, and
an additional criterion is that their total cost, assumed to be the sum of individual
arc lengths or costs is minimum. An algorithm and related theory is discussed for
a general number k of nodedisjoint paths with minimum total cost. The
algorithm applies shortest path with minimum total cost. The algorithm applies
shortest path labeling algorithms familiar in the literature, k nodedisjoint paths
are found in k iterations of a single shortest path algorithm.
Nodedisjoint paths are used in communication networks for reliability of
transmission between a given source and sink. An objective is to find a given
number k of these paths, with minimum total length subject to nodedisjointness.
Here a labeling algorithm involving k shortest path iterations is described for the
problem. Where the nodedisjoint requirement is relaxed to arcdisjointness, the
same algorithm with a minor change applies.
There is little specific attention devoted to these and related problems in
the literature. In an application where network survivability is related to the
maximum number of nodedisjoint paths, Frisch [17] and later Steiglitz and Bruno
[18] give algorithms for nodedisjoint paths, not involving the secondary
requirement for minimum total length. Takamori [19] treats the problem of
finding two arcdisjoint paths with maximum total capacity.
The shortage of specific treatment in the literature is perhaps due to the
possibility of representing a node (or arc) disjoint problem as a minimum cost
flow problem: To represent nodedisjointness, for example, each node of the
original, uncapacitated network is replaced by two nodes and a connecting arc of
unit capacity, the device originating in Smith [16], and used in Ford [19] to
specialize a maximal flow algorithm for the maximal number of nodedisjoint
18
paths. Similarly, k disjoint paths of minimum total length can be found by
adapting the minimal cost flow algorithm.
Here, the special nature of the problem is also used, and paththeoretic
possibilities are emphasized. On the computational side, Jc disjoint paths are
found inductively from optimal solutions for 1, 2,..., (Â£1), disjoint paths, using
the shortest path algorithm at each step.
A shortest path algorithm valid for negative arc costs is sufficient in the
above iterative scheme. But in one approach of Smith [16], the network is
transformed at each step to get equivalent nonnegative arc costs, making a non
negative algorithm sufficient. This is the same idea considered recently in
Edmonds and Karp [20], where it is shown that for minimum cost flow problems
in general, iterative cost revisions and nonnegative arc costs for flow
augmentations yield theoretical improvements in labeling operations. For disjoint
paths in sparse average case networks, however, there may be a computational
advantage in a general shortest path algorithm such as Fords [21] over a non
negative shortest path algorithm such as Dijkstras [21], as some experience
indicates [22].
2.3.1 Discussion of the approach to computing disjoint paths
The basic idea for computing nodedisjoint paths is illustrated in Figure
2.3.1, where the shortest path is P] = {abcz}, and the optimal pair of nodedisjoint
paths is P2 = {abz, acz). Representing the logical difference P2 Pi with + on
arcs of P2 on arcs of Pi and cancellation of signs on arcs common to both, the
difference turns out to be an a to z path with + and labels (see Figure 2.3.2).
Length interpretation for the path of Figure 2.3.2 is (total length of arcs labeled +)
 (total length of arcs labeled ), representing the cost difference between P2 and
Pi solutions.
Figure 2.3.1 Example with two nodedisjoint paths.
19
Figure 2.3.2 Difference between P2 and Pi in Figure 2.3.1.
In general, the logical difference P2 0 Pi is more complicated, possibly
including cycles, but the difference always includes an a to z path with + and 
labels. Path difference is analogous to the idea of alternating paths in
transportation and matching algorithms, and is exactly the idea of flow
augmenting paths in maximum flow problems. Alternating paths in programming
literature have arcs labeled in strict + and alternation, while this need not be the
case for the path difference; to maintain the slight distinction, paths (cycles) in the
path difference are here called signed paths (signed cycles)*.
As suggested in Figure 2.3.1 and Figure 2.3.2, one proceeds from a
shortest path to an optimal nodedisjoint pair using a signed path, whose length is
the transition in cost and is as small as possible. Therefore, given a shortest path
Pi, a greedy labeling procedure produces a shortest signed path and an optimal
pair of nodedisjoint paths P2, and continuing inductively, given an optimal set of
(Â£1) nodedisjoint paths, a greedy labeling procedure produces an optimal set of k
nodedisjoint paths.
* Called this after the term signed graphs' used for general graphs with arcs labeled + or
20
3. Algorithm for computing vertex connectivity
from max flow in a network
We may compute the vertex connectivity of a network by converting it to
a max flow problem. This can be done by computing max flow for all n choose 2
pairs of vertices in the network. Each pair is considered as a source, s and a sink,
t. The algorithm to compute max flow is of order 0( V \E\2). We then can
compute the n choose 2 max flows in 0(Vj5 \E2\).
We define a network as a weighted, directed graph with two notable
vertices called source, s and sink, t. The source has no edges coming to it, and the
sink has no edges leaving from it. The weights on the edges are assumed to be
nonnegative and represent the flow capacities of the edges. We now describe a
flow as a set of weights on the edges such that the flow on each edge is equal to or
less than the capacity. By conservation, the flow into a vertex is equal to the flow
out of it. The value of the flow is flow out of the sink (or into the source). The
network flow problem addresses the issue of finding a flow with the maximum
value for a given network.
The algorithm implemented in this thesis (see Appendix) for computing
max flow is based on the FordFulkerson method. This is summarized in the next
section.
3.1 Basic FordFulkerson algorithm
Start with a flow,/(,v)=0, for all n,v e V(G). This gives an initial flow of
0 for the network. Now, iterate by increasing the flow value via an augmenting
path. An augmenting path can be thought of as a path from the source, s to the
sink, t along which we can push more flow, and then increasing the flow along
this path. This process is repeated until no augmenting path can be found. Upon
termination, according to the maxflow, mincut theorem, this method produces a
max flow for the network. Here is the basic method in pseudocode [23]:
21
FordFulkersonMethod(G, s, t)
1. Initialize the flow to 0
2. while there exists an augmenting path p
do augment flow /along p
3. return/
The actual algorithm that is implemented is based on a labeling scheme in
which each edge is progressively labeled according to its flow and capacity. The
basic pseudocode for doing this is in the next section.
3.2 A more refined FordFulkerson method
FordFulkerson(network with source s and sink t)
set flow of all edges and vertices to 0;
label (s) = (null,);
labeled= {s}; // labeled is a queue
while labeled is not empty
detach a vertex, v from labeled;
for all unlabeled vertices u adjacent to v;
if forward(edge(vw) and slack(edge(vn))>0
label(w) =
(v+,min(slack(v),slack(edge(vM))));
else if backward(edge(vn)) and/(edge(wv))>0
label(w)=(v',min(slack(v),/(edge(wv))));
if u got labeled
if ut
Augmentpath(network)
labeled={^}
else
include u in labeled;
Augmentpath(network with source, s and sink, t)
for each edge, e in the path from s to t
if forward(e)
fie) += slack(r);
else
f{e) = slack(r);
22
3.2.1 Labeling of the FordFulkerson algorithm
The previous algorithm computes the maximum flow by augmenting the
flow along each path from the source, s to the sink, t in the graph, G=(V,E) such
that/(e) < c(e) on forward edges, and f(e)>0 on backward edges. This is done
until there is no more augmenting paths, in which case f(e)=0 on backward edges.
The algorithm goes through a phase in which each vertex, v is assigned a
label which is the pair,
label(v) = (parent(v),slack(v)),
where parent(v) is the vertex from which v is being accessed and slack(v) is the
amount of flow that can be transferred from s to v. The forward and backward
edges are treated differently. If a vertex u is accessed from v through a forward
edge, then,
label( u) =(v+, min( slack( v), slackf edge( vu)))),
where
slack( edge( vu))=cap( edge( vu)) f( edg( vu)),
which is the difference between the capacity of edge(vu) and the amount of flow
currently carried by this edge. If the edge from v to u is backward (i.e,. flow from
u to v), then,
label(u) = (v'.min (slack(v),f(edge(uv)))).
After a vertex is labeled, it is stored for later processing. In this process,
only this edge(vu) is labeled which allows for some more flow to be added, which
for forward edges is possible, when slack(edge(vu))>0 and for backward edges,
when f(edge(uv))>0. However, finding one such path may not finish the entire
process. The process is finished if we are stuck in the middle of the network,
unable to label any more edges. If we reach the sink, t, the flows of the edges on
the augmenting path that was just found are updated by increasing flows of
forward edges and decreasing flows of backward edges, and the process restarts,
looking for another augmenting path.
23
4. Two NPComplete problems
related to vertex connectivity
In this chapter we present two computational complexity results
addressing problems in network design and construction. Specifically, we will
show that finding a spanning biconnected subgraph G, whose cost is restricted via
an equality constraint or via upper and lower bounds, is NPComplete. This result
has significant implications in that it justifies the use of heuristic or approximation
algorithms to address the above mentioned problems.
First, let us formally define the SUBSET SUM problem. This problem is
NPComplete and it is closely related to one of the original six basic NP
Complete problems identified by Karp in [24], the SET PARTITION problem.
4.1 The SUBSET SUM problem
INSTANCE: Set A = {ai, 2, ..., an} of positive integers and a positive integer K.
QUESTION: Is there a subset of A, say A, such that the sum of the element
values in A is exactly K1
4.2 Finding a spanning biconnected subgraph (SBS)
Let G = (V,E) be a weighted graph, with each edge having a nonnegative
integer weight, and K be a positive integer. The SBS problem is defined as
finding a subgraph of edges of G such that it remains biconnected, and the
summation of the edge weights is equal to K.
24
4.2.1 Computing SBS of cost K is PComplete
Theorem 4.1
Given G and K, the problem of determining if G has a spanning
biconnected subgraph (SBS) of weight equal to K is NPComplete.
Proof:
We can nondeterministically guess an SBS and verify in deterministic
linear time if its weight is equal to K, as well as in quadratic time (n DFS
traversals) if the removal of any node still leaves the subgraph connected. Hence
the problem is clearly in NP.
Let us take an instance of the SUBSET SUM problem A = {aj, a.2, ..., a),
and integer K. We shall construct a graph G that will have a spanning
biconnected subgraph of weight K if and only if the SUBSET SUM problem has
A c A of weight K. For each a, in A construct a pair of nodes w, and v, and
connect them with an edge of weight a,. Next, construct a node w, and connect it
to Ui and v, with two zeroweight edges.
Finally, connect each node v, to ui+i with a zeroweight edge. Note that
node v will be connected to node uj. The resulting graph is shown in Figure 4.2.
Now, if A has a subset A of weight K, then G has a SBS of the same
weight by simply choosing those nonzero weight edges v,) that correspond to
each a, in A. All of the remaining (zero weight) edges of G would, of course,
still be needed to make the subgraph biconnected. Conversely, if G has a SBS of
weight K, then A of the same weight obviously exists.
25
4.2.2 Computing SBS of cost between
C and D is NPComplete
Theorem 4.2.2
Given a weighted graph G and two positive integers C and D, the problem
of determining if G has a spanning biconnected subgraph of weight bounded by C
and D is NPComplete.
Proof:
Follows directly from Theorem 4.1 with C = D = K.
26
A { flj, fl2j }
Figure 4.2 The graph and SBS corresponding to the SUBSET SUM instance.
27
Appendix
Code to compute max flow in a network using a FordFulkerson method
jjgenBSTree h
// generic binary search tree
#ifndef BINARY_SEARCH_TREE
#define BINARY SEARCH TREE
#include "genLstSt.h"
#include "genQueue.h"
template
struct TreeNode {
genType key;
TreeNode *left, *right;
TreeNode() { left = right = 0; }
TreeNode(const genType& el, TreeNode *1=0, TreeNode *r
0)
{ key = el; left = 1; right = r; }
};
templatecclass genType>
class BinarySearchTree {
public:
BinarySearchTree() { root = 0; }
Clear() { Clear(root); root =0; }
BinarySearchTree() { Clear(); }
int IsEmptyO { return root == 0; }
void SideViewO { SideView(root, 0) ; }
void Preorder() { Preorder(root); }
void Inorder() { Inorder(root); }
void PostorderO { Postorder (root) ; }
void Insert(genType&);
void Reclnsert(genTypek el) { Reclnsert(root,el);
}
TreeNode* Search(genType& el) { return
Search(root,el); }
genType* IslnTree(genType& el) { return &Search(el)
>key; }
TreeNode* Search2(genType& el) { return
Search(root,el); }
28
void DeleteByCopying(TreeNode*&);
void FindAndDeleteByCopying(genTypek);
void DeleteByMerging(TreeNode*&) ;
void FindAndDeleteByMerging(genType&);
void IterativePreorder();
void Iterativelnorder();
void IterativePostorder();
void BreadthFirst();
void Morrislnorder() ;
void Balance (genType*,int,int);
protected:
TreeNode* root;
Queue*> queue;
SLLStack*> travStack, output;
void Clear(TreeNode*);
void SideView(TreeNode*,int);
void Reclnsert(TreeNode*&, genType&);
TreeNode* Search(TreeNode*, genType&);
TreeNode* Search2(TreeNode*, genType&);
void Preorder(TreeNode*);
void Inorder(TreeNode*);
void Postorder(TreeNode*);
virtual void Visit(TreeNode* p) { cout << p>key <<
} ;
template
void
BinarySearchTree::Clear(TreeNode *p)
{
if (P) {
Clear(p>left);
Clear(p>right);
delete p;
}
}
template
void
BinarySearchTree::SideView(TreeNode *p, int
depth)
{
if (P) {
SideView(p>right,depth+1) ;
register int i;
for (i = 1; i <= depth; i++) {
cout << " ";
}
cout << p>key << endl;
SideView(p>left,depth+1);
29
}
}
templatecclass genType>
void
BinarySearchTree::Insert(genType& el)
{ TreeNode *p = root, *prev = 0;
while (p) { // find a place for inserting new node;
prev = p;
if (p>key < el)
p = p>right;
else p = p>left;
}
if (root == 0) // tree is empty;
root = new TreeNode(el);
else if (prev>key < el)
prev>right = new TreeNode(el);
else prev>left = new TreeNodecgenType>(el);
}
template
void
BinarySearchTree::RecInsert(TreeNode*& p,
genType& el)
{
if (p == 0)
p = new TreeNode(el);
else if (el < p>key)
Reclnsert(p>left, el);
else Reclnsert(p>right,el);
}
templatecclass genType>
TreeNode*
BinarySearchTree::Search(TreeNode* p, genTypeS:
el)
{
while (p)
if (el == p>key)
return p;
else if (el < p>key)
p = p>left;
else p = p>right;
return 0;
}
templatecclass genType>
TreeNode*
30
BinarySearchTree::Search2(TreeNode* p, genTypefc
el)
{
if (p)
if (el == p>key)
return p;
else if (el < p>key)
return Search2(p>left,el);
else return Search2(p>right,el);
else return 0;
}
template
void
BinarySearchTree::Inorder(TreeNode *p)
{
if (P) {
Inorder(p>left) ;
Visit(p);
Inorder(p>right);
}
}
template
void
BinarySearchTree::Preorder(TreeNode *p)
{
if (P) {
Visit(p);
Preorder(p>left);
Preorder(p>right);
}
}
template
void
BinarySearchTree::Postorder(TreeNode* p)
{
if (P) {
Postorder(p>left) ;
Postorder(p>right);
Visit(p);
}
}
// the procedure DeleteByCopying() removes node;
templatecclass genType>
void
31
BinarySearchTree::Del
node)
{ TreeNode *prev,
if (!node>right)
for node;
node = node>left;
else if (!node>left)
node = node>right;
else {
tmp = node>left;
prev = node ;
while (tmp>right) {
prev = tmp;
tmp = tmp>right;
}
node>key = tmp>key,
if (prev == node)
prev>left = tmp
else prev>right = tmp
}
delete tmp;
}
teByCopying(TreeNode*&
tmp = node;
// there is no right child
//no left child for node;
// node has both children;
// 1.
// 2.
// 3.
>left; // 4.
>left; // 5.
// FindAndDeleteByCopying() searches the tree to locate the node
containing
// el. If the node is located, the function DeleteByCopying() is
called.
templatecclass genType>
void
BinarySearchTree::FindAndDeleteByCopying(genType& el)
{ TreeNode *p = root, *prev = 0;
while (!(p>key == el) && p) {
prev = p;
if (p>key < el)
p = p>right;
else p = p>left;
}
if (p>key == el)
if (p == root)
DeleteByCopying(root);
else if (prev>left == p)
DeleteByCopying(prev>left);
else DeleteByCopying (prev>right) ,
else if (root)
cout << "key << el << is not in the tree\n";
else cout << "the tree is empty\n";
}
32
template
void
BinarySearchTree::DeleteByMerging(TreeNode*&
node)
{ TreeNode *tmp = node;
if (node) {
if (inode>right)
left
node = node>left;
its parent;
else if (!node>left)
right
node = node>right;
parent;
else {
tmp = node>left;
while (tmp>right)
possible;
tmp = tmp>right;
tmp>right =
the
node>right;
left
//
tmp = node;
node = node>left;
}
delete tmp;
}
// node has no right child: its
// child (if any) is attached to
// node has no left child: its
// child is attached to its
// be ready for merging subtrees;
// 1. move left
// 2. and then right as far as
// 3. establish the link between
// the rightmost node of the
subtree and the right subtree;
// 4.
// 5.
// 6.
template
void
BinarySearchTree::FindAndDeleteByMerging(genType& el)
{ TreeNode *node = root, *prev = 0;
while (node) {
if (node>key == el)
break;
prev = node;
if (node>key < el)
node = node>right;
else node = node>left;
}
if (node>key == el)
if (node == root)
DeleteByMerging(root);
else if (prev>left == node)
33
DeleteByMerging(prev>left);
else DeleteByMerging(prev>right);
else if (root)
cout << "key << el << is not in the tree\n";
else cout << "the tree is empty\n";
templatecclass genType>
void
BinarySearchTree::IterativePreorder()
{ TreeNode *p = root;
if (P) {
travStack.Push(p);
while (! travStack. IsEmptyO ) {
p = travStack.Pop();
Visit(p);
if (p>right)
travStack.Push(p>right);
if (p>left) // left child pushed after right
travStack.Push(p>left); // to be on the top of the
stack;
}
}
}
templatecclass genType>
void
BinarySearchTree::Iterativelnorder()
{ TreeNode *p = root;
while (p) {
while(p) { // stack the right child (if any)
if (p>right) // and the node itself when
going
travStack.Push(p>right); // to the left;
travStack.Push(p);
p = p>left;
}
p = travStack.Pop(); // pop a node with no left
child
while (!travStack.IsEmpty() && !(p>right)) { // visit it
and all
Visit (p); // nodes with no right
child;
p = travStack.Pop();
}
Visit(p); // visit also the first node with
if (!travStack.IsEmptyO) // a right child (if any);
p = travStack.Pop();
34
else p = 0;
}
}
template
void
BinarySearchTree::IterativePostorder()
{ TreeNode *p = root;
if (p) { // lefttoright postorder = righttoleft
preorder
travStack.Push(p);
while (! travStack. IsEmptyO ) {
p = travStack.Pop();
output.Push(p);
if (p>left)
travStack.Push(p>left);
if (p>right)
travStack.Push(p>right);
}
while (!output.IsEmpty()) {
p = output.Pop();
Visit(p);
}
}
}
template
void
BinarySearchTree::BreadthFirst()
{ TreeNode *p = root;
if (p) {
queue.Enqueue(p);
while (!queue.IsEmpty()) {
p = queue.Dequeue();
Visit(p);
if (p>left)
queue.Enqueue(p>left);
if (p>right)
queue.Enqueue(p>right);
}
}
}
template
void
BinarySearchTree::Morrislnorder()
{ TreeNode *p = root, *tmp;
35
while (p)
if (p>left == 0) {
Visit(p);
p = p>right;
}
else {
tmp = p>left;
while (tmp>right && // go to the rightmost node
of
tmp>right != p) // the left subtree or
Y\ . tmp = tmp>right; // to the temporary parent of
P / if (tmp>right == 0) { // if 'true' rightmost node
was
tmp>right = p; // reached, make it a temporary
p = p>left; // parent of the current
root,
}
else { // else a temporary parent has been
Visit(p); // found; visit node p and then
cut
tmp>right =0; // the right pointer of the
current
p = p>right; // parent, whereby it ceases
to be
} // a parent,
}
}
templatecclass genType>
void
BinarySearchTree::Balance (genType data[], int first,
int last)
{
if (first <= last) {
int middle = first + (lastfirst) / 2;
Insert(data[middle]);
Balance (data, first,middle1) ,
Balance(data,middle+1,last);
}
}
#endif
j j ******************************* genLi stSt ack. h
Hr***********************
// generic stack, an offspring of generic linked list class
#ifndef SLL STACK
36
#define SLL STACK
#include "genSLLst.h"
templatecclass genClass>
class SLLStack {
public:
SLLStack() { }
void Push(const genClass& el) { list.Add(el); }
genClass Pop() { return *list.Remove(); }
int IsEmptyO const { return list.IsEmpty(); }
void PrintAll(ostream& out) const { list. PrintAll (out) ; }
void ClearO { list.Clear() ; }
private:
SinglyLinkedList list;
};
#endif
II ****************************
!!************************ genSLList.h.
*******************************
// generic singly linked list class with head only
#ifndef SINGLY_LINKED_L1ST
#define SINGLY_LINKED_L1ST
template
class SinglyLinkedList {
protected:
struct Node {
genType info;
Node *next;
Node() { }
Node(genType el. Node *ptr = 0)
{ info = el; next = ptr; }
} *head, *tmp;
genType el;
public:
SinglyLinkedList() { head =0; }
SinglyLinkedList () { ClearO; }
void Clear();
void SetToNullO { head =0; }
void PrintAll(ostreamS out) const;
genType* Find(const genType&) const;
void Add(const genTypefc el) { head = new Node(el,head); }
genType* Remove(); // remove the head and return its
info;
void Remove(genType&); // find a node and remove it;
37
int IsEmptyO const { return head == 0; }
genType* First() { return &head>info; }
Node* Head() { return head; }
templatecclass genType>
void
SinglyLinkedList::Clear ()
{
while (head) {
tmp = head;
head = head>next;
delete trap;
}
}
template
genType*
SinglyLinkedList::Remove()
{
if (head) { //if nonempty list;
el = head>info;
tmp = head;
head = head>next;
delete tmp;
return ⪙
}
else return 0;
}
template
void
SinglyLinkedList::PrintAll(ostream& out) const
{ Node *tmp;
for (tmp = head; tmp; tmp = tmp>next)
out << tmp>info << ";
// overloaded <<
templatecclass genType>
genType*
SinglyLinkedList::Find(const genType& el) const
{ Node *tmp;
for (tmp = head; tmp && !(tmp>info == el); // overloaded
tmp = tmp>next);
if (!tmp)
return 0;
else return &(tmp>info);
38
}
template
void
SinglyLinkedList::Remove(genTypek el)
{
if (head) // if nonempty list;
if (el == head>info) { // if head needs to be removed;
Node *pred = head;
head = head>next;
delete pred;
}
else {
Node *pred;
for (pred = head, tmp = head>next; // and a nonhead
node
tmp && !(tmp>info == el); // is deleted;
pred = pred>next, tmp = tmp>next);
if (tmp) { // if found
pred>next = tmp>next;
delete tmp;
}
}
}
#endif
/I ********************
#include
#include
#include
#include
#include
#include
#include "genLstSt.h"
#include "genSLLst.h"
#include "genBSTre.h"
class LocalTree;
class Network {
public:
NetworkO : yes(l), forward(l), sink(l), source(O), none(l),
numOfVertices(2) {
sourceVer.idNum = source;
sinkVer.idNum = sink;
sourceVer.edge = !forward; //no need
sinkVer.edge = forward;
39
sourceVer.capacity = sinkVer.capacity = 1;
sourceVer.edgeFlow = sinkVer.edgeFlow = 0;
}
void ReadNetwork(char *committees);
void AugmentPath();
void FordFulkersonMaxFlow();
void Print();
private:
friend LocalTree,
const int sink, source, none;
const unsigned int yes, forward : 1;
int numOfVertices;
struct Vertex {
int idNum, capacity, edgeFlow;
unsigned int edge : 1; // direction;
Vertex *twin; // edge in opposite direction
vertex () { }
Vertex(int id, int c, int ef, int e, Vertex *t = 0)
{ idNum = id; capacity = c; edgeFlow = ef; edge =
e; twin = t; }
int operator== (Vertex v) { return idNum == v.idNum; }
} sourceVer, sinkVer;
struct VertexArrayRec {
char *idName;
int vertexSlack;
unsigned int labeled : 1;
int parent;
SinglyLinkedList adj acent;
Vertex *corrVer; // corresponding vertex: vertex
on parent's
VertexArrayRec() { } // list of adjacent vertices with
the same
} *vertices, // idNum and the cell's index;
struct NetTreeNode {
int idNum;
char idName,
SinglyLinkedList adj acent;
NetTreeNode() { }
int operator< (NetTreeNode& tr)
{ return strcmp(idName,tr.idName) < 0; }
int operator== (NetTreeNode^ tr)
{ return strcmp(idName,tr.idName) == 0; }
};
friend ostreamk operator<< (ostream&, Network: :NetTreeNode&) ,
friend ostreamt operator<< (ostream&. Network: :Vertex&) ,
// class List : public SinglyLinkedList {
// friend FordFulkersonMaxFlow();
// } ;
SLLStack labeled;
40
int EdgeSlack(Vertex *u) { return u>capacity u>edgeFlow;
}
int min(int n, int m) { return n < m ? n : m; }
int Labeled(Vertex *p)
{ return vertices[p>idNum].labeled == yes; }
void Label(Vertex*,int);
} net ;
ostream&
operator<< (ostreamS out. Network::NetTreeNode& tr)
{
out << tr.idNum << 1 ' << tr.idName << '
return out;
}
// define new Visit() to be used by Inorder() from genBSTree.h;
class LocalTree : public BinarySearchTree {
void Visit(TreeNode* p)
{ net.vertices[p>key.idNum].idName = p>key.idName;
net.vertices[p>key.idNum].adjacent = p
>key.adj acent;
p>key.adjacent.SetToNull();
}
};
ostream& operator<<
{
out << vr.idNum
'
<< vr.edge
return out;
(ostreamSc out, Network: :Vertex& vr)
<< ' << vr.capacity << ' << vr.edgeFlow
<< ' <
void
Network::Print()
{ register int i;
for (i = 0; i < numOfVertices; i++) {
cout << i << ": "
<< vertices[i].idName << '
<< vertices[i].vertexSlack << '
<< vertices [i] .labeled << '
<< vertices[i].parent << '
<< vertices[i].corrVer << "
vertices[i].adjacent.PrintAll(cout);
cout << endl;
}
41
void
Network::ReadNetwork(char *fileName)
{ char i, name[80], s;
int lastMember;
LocalTree committeeTree, memberTree;
Vertex memberVer(0,1,0,!forward), *memberVerAddr;
Vertex commVer(0,1,0,forward), *commVerAddr;
NetTreeNode committeeTreeNode, memberTreeNode, *member;
SinglyLinkedList sourceList;
ifstream fIn(fileName);
if (fin.fail()) {
cerr << "Cannot open << fileName << endl;
exit(1);
}
while (Ifln.eofO) {
fin >> name[0]; // skip leading spaces;
if (fln.eofO) // spaces at the end of file;
break;
for (i = 0; name[i] != )
name [++i] = fln.getO;
for (i; isspace(name[i]); i); // discard trailing
spaces;
name[i+1] = '\0',
s = new char[strlen(name)+1];
strcpy(s,name);
committeeTreeNode.idNum = commVer.idNum =
numOfVertices++;
committeeTreeNode.idName = s;
for (lastMember = !yes; lastMember != yes; ) {
fin >> name[0]; // skip leading spaces;
for (i = 0; name[i] != && name[i] != ';'; )
name [++i] = fln.getO;
if (name[i] == ';')
lastMember = yes;
for (i; isspace(name[i]); i); // discard trailing
spaces;
name[i+1] = '\0';
s = new char[strlen(name)+l];
strcpy(s,name);
memberTreeNode.idName = s;
commVer.edge = !forward;
if ((member = memberTree.IsInTree(memberTreeNode)) ==
0) {
memberVer.idNum = memberTreeNode.idNum =
numOfVertices++;
memberTreeNode.adj acent.Add(sinkVer) ;
memberTreeNode.adj acent.Add(commVer) ;
commVerAddr =
memberTreeNode.adjacent.Find(commVer);
42
memberTree.Insert(memberTreeNode);
memberTreeNode.adjacent.SetToNull();
}
else {
memberVer.idNum = member>idNum;
member>adjacent.Add(commVer);
commVerAddr = member>adjacent.Find(commVer)
}
memberVer.edge = forward;
committeeTreeNode.adj acent.Add(memberVer);
memberVerAddr =
committeeTreeNode.adj acent.Find(memberVer) ;
memberVerAddr>twin = commVerAddr;
commVerAddr>twin = memberVerAddr;
}
commVer.edge = forward;
sourceList.Add(commVer);
committeeTree.Insert(committeeTreeNode);
committeeTreeNode.adj acent.SetToNull();
}
fin.close () ;
vertices = new VertexArrayRec[numOfVertices];
vertices[source].idName = "source";
vertices[sink].idName = "sink";
vertices[source].adjacent = sourceList;
vertices[source].parent = none;
sourceList.SetToNull(); // prevent the lists from wiping
them
committeeTree.Inorder(); // transfer data from both trees
memberTree.Inorder(); //to array vertices[];
Print();
}
void
Network::Label(Vertex *u, int v)
{
vertices[u>idNum].labeled = yes;
if (u>edge == forward)
vertices[u>idNum].vertexSlack =
min(vertices[v].vertexSlack,EdgeSlack(u));
else vertices[u>idNum].vertexSlack =
min (vertices [v] vertexSlack, u>edgeFlow) ,
vertices[u>idNum].parent = v;
vertices[u>idNum].corrVer = u;
}
void
Network::AugmentPath()
{ register int i;
43
Vertex *u;
cout << Augmenting path: ";
for (i = sink; i != source; i = vertices[i].parent) {
cout << vertices[i].idName << <= ";
if (vertices[i].corrVer>edge == forward)
vertices[i].corrVer>edgeFlow +=
vertices[sink].vertexSlack;
else vertices[i].corrVer>edgeFlow =
EdgeSlack(vertices[i].corrVer);
if (vertices[i].parent != source && i != sink)
vertices[i] .corrVer>twin>edgeFlow =
vertices[i].corrVer>edgeFlow;
}
cout << "source," << endl;
for (i = 0; i < numOfVertices; i++)
vertices[i].labeled = !yes;
}
void
Network::FordFulkersonMaxFlow()
{ register int i, v;
Vertex *u;
SinglyLinkedList::Node *er;
// List::Node *er;
for (i = 0; i < numOfVertices; i++) {
vertices[i].labeled = !yes;
vertices[i].vertexSlack =0; // no need;
vertices[i].parent = none; // no need;
}
vertices[source].vertexSlack = MAXINT;
labeled.Clear();
labeled.Push(source);
while (!labeled.IsEmptyO) { // while not stuck;
v = labeled.Pop();
for (er = vertices[v].adjacent.Head(), u = &er>info;
er; er = er>next, u = &er>info)
if (!Labeled(u)) {
if (u>edge == forward && EdgeSlack(u) > 0)
Label(u,v);
else if (u>edge != forward && u>edgeFlow > 0)
Label(u,v);
if (Labeled(u))
if (u>idNum == sink) {
AugmentPath();
labeled.Clear();
labeled.Push(source);// look for
another path;
}
else {
44
}
}
}
labeled.Push(u>idNum);
vertices[u>idNum].labeled = yes
main(int argc, char* argv[])
{ char fileName [30]
if (argc != 2) {
cout << "Enter a file name:
cin.getline(fileName,30);
}
else strcpy(fileName,argv[1] ) ;
net.ReadNetwork(fileName);
net.FordFulkersonMaxFlow(),
return 0;
}
45
References
[1] Gross, Jonathan, Jay Yellen, Graph Theory and its Applications, CRC Press,
Boca Raton, FI, 1998, 189191.
[2] Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, Introduction to
Algorithms, MIT Press, Cambridge, MA, 1990, 580.
[3] Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, Introduction to
Algorithms, MIT Press, Cambridge, MA, 1990, 585.
[4] West, D., Introduction to Graph Theory, PrenticeHall, Upper Saddle, NJ,
1996,162163.
[5] Gross, Jonathan, Jay Yellen, Graph Theory and its Applications, CRC Press,
1999,176.
[6] McHugh, James A., Algorithmic Graph Theory, PrenticeHall, Inc., 1990.
[7] Gross, Jonathan, Jay Yellen, Graph Theory and its Applications, CRC Press,
1999,178179.
[8] Harary, Frank, The maximum connectivity of a graph, Proc. Natl. Acad. Sci.,
U.S., 48 (1962) 142146.
[9] Alon, N, A. Barak and U. Mauber, On Disseminating Information Reliably
without Broadcasting, Proc. 7th Internet Conference on Distributed Computing
Systems, (1987), 7481.
[10] Bhatt, S.N., F.R.K. Chung, F.T. Leighton and A.L. Rosenberg, Efficient
Embeddings of Trees in Hypercubes, SIAM J. Computer, 21 (1992), 151
162.
[11] Weiss, Mark A., Data Structures and Algorithm Analysis in C++,
AddisonWesley, Reading, MA, 1999, 363364.
46
[12] Liang, Y and Chongkye Rhee, Finding biconnected components in O(n)
time for a class of graphs, Information Processing Letters, no. 60 pages
1996, 159163.
[13] Hochbaum, D.S., Why should biconnected components be identified first,
Discrete Appl. Math, 42,1993, 203210.
[14] Even, S. and Endre Tarjan, Network Flow and testing Graph Connectivity,
SIAM J. Computing, Yol. 4, no. 4,1975, 507518.
[15] Dinic, E.A., Algorithm for solution of a problem of maximum flow in a
network with power estimation, Soviet Math Dokl., 11,1970, 12771280.
[16] Ford, L. R. and D. R.Fulkerson, Flows in Networks, Princeton University
Press, 1962.
[17] Frisch, I. T., An Algorithm for VertexPair Connectivity, Int. J. Control,
Vol. 6, No. 6, 1967, 579593.
[18] Steiglitz, K. and J. Bruno, A new Derivation of Frischs Algorithm for
Calculating VertexPair Connectivity, BIT, Vol. 11, 1971, 94106.
[19] Takamori, H. EdgeDisjoint Routes and Blocking Routes Problems,
Department of Statistics and Operations Research, University of
Pennsylvania, Nov., 1969.
[20] Edmonds, J. and R.M. Karp, Theoretical Improvements in Algorithmic
Efficiency for Network Flow Problems, Journal of the Association for
Computing Machinery, Vol. 19, No. 2, April 1972, 248264.
[21] Price, W. L., Graphs and Networks, Auerbach Publishers, 1971, 4650.
[22] Dijkstra, E.W., A Note on Two Problems in Connexion with Graphs,
Numerische Mathematik, 1959,269271.
[23] Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, Introduction
to Algorithms, MIT Press, Cambridge, MA, 1990, 588.
[24] Garey, M.R. and David S. Johnson., Computers and Intractability, A Guide
to the Theory of NPCompleteness,W.H. Freeman and Company, 1979.
47
[25] Gibbons, Alan, Algorithmic Graph Theory, Cambridge University, 1985.
48
