steiner.cc

#include<sstream>
#include<scil/scil.h>
#include<scil/constraints/path.h>

using namespace std;
using namespace boost;


struct vertex_reached_t {
  typedef vertex_property_tag kind;
};

struct edge_cost_t {
  typedef edge_property_tag kind;
};

typedef property<vertex_color_t, int> vertexProperty;   // replace with boost::default_color_type..... -1=red, 0=white, 1=green
typedef property<edge_cost_t, double> edgeProperty;
typedef boost::adjacency_list<vecS,vecS,bidirectionalS,vertexProperty,edgeProperty > Graph;

typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef graph_traits<Graph>::edge_descriptor edge_descriptor;

double strToDouble(const char* s){
  return atof(s);
}

void read_steinlib(Graph& G, const char* fname) {
  int n, i, j, k;

  ifstream ifs(fname);  
  std::string s;
  vertex_descriptor lastterm;
  edge_descriptor e;
  std::string prefix;

  while(!ifs.eof()) {

    getline(ifs,s);

    istringstream is(s);
    is >> prefix;

    if(prefix=="Nodes") {
      is >> n;
      cout<<n<<" Nodes\n";
      for(i=0; i<n; i++) {
        add_vertex(G);
      };
    };
    if(prefix=="E") {
      is>>i;
      is>>j;
      std::string s2;
      is>>s2;
      add_edge(i-1,j-1,strToDouble(s2.c_str()),G);
      add_edge(j-1,i-1,strToDouble(s2.c_str()),G);
    };
    if(prefix=="A") {
      is>>i;
      is>>j;
      std::string s2;
      is>>s2;
      if(s2!="1000000000") {
        add_edge(i-1,j-1,strToDouble(s2.c_str()),G);
      };
      is>>s2;
      if(s2!="1000000000") {
        add_edge(j-1,i-1,strToDouble(s2.c_str()),G);
      }
    };
    if(prefix=="T") {
      is >> i;
      put(vertex_color_t(),G,i-1,-1);   // color = red
      lastterm = i-1;
    };
    if(prefix=="DD") {
      is>>i;
      is>>j;
      is>>k;
    };
  };

  bool haveroot=false;
  BGL_FORALL_VERTICES(u,G,Graph) {
    if( in_degree(u,G)==0 ) {
      put(vertex_color_t(),G,u,1);      // color = green
      haveroot=true;
      cout<<"Declare a root\n";
    };
  }

  if(haveroot==false) {
      put(vertex_color_t(),G,lastterm,1);       // color = green
      cout<<"Declare last terminal as root\n";
  };
};



//void ComputeSteinerTree(Graph& G, edge_array<double>& Cost, node r,
//                      node_array<bool>& R, std::list<edge>& T) {
void ComputeSteinerTree(Graph& G, vertex_descriptor r, std::vector<bool>& R, std::list<edge_descriptor>& T) {
 
  cout<<"setupm\n";

  ILP_Problem IP(Optsense_Min);

  cout<<"setup problem\n";

  var_map<edge_descriptor> VM;
  BGL_FORALL_EDGES(e,G,Graph) { 
    double cost = get(edge_cost_t(),G,e);
    VM[e]=IP.add_binary_variable(cost);
  }

  BGL_FORALL_VERTICES(u, G, Graph) {
    if(R[u]) {
      IP.add_sym_constraint(new PATH<Graph>(G, r, u, VM));
      row r;
      BGL_FORALL_INEDGES(u,e,G,Graph) r+=VM[e];
      IP.add_basic_constraint(r==1);
    } else if(u!=r) {
       row r;
       BGL_FORALL_INEDGES(u,e,G,Graph)  r+=VM[e];
       BGL_FORALL_OUTEDGES(u,e,G,Graph) r-=VM[e];
       IP.add_basic_constraint(r<=0);
    }
  }

  cout<<"start optimization\n";
  IP.optimize();
  
  BGL_FORALL_EDGES(e,G,Graph) {
    if(IP.get_solution(VM[e])==1) T.push_back(e);
  }
} 


int main(int argc, char** argv)
{
  cout.precision(10);

  char* s;
  if(argc<2) {
    cout<<"Filename : ";
    cin>>s;
  }else
    s = argv[1];

  Graph G;
  read_steinlib(G, s); 

    
  std::vector<bool> R(num_vertices(G),false); 
  vertex_descriptor r;
  BGL_FORALL_VERTICES(u,G,Graph) {
    if(get(vertex_color_t(),G,u)==-1) R[u]=true;        // color = red
    if(get(vertex_color_t(),G,u)==1) r=u;               // color = green 
  };

  std::list<edge_descriptor> T;
  ComputeSteinerTree(G, r, R, T);

  return 0;
}

---