An Efficient Algorithm for Computing Network Reliability in Small Treewidth
Our implementation of the main algorithm is in Java, so you will need a JRE to execute it. Moreover, the scripts we use for performing experiments are written in a combination of bash and C++. Hence, our tool can be executed on Linux/Mac machines and depends on g++.
We use an external tool, called FlowCutter, for computing tree decompositions. See https://github.com/kit-algo/flow-cutter-pace17 for instructions on installing FlowCutter.
An instance is specified using two files. The first file, which we call “input.txt” consists of a description of the graph G and the probabilities Pr. The second file, which we call “sourcetarget.txt” specifies the source and target vertices.
We assume that the vertices are numbered from 1 to n. Each line of input.txt defines a single edge and consists of three space-separated values: u v and p, denoting an edge from u to v with probability p.
The first line includes the source vertex. The second line includes a space-separated list of target vertices.
Browse to the “tool” folder and prepare input.txt and sourcetarget.txt as above. Copy FlowCutter into “tool/flow-cutter-pace17”. Then, run the following command in the terminal:
java -jar main.jar input.txt sourcetarget.txt
To run the experiment with p=0 to p=1 (with step size 0.05), go to the “experiment” folder and fill in “graph.txt” and “sourcetarget.txt” as above (except that the graph description no longer contains probabilities). Then simply run the following command in the terminal:
The results will be compiled into a folder called “log”. Note that FlowCutter should also be copied in the “experiment” folder before running “all.sh”. The “instances” folder contains the graphs of subway systems of Berlin, London, Tehran, Tokyo and Vienna. See the “readme.txt” file.
By default, the time limit for FlowCutter to computer a tree decomposition is set to 10 minutes. To change the time limit, simply edit “computeTD.sh” (resp. “computeTD-disabled.sh”) and change the number 600 in the first line.
Please write to goharshady[at]ist.ac.at for any questions.