broadcast.cc

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <scil/constraints/stronglyconnected.h>
#include <scil/scil.h>

using namespace SCIL;
using namespace std;
using boost::no_property;
using boost::directedS;
using boost::undirectedS;
using boost::bidirectionalS;
using boost::vecS;
using boost::property;
using boost::edge_weight_t;

#define MAX_DOUBLE 10e+300
#define MAX_INT 1000000


typedef boost::adjacency_list<vecS,vecS,undirectedS, no_property, property<edge_weight_t, double> > Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits<Graph>::edge_descriptor edge_descriptor;


#include"sym_connect.cc"

struct point {
    double x;
    double y;

    point(double x_ = 0.0, double y_ = 0.0) : x(x_), y(y_) { }; 

    // Distance to another point. 
    double distance(point other) {
      double xd = x - other.x;
      double yd = y - other.y;
      return sqrt(xd * xd + yd * yd);
    }
};

void make_tests(char* s) {

      cout<<"Instance: "<<s<<endl;
      ifstream outp(s);

      double x,y;
      edge_descriptor e;
      std::list<edge_descriptor> T;

      int i;
      outp >> i;

      Graph G;
      std::vector<point> P(i);
      vertex_descriptor u;

      std::vector<int> N(i);
      for(int k=0; k<i; k++) {
        outp >> x;
        outp >> y;
        point p1(x,y);
        u=add_vertex(G);
        P[u]=p1;
        N[u]=k;
      }

      // COMPLETE GRAPH
      BGL_FORALL_VERTICES(u,G,Graph) {
         BGL_FORALL_VERTICES(v,G,Graph) {
            if(u>v) add_edge(u,v,G);
         }
      }

      property_map<Graph,edge_weight_t>::type 
        cost = get(edge_weight, G);
      BGL_FORALL_EDGES(e,G,Graph) {
        cost[e]=P[source(e,G)].distance(P[target(e,G)]); 
      }

      ComputeBroadcast(G, T);
};


int main(int argc, char** argv)
{
  if (argc < 2) {
    std::cout<<"usage: broadcase name_of_file";
    return 0;
  }

  make_tests(argv[1]);

  return 0;
}

---