Berechnung der Zuverlaessigkeit von Netztopologien

(Reliability of Network Topologies, ReNeT)
Heidtmann, 1997,  developed an algorithm to compute the probability that the nodes of a subset of all nodes of a given network topology are connected by decomposing this event into a union of events which are disjoint and whose probabilities can be sumed up. The advantage of this method is that it produces much less disjoint terms than other methods and that it is therefore much more effective (For a comparison with other methods see ReNeTComp).

Xiang developed an applet to demonstrate that algorithm. You will be able to input your network model by drawing a graph and defining the probability of every edge of the network. The network will be firstly reduced by eliminating serial and parallel edges and then the reduced network will be decomposed with Heidtmann's method. Finally the reliability of the network (i.e. the probability the nodes of a subset K of all network nodes are connected) will be calculated and output.

Please run the applet.

 
Heidtmann's algorithm:
(for monoton systems only)

Procedure HEIDTMANN-ZERLEGUNG(I(0),I(1),...,I(k),i)
begin
    if i=k
        then output I(0),I(1),...,I(k-1)
    else
        if $ l, 0<l<i and {}Ì I(l)Í Ii
            then HEIDTMANN-ZERLEGUNG(I(0),I(1),...,I(k),i+1)
        else
            begin
                    for all l=0 upto k, HI(l)=I(l)
                    for all l=1 upto i-1
                        begin
                            HI(l)=I(l)Ç Ii
                            if HI(l)¹ {} then
                                HEIDTMANN-ZERLEGUNG(HI(0),HI(1),...,HI(k),i+1)
                            HI(l)=I(l)-Ii
                            HI(0)=HI(0)È (I(l)Ç Ii)
                        end
                                             i-1
                    HI(i)= Ii-È I(l)
                                            l=0

                    if HI(i)¹ {} then
                        begin
                            for all l=1 upto i-1, HI(l)=HI(l)-HI(i)
                            HEIDTMANN-ZERLEGUNG(HI(0),HI(1),...,HI(k),i+1)
                        end
                end
end