We consider the connected subgraph problem which can be described as follows: We are given a connected, undirected graph G = (V,E). For each node v in V we are given a non-negative cost c(v) and a non-negative profit p(v). Moreover, we are given a positive budget b and a set of distinguished vertices T (being a subset of V). The goal is to find a connected subgraph whose vertex set contains T and which maximises the total profit subject to the total cost being less or equal than the budget b.
Further information is available here.
The considered input file is given by the Corridor instance format.
Run python3 main.py -h to see all command line arguments.
In root directory: python3 -m unittest discover test -v