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.