Probabilities

This option finds the probability that an end node can be reached when directed links are available with specified probability

Input

format

The first line specifies the calculation required. It must contain

format probs

graph mode

Column	Description
1	g for graph

If present, this must be the second line. It specifies that the links are directed.

Links

Column	Description
1	l for link
2	src node name
3	dst node name
4	probability ( 0.0 to 1.0 )

end

Column	Description
1	e
2	node name

Example

format probs
g
l u c 0.3
l u d 0.5
l c a 0.2
l c b 0.2
l d b 0.4
l a v 0.1
l b v 0.1
e v

Result 0.0306512

Algorithm

IF A and B are independent events with probability PA and PB

Probability of A AND B both happening is PA * PB

Probability of A OR B OR both happening is PA + PB - PA * PB

- Mark all nodes 'uncalculated'
- LOOP over nodes
    - IF node has outlinks but no inlinks
        - LOOP over all paths from node to end node
            - LOOP PN over nodes in path
                 - LOOP I over inlinks to PN
                     - IF source node on I  'uncalculated'
                         - BREAK out of PN loop
                     - SET IP(I) = I probability * source node probability
                 - ENDLOOP I 
                 - IF 0 inlinks
                     - SET PN probability = 1
                 - IF 1 inlinks
                     - SET PN probability = IP[0]
                 - IF 2 inlinks
                     - SET PN probability = IP[0] + IP[1] - IP[0] * IP[1]
                 - IF inlinks > 2
                     - ask user to refactor input
                     - STOP
                 - IF PN = end node
                     - OUTPUT end node probability
                     - STOP

If a node has more then 2 inlinks, it can be refactored by adding intermediate nodes

e.g.