Description 
Usage:
The PrizeCollecting Steiner Tree problem (PCST) is to find a tree T = (V',E') of a undirected graph G(V,E) that maximizes profit(T) which is defined as the sum of all nodeprizes taken into the solution minus the costs of the edges needed to establish the network.
Use T = FindTree(G,vp) to start the computation.
The function PCTSP(G,vp,r) try to find a optimal prizecollecting steiner tree with the root node to be r.
FindTree run PCTSP multiple times using different vertices as roots to find the best prizecollecting steiner tree.
input format:
The input graph for the program is represented by a matrix G and vector vp.
Assume there are n vertices in the graph. The vertices are denoted by 1, 2, 3,...,n. Then G is an n by n matrix. If G(i,j) is NaN or negative number, there is no edge linking vertex i and vertex j. Otherwise, it means the cost of edge(i,j).
The vector vp stores the scores of the vertices. vp(i) is the score of vertex i.
Example:
G = [1, 1, 1;
1, 1, 0;
1, 0, 1;]
vp = [2, 1, 1]
means a graph having 2 edges: e(1,2) with cost 1 and e(2,3) with cost 0. The score on vertex 1 is 2, on vertex 2 is 1, and on vertex 3 is 1.
If G =
[1 1 10 1 1 1 1 1 1 1;
1 1 1 1 1 10 1 1 1 1;
10 1 1 10 1 1 1 1 1 1;
1 1 1 1 1 1 1 1 10 1;
1 1 1 1 1 1 10 10 1 1;
1 10 1 1 1 1 10 1 1 1;
1 1 1 1 10 10 1 1 1 1;
1 1 1 1 10 1 1 1 1 100;
1 1 1 10 1 1 1 1 1 100;
1 1 1 1 1 1 1 100 100 1;]
vp = [10 1 1 150 200 1 100 1 1 20];
and FindTree(G,vp) will be
The edge(s) in the tree is(are)
Vertex Vertex Cost
3(1) 5(200) 1
5(200) 6(1) 1
5(200) 9(1) 1
3(1) 4(150) 10
5(200) 7(100) 10
total score is 430.
The numbers in the parentheses are the vertex scores.
You may need to implement a parser by yourself to construct such a matrix and vector from your data files.
Bibliography:
Michel X. Goemans and David P. Williamson: A general approximation techique for constrained forest problems. SIAM Journal on Computing, 24:296317, 1995.
The program is based on the pseudo code on the Page 19.
