mahi045 / relnet Goto Github PK

RelNet is a counting-based network reliability framework using state-of-the-art approximate model counters like ApproxMC.

• Python 3
• ApproxMC (for model counting)

First download the repository:

$ git clone https://github.com/paredesroger/relnet
$ cd relnet

Install (optional) the package to make sure you meet Python dependencies:

$ python setup.py install

In the K-terminal network reliability problem you are given a graph G=(V,K,E) and you are asked to compute the probability that the terminal nodes in K, a subset of V, will remain connected given that each edge e in E fails with probability p_e.

The toy problem in Fig. 1(a) of our paper considers a graph G=(V,K,E) with V=[1, 2, 3, 4], K=[1, 4], and E=[(1,2), (1,3), (2, 4), (3, 4)], and edge "down" probabilities P=[0.5, 0.375, 0.5, 0.5]. The input file format for this graph is as follows:

c "c" lines are comments
c problem type
p g
c terminal nodes
T 1 4
c edges and corresponding "up" probabilities
e 1 2 0.5
e 1 3 0.625
e 2 4 0.5
e 3 4 0.5

To compute the unreliability u of the graph, construct the CNF file issuing:

$ python -m relnet example_graph.txt example_graph.cnf
[relnet] CNF file "example_graph.cnf" saved
[relnet] Number of sampling variables is 6
[relnet] For counting issue:
         $  approxmc example_graph.cnf

If you install ApproxMC, you can compute the count issuing:

$ approxmc example_graph.cnf
...
[appmc] FINISHED AppMC T: 0.02 s
[appmc] Number of solutions is: 33 x 2^0

Finally, the unreliability is u = (33 * 2^0 ) / 2^6 = 0.515625

For a large graph you can set multiplicative error threshold epsilon_val and chance of exceeding it delta_val as follows:

$ approxmc --epsilon epsilon_val --delta delta_val large_graph.cnf

If you use RelNet, please cite these papers PMDV2019 and AAAI17.