An Efficient Algorithm for Computing Network Reliability in Small Treewidth

Implementation Guide

Download

Prerequisites

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.

Computing Reliability of a Single Instance

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.

Format of input.txt

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.

Format of sourcetarget.txt

The first line includes the source vertex. The second line includes a space-separated list of target vertices.

Steps for Computing Reliability

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

Performing the Experiments Reported in the Paper

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:

./all.sh

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.

Changing the Time Limit for Computing Tree Decompositions

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.

Contact

Please write to goharshady[at]ist.ac.at for any questions.