An Approximation Solution for the Prize-Collecting Steiner Tree Problem

A function giving feasible(not optimal) solutions to the Prize-Collecting Steiner Tree Problem

Usage:
The Prize-Collecting 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 node-prizes 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 prize-collecting steiner tree with the root node to be r.
FindTree run PCTSP multiple times using different vertices as roots to find the best prize-collecting 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:296-317, 1995.
The program is based on the pseudo code on the Page 19.