American Journal of Computational Mathematics, 2012, 2, 316320 http://dx.doi.org/10.4236/ajcm.2012.24043 Published Online December 2012 (http://www.SciRP.org/journal/ajcm) An InclusionExclusion Algorithm for Network Reliability with Minimal Cutsets YanRui Sun, WeiYi Zhou 1School of Sciences, Northeastern University, Shenyang, China 2School of Electronic Information, Wuhan University, Wuhan, China Email: yanruisun@126.com, weiyi0564@126.com Received August 10, 2012; revised October 9, 2012; accepted October 23, 2012 ABSTRACT The inclusionexclusion formula (IEF) is a fundamental tool for evaluating network reliability with known minimal paths or minimal cuts. However, the formula contains many pairs of terms which cancel. Using the notion of compara ble node partitions some properties of canceling terms in IEF are given. With these properties and the thought of “dy namic programming” method, a simple and efficient inclusionexclusion algorithm for evaluating the sourcetoterminal reliability of a network starting with cutsets is presented. The algorithm generates all the noncanceling terms in the unreliability expression. The computational complexity of the algorithm is 3 On mM , where n and m are the numbers of nodes and minimal cuts of the given network respectively, M is the number of terms in the final symbolic unreliability expression th at generated us ing the presented algorithm. Examples are shown to illustrate the effectiveness of the algorithm. Keywords: InclusionExclusion Formula; Network Reliability; Minimal Cu tset; Dynamic Programming 1. Introduction The reliability of a network is an important parameter in design and operation of networks. There are many meth ods to compute the reliability of networks [1,2]. Several algorithms exist in the literature for evaluating the reli ability of a directed graph by inclusionexclusion formula (IEF) based on either path (ktree) enumeration or cutset enumeration [38]. In finding the k terminal reliability by IEF there are two approaches, one based on enumeratin g all ktrees and the other based on enumerating all kterminal cuts. If there are m minimal paths (or cuts) in a graph, there are possible intersection terms in IEF. However, the number of noncancelling terms in IEF is considerably less. 21 m Starting with the set of paths (or ktrees) of a directed graph, Satyanarayana and coworkers [5,6] developed methods of identifying noncancelling terms in IEF. They sh owed that the non canceling terms of the source toterminal reliability correspond onetoone with the pacyclic subgraphs of the given graph. An algorithm was given for generating all the pacyclic subgraphs of a directed graph [5]. Buzacott [3] gave a corresponding result for the noncancelling terms in IEF starting with the set of cuts of a graph. Since each term in the resulting formula is associated with a partition of the set of nodes of the graph, it was called the node partition formula. Find all the node partitions of a graph is a very tedious work. Using a lemma (the Lemma 3.4 of [3]) of incompara ble node partitions of [3] and characteristics of can celing terms in IEF, by the thought of “dynamic programming” method a simple and efficient inclusionexclusion algo rithm is given in this paper for evaluating the source toterminal reliability of a graph based on minimal cuts. The algorithm generates only the noncanceling terms of the reliability expression of the graph. 2. Nomenclature, Notation and Assumption A network is modeled as a directed graph ,GNE (abbreviated to G) which consists of a set of nodes N and a set of edges (links) E. A node N is the source of G and tN s is the terminal of G. 2.1. Nomenclature Source to terminal (s – t) reliability: the probability that the source s is connected to the terminal node t by paths working edges. t cut: a subset of edges whose removal divides the node set of the network into two parts i and Ni N such that ii NNN , i N and i Nt, i.e. the edge set from to i Ni N. C opyright © 2012 SciRes. AJCM
Y.R. SUN, W.Y. ZHOU 317 Minimal t cut: t cut which no longer re mains a t cut if its any edge is removed. Candidate child set of : an ordered set i N 12 ,,, r ii i NN N 1, ii NN consisting of all the node sets such that , 2,, jj r12 r ii NN Ni 2 . Incomparable node sets: a pair of node sets and such that and . 1 N 2 N1 NN21 NN 2.2. Notation i N: subset of such that Ni N i N: complement of, and i Ni tN , ii NN : cut, i.e. the edge set from to i Ni N i C: 1) cut , ii NN 1) event that all the edges of cut fail i : 1) union of all the edges of cuts and C ij CC i C C 2) intersection of events and i C C i U(N : union of i cuts ) i : candidate child set of i N Pr : the probability of event , G Qst: sourcetoterminal (s – t) unreliability of G 2.3. Assumption 1) G has perfectly reliable nodes and sindependent 2state (good and failed) edges, and the reliability of each edge has been given. 2) Let , ii CNN i and , jj CNN be mincuts of G, then , ij ijij CNNNN is also a min cut of G. 3. Preliminaries Let be the set of mincuts of a given network G where corresponds onetoone with the 12 ,,, m CC C Ci node set , i.e. i N , ii CNNim (). The s – t 1, 2,,i unreliability of G, by IEF, can be expressed as 12 11 1 12 1 , Pr Pr Pr Pr1 Pr G m iij imi jm m ijk m ijkm Qst CC C CCC CCCCC C (1) the summations are over all mincuts and mincut combi nations. In formula (1), there exist possible terms. But it is possible that ij for some , . Indeed the most vexing problem in reliability analysis using (1) is the appearance of large numbers of pairs of identical terms with opposite sign, which cancel. Find the charac teristic of canceling terms in (1) is the keystone of an efficient algorithm. Buzacott gave a simple and very useful lemma (Lemma 3.4 of Ref. [3]) to identify some canceling terms in (1). 21 m UU,ij ij Lemma 1. Given any two mincuts , ii CNN i and , jj CNN of G such that and i N N are incom parable, all terms in IEF containing both and i C C cancel if , ij ijij CNNNN is also a mincut [3]. In formula (1), assume that 12 m NN N. According to Lemma 1, (1) can be changed into: 12 12 12 12 11 1 1 1 ,Pr Pr Pr Pr 1Pr ij ijk k ii i k k Gm iij imN N ijm ijk NN N ijkm k ii i NNN iiim QstC CC CCC CCC CC C (2) the summations are over all mincuts and mincut combi nations that satisfy the given conditions. The terms in (2) can correspond onetoone the vertex of the m rooted trees with the following properties. 1) The root vertex of each rooted tree is the vertex i corresponding to cut set , its weight is , sign is +1. N i CNi 2) Sons of each vertex i in every rooted tree are all elements in C i N , each son’s weight is the union of its father’s weight and the cut set corresponding to this son vertex, sign is its father’s sign times –1. For example, let 1234 , NNNN , ii CNNi 1, 2, 3, 4i. Figure 1 are four rooted trees. In Figure 1(a), tree (N4) has a only vertex, the root vertex N4. Its weight is C4, sign is 1. In Figure 1(c), tree (N2)’s root vertex is N2, its weight is C2, sign is 1. N2 has two sons: N3 and N4. The son vertex N3’s weight equals to C2C3, sign is –1; N4’s weight equals to C3C4, sign is –1. N3’s son is N, here N4’s weight equals to C2C3C4, sign is 4 111 . The weight with its sign of each node in the rooted trees onetoone corresponds with the term in the expres sion of formula (2). So we discuss m rooted trees’ gener ating. The rooted tree whose root is is denoted as tree i N i N. In fact, if we generate the rooted trees in nonincreas ing order of root’s modulus and generate the sons of each vertex in nondecreasing order of the son’s modulus, we can use the trees which have already been generated to generate the following trees. For example, Figure 1 are four rooted trees, where tree is a branch of tree 3 N 2 N, tree 2 N and tree are the branches of tree 3 N 1 N. If tree 3 N is generated firstly, we can use the result when we generate tree . And when we 2 N Copyright © 2012 SciRes. AJCM
Y.R. SUN, W.Y. ZHOU 318 (b) (c) 2 3 4 4 3 4 4 (a) (d) 4 1 2 4 4 3 4 3 Figure 1. Rooted subtrees. (a) Subtree(N4); (b) Subtree(N3); (c) Subtree(N2); (d) Subtree(N1). generate tree , we can use tree and tree directly. This is the thought of “dynamic pro gramming”. By this thought the process of generating trees is greatly simplified. 1 N 3 N 2 N In formula (2) there are still many terms that can can cel each other. The properties of canceling terms are dis cussed as follow. Theorem 1. Let , iii be three mincuts of a directed graph G, 12 , and . Then for any mincuts CNN 1, 2,3i NN3 N 123 13 CCC CC 0 N 1 00 ,CN that and 0 NN N 444 ,N3 CN that of G, 4 N 0123 013 CCCCCCC, . 1234 134 CCCC CCC Theorem 2. Let , ii CNNi 1, 2,3i be three mincuts of a directed graph G with 12 . If 123 then doesn’t exist mincut 3 NNN 13 CCC CC N 00 ,CN 23 013 CC CCC 0 of G, 01 such that 01; and doesn’t exist NNCC 444 ,CNN 3 of G, such that . 43 NN 1234 1 CCCC CC34 Theorems 1 and 2 imply that if we find out the all pairs of canceling terms that union of two cuts and three cuts, i.e. find out all 2 and 3 U with , the all canceling terms in (2) can be determined. C U 2 UU The following lemma gives a condition that 23 UU in (2). Lemma 2. Let , iii be three minimal cuts of a directed graph G and . Then if and only if . CNN 3 1,2, 3i 12 NNN 13 123 CC CCC 213 2 ,NNNN According to Theorems 1 and 2 and Lemma 2 we give the generating processes of the trees with above proper ties 1) and 2). Such that trees’ vertices correspond with the noncanceling terms of (2). 4. Algorithm This section presents an algorithm for efficiently generat ing all the noncanceling terms in (2). The algorithm has four parts, The main part is to generate all trees whose vertices correspond with the noncanceling t e rm s of (2 ). 4.1. Algorithm 1) Find all the mincuts of the given directed network ,GNE 12 ,,NN 12 ,,NN which satisfies assumptions. Let 12 be the mincuts corresponding to the node partitions , respectively. Order the node partitions as such that ,,, m CC C , m N , m N12 NNm N. 2) Find 1, 2,, i Ni m . 3) Generate m rooted trees by the following Algo rithmTree, i.e. generate all the noncanceling terms of , G Qst. 4) Sum up the weights with sign of vertices of all the trees to obtain the symbolic expression of , G Qst. Finally, we get the symbolic reliability expression of ,1 , GG Rst Qst . 4.2. Algorithm Tree By theorems 1 and 2, all the pairs of canceling terms in IEF can be known if we find the canceling terms which union of two and three cut sets. Using this property an algorithm “Algorithm Tree” is given. It has two parts: “Trees Generation” and “Weighted Trees”. It generates rooted trees in the nonincrease order of the root vertex’s modulus, i.e. generates tree (Nm), tree (Nm1), ···, tree (N1) successively. 4.2.1. Trees Generation We shall give an algorithm to generate all trees as follow. Algorithm Trees Generation Input: 1) the node partitions of G: 12 such that ,,, m NN N 12 m NN N and the corresponding mincuts . 12 2) the candidate child sets: ,,, m CC C 1 111121 12 1 ,,,,, ,,,, ,, k t kkk kt mmm NNN N NNN N NNN . Output: all the trees. Begin Step 1. Generate the first tree with the only vertex, i.e. root vertex . m N N m Step 2. Generate the second tree with a root N 1m Copyright © 2012 SciRes. AJCM
Y.R. SUN, W.Y. ZHOU 319 vertex and its only son vertex . 1m Step 3. Suppose that trees Nm N mk 1mi N , 1, 2,,ikm have been generated. Generate tree . N N 1) The root of tree is . mk mk 2) Generate sons (we call them the firstgeneration offspring) of : N mk N,1 ,2, ,,, mk mk mkmkt NN N k N ,, mk mk (where ,1 ,mk NN mk NN mk 1 GN 2 , ,,, mk mkmktm N , ,mktm); 1,1,2 , mk mk mkmkt GNNN NN , . 3) While do. 1mk GN Begin Denote the element with the minimal modulus in as , mk,mki N1it N . 11kmk mk i,m GN GN. Substitute mk ’s son ,mki with treeNN ,mki N ,mki N . Denote the son set of this vertex as . Suppose GN m GN GN N 1,mki ,,N 12 1,, ,, ki kim kim kiki , m N mki N (in the nondecreasing order of their modulus). 0, 1,mki mki GN . For j = 1 to i k Begin If and ,1 j mkimk NGN ,NNN ,,, j mkimk mki , then 1, 1,, mkimki ki GN GN m N , ; 11 mkmk i GN GN mk N ; Cut ’s son ,mk N mki and ,mk’s son Ni N , mki N N N with its offspring from current tree ; ,mki Else next j End If 0,1,mki mki , then mark ,mki , called it still node, denoted as still node . GN GN ,mki N End. Step 4. Repeat step 3 until all the trees , i N have bee n ge nerate d. ,1,m,2,im 1 End. 4.2.2. Weighted Trees Tree’s weight is defined the sum of root’s and all verti ces’ weights with their sign. In the order of generating trees, starting from each tree’s root vertex gives each vertex a weight in depth firstsearch. The root’s weight is the all edges of the cut set corresponding to the root vertex, sign is +1. Each nonstill vertex’s weight equals to the union of its fa t s Figure 2. Network. ther’s weight and all the edges of the cut set correspond ing this vertex, its sign is its father’s sign times –1. Each still node’s weight equals to the union of its father’s weight and the tree’s weight whose root is this vertex and its sign is its father’s sign times –1. 5. Computational Complexity The main part of the presented algorithm is “Algorithm Subtree”. It has two parts. One is Subtrees Generation, the other is Weighted Subtrees. The main work of “al gorithm Subtrees Generation” is to determine whether there exist edges between two sets. It at most needs 1211mm mm 2 comparison op erations for each subtree. “Weighted subtrees” runs in OM 2m 18 2 2 m , wh ere M is the number of terms in the last sym bolic unreliability expression. In fact, M is more smaller than . For examp l e ，the network in Figure 2, m = 18, , but M = 151. For each of subtrees, other operations at most take time. It takes 262144 Om On ti me to find all mincuts, where n is the number of nodes of a given network. It takes time to find each candidate child set. So the computational complex ity of the presented algorithm is . Om On m 3 M 6. Conclusion This paper presents an efficient algorithm for evaluating the reliability of network based mincuts. The algorithm generates all the noncanceling terms in the unreliability expression. By the thought of “dynamic programming” method each vertex at most generates two generations children in every subtree. The number of vertices of the generated subtrees are more smaller than the number of noncanceling terms in , G Qst’s expression. The algo rithm has smaller time complexity. REFERENCES [1] C. J. Colbourn, “The Combinatorics of Network Reliabil ity,” Oxford University Press, New York, Oxford, 1987. [2] M. O. Ball, C. J. Colbourn and J. S. Provan, “Network Reliability,” Handbook of Operations Research: Network Models, Elsevier NorthHolland, Amsterdam, Vol. 7, 1995, pp. 673762. Copyright © 2012 SciRes. AJCM
Y.R. SUN, W.Y. ZHOU Copyright © 2012 SciRes. AJCM 320 [3] J. A. Buzacott, “Node Partition Formula for Directed Graph Reliability,” Networks, Vol. 17, No. 2, 1987, pp. 227240. doi:10.1002/net.3230170207 [4] J. A. Buzacott and S. K. Chang, “Cut Set Intersections and Node Partition,” IEEE Transactions on Reliability, Vol. 31, No. 4, 1982, pp. 385389. [5] A. Satyanarayana and A. Prabhakar, “New Topological Formula and Rapid Algorithm for Reliability Analysis of Complex Networks,” IEEE Transactions on Reliability, Vol. 27, No. 1, 1978, pp. 82100. doi:10.1109/TR.1978.5220266 [6] A. Satyanarayana and J. N. Hagstrom, “A New Algorithm for Reliability Analysis of MultiTerminal Networks,” IEEE Transactions on Reliability, Vol. 30, No. 4, 1981, pp. 325334. doi:10.1109/TR.1981.5221103 [7] L. C. Zhao and F. J. Kong, “A New Formula and an Al gorithm for Reliability Analysis of Network,” Microelec tron Reliability, Vol. 37, No. 4, 1997, pp. 511518. [8] W. C. Yeh, “A Greedy BranchandBound InclusionEx clusion Algorithm for Calculating the Exact MultiState Network Reliability,” IEEE Transactions on Reliability, Vol. 57, No. 1, 2008, pp. 8893. doi:10.1109/TR.2008.916871
