Code covered by the BSD License  

Highlights from
An Approximation Solution for the Prize-Collecting Steiner Tree Problem

  • FindTree(G, vp) G is matrix representing a undirected graph (V,E) have none negtive weighted edges, where the G(i,j) is the cost of edge(i,j)
  • PCSTr(G, vp, r) G is matrix representing a undirected graph (V,E) have none negtive weighted edges, where the G(i,j) is the cost of edge(i,j)
  • View all files

An Approximation Solution for the Prize-Collecting Steiner Tree Problem

by

 

18 Jan 2013 (Updated )

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

FindTree(G, vp)
%% G is matrix representing a undirected graph (V,E) have none negtive weighted edges, where the G(i,j) is the cost of edge(i,j)
%% Each vertex in V is denoted by the index 1,2,3,... size(V)
%% vp is vertex penalites, a list of int

function T = FindTree(G, vp)  
    score = -inf;
    T = [];
    for i = 1:length(vp)
        Temp = PCSTr(G, vp, i);
        TempScore = Temp.score;        
        %{ 
        Debug information
         str = sprintf('The edge(s) in tree with root %d and total score is %d', i, TempScore);
         disp(str);
         disp(' Vertex      Vertex       Cost');
        
        for i = 1: length(Temp.E)
             str = sprintf('   %d(%d)         %d(%d)         %d', Temp.E(i).id.i, vp(Temp.E(i).id.i), Temp.E(i).id.j, vp(Temp.E(i).id.j), Temp.E(i).cost);
             disp(str);
        end
        %}
        %% disp('---------------------------------------------------------');
        if TempScore >= score            
             score = TempScore;          
             T = Temp;
             
        end
    end
           
    disp('The edge(s) in the tree is(are)');
    disp('     Vertex           Vertex          Cost');
    for i = 1: length(T.E)
        str = sprintf('%4d(%6d)      %4d(%6d)       %4d', T.E(i).id.i, vp(T.E(i).id.i), T.E(i).id.j, vp(T.E(i).id.j), T.E(i).cost);
        disp(str);
    end
    str = sprintf('total score is %d', T.score);
    disp(str);
    
        
        
    

       





Contact us