broadcast.c

#include<scil/scil.h>
#include<scil/constraints/spantree.h>
#include<scil/constraints/stronglyconnected.h>
#include<LEDA/graph.h>
#include<LEDA/graphwin.h>
#include<LEDA/graph_alg.h>
#include<LEDA/graph_misc.h>
#include<LEDA/delaunay.h>
#include<LEDA/string.h>
#include<LEDA/node_pq.h>
#include<LEDA/stream.h>

using namespace LEDA;
using namespace SCIL;
using namespace std;

#define MAX_DOUBLE 10e+300
#define MAX_INT 1000000

#include"sym_connect.c"
#include"asym_connect.c"

void triang_points(GraphWin& GW) 
{
  graph& G=GW.get_graph();
  int n=G.number_of_nodes();
  if (n!=0) {
  
    GW.set_flush(false);

    point_set T;  
    node_array<node> tr(T,n,nil);
    node_array<int> num(T,n,0);
    node v,v1;
    int i=0;

    double x,y;
    forall_nodes(v1,G) 
    {
      x=GW.get_position(v1).xcoord();
      y=GW.get_position(v1).ycoord();
      point p(x,y);
      v=T.insert(p);
      tr[v]=v1;
      num[v]=i++;
     }

    G.del_all_edges();
    GW.update_graph();
    edge e;
    forall_edges(e,T) if (num[T.source(e)]<num[T.target(e)])
                        GW.new_edge(tr[T.source(e)],tr[T.target(e)]);
    GW.redraw();
    GW.set_flush(true);
    GW.redraw();
  }
}

void complete_points(GraphWin& GW) 
{
  graph& G=GW.get_graph();
  int n=G.number_of_nodes();
  if (n!=0) {
  
    GW.set_flush(false);

    G.del_all_edges();

    node u, v;
    forall_nodes(u, G) forall_nodes(v,G) if(u>v) {
      G.new_edge(u,v);
    };

    GW.update_graph();

    GW.redraw();
    GW.set_flush(true);
    GW.redraw();
  }
}

void generate_del(GraphWin& GW) 
{
  graph& G=GW.get_graph();
  if (!G.empty()) GW.clear_graph();

  int n=10;

  panel p;
  p.int_item("Number of nodes : ",n);
  p.open(GW.get_window());
 
  random_source ran;

  double x,y;
  for(int i=0;i<n;i++) 
  { ran >> x >> y;
    x=(x+0.08)*(GW.get_xmax()-GW.get_xmin())*0.9+GW.get_xmin();
    y=(y+0.08)*(GW.get_ymax()-GW.get_ymin())*0.9+GW.get_ymin();
    point p1(x,y);
    GW.new_node(p1);
   }
  triang_points(GW);
}



void make_tests(GraphWin& GW) {

  ofstream tr("test_results");
  double x,y;
  edge e;
  list<edge> T;
  int i=4;
  int j=0;
  int l;
  
  while(i<6) {
    while(j<10) {

      graph G;

      LEDA::string s("random_%d_%d.pts",i*5,j);

      cout<<"Instance: "<<s<<endl;

      ifstream outp(s);
      outp>>l;

      node_map<point> P(G);
      node u,v;

      node_map<int> N(G);

      //GW.clear_graph();
      for(int k=0; k<i*5; k++) {
        outp >> x;
        outp >> y;
        //x=(x+0.08)*(GW.get_xmax()-GW.get_xmin())*0.9+GW.get_xmin();
        //y=(y+0.08)*(GW.get_ymax()-GW.get_ymin())*0.9+GW.get_ymin();
        point p1(x,y);
        u=G.new_node();
        P[u]=p1;
        N[u]=k;
      }

#define COMPLETE_GRAPH

      #ifdef COMPLETE_GRAPH
      // COMPLETE GRAPH
      forall_nodes(u,G) forall_nodes(v, G) if(u>v) {
        G.new_edge(u,v);
      };
      #else
      // DELAUNAY GRAPH
      point_set TD;  
      node_array<node> tr(TD,G.number_of_nodes(),u);
      node v1;

      forall_nodes(v1,G) {
        v=TD.insert(P[v1]);
        tr[v]=v1;
      }

      forall_edges(e,TD) if (source(e)<target(e))
        G.new_edge(tr[source(e)],tr[target(e)]);
      #endif

      edge_array<double> Cost(G);
      forall_edges(e, G) { 
        Cost[e]=P[source(e)].distance(P[target(e)]); 
      }

      ComputeBroadcast(G, Cost, T, GW);
      LEDA::string so("random_%d_%d.opt",i*5,j);
      ofstream opts(so);
      opts<<"p edges "<<G.number_of_nodes()<<" "<<T.size()<<endl;
      forall(e, T) opts<<"e "<<N[source(e)]<<" "<<N[target(e)]<<" "<<Cost[e]<<endl;
      T.clear();

      list<edge> MST=MIN_SPANNING_TREE(G, Cost);
      LEDA::string sm("random_%d_%d.mst",i*5,j);
      ofstream msts(sm);
      msts<<"p edges "<<G.number_of_nodes()<<" "<<T.size()<<endl;
      forall(e, MST) msts<<"e "<<N[source(e)]<<" "<<N[target(e)]<<" "<<Cost[e]<<endl;

      if(x<0) for(;;);
      j++;
    };
    i++; j=0;
  };
};

void make_instances(GraphWin& GW) {

  random_source RS;
  double x,y;

  int i=9;
  int j=0;
  
  while(i<21) {
    while(j<50) {

      graph G;

      LEDA::string s("random_%d_%d.pts",i*5,j);

      cout<<"Instance: "<<s<<endl;

      ofstream outp(s);
      outp<<i*5<<endl;

      for(int k=0; k<i*5; k++) {
        RS>>x;
        RS>>y;
        outp << ((int) (x*10000)) <<" ";
        outp << ((int) (y*10000)) <<endl;
      }
      j++;
    };
    i++; j=0;
  };
};

void read_graph(GraphWin& GW) {
  cout<<"File Name : ";
  LEDA::string s;
  cin>>s;

  ifstream inp(s);
  int i,x,y;
  inp>>i;
  cout<<i<<endl;

  for(int j=0; j<i; j++) {
    inp>>x;
    inp>>y;
    cout<<x<<" "<<y<<endl;
    GW.new_node(point(x,y));
  };
  cout<<"reading done\n";
}


int main()
{
  GraphWin GW;

// Setup of the graph window
  GW.set_node_width(8);
  GW.set_node_height(8);
  GW.set_flush(true);
  GW.set_edge_direction(undirected_edge);

// Additional functionality of the graph window; the implementation is hidden
  int gn=gw_add_menu(GW,"Generation");
  gw_add_simple_call(GW,triang_points,"Triangulate defined points",gn);
  gw_add_simple_call(GW,complete_points,"Make complete graph",gn);
  gw_add_simple_call(GW,generate_del, "Generate random Delaunay-Graph",gn);
  gw_add_simple_call(GW,make_tests, "Make Test", gn);
  gw_add_simple_call(GW,make_instances, "Make Instances", gn);
  gw_add_simple_call(GW,read_graph, "Read Graph", gn);

  GW.display();

  while(GW.edit())
  {
    graph& G=GW.get_graph();

    edge e;
    edge_array<double> C(G);
    forall_edges(e, G) 
      C[e]=GW.get_position(source(e)).distance(GW.get_position(target(e)));

    list<edge> T;
    ComputeBroadcast(G, C, T, GW);

    node_array<double> W(G,0);
    forall(e, T) { 
      W[source(e)]=leda_max(W[source(e)], C[e]);
      W[target(e)]=leda_max(W[target(e)], C[e]);
    };

    forall_edges(e,G) {
      GW.set_color(e, black);
      if((C[e]<=W[source(e)]) && (C[e]<=W[target(e)]))
        GW.set_color(e,red);
    }
    
    node u;
    forall_nodes(u, G) {
      GW.get_window().draw_circle(GW.get_position(u), W[u], green);
    };
  }
  return 0;
}

---