steiner.c

#include<LEDA/graph.h>
#include<LEDA/graphwin.h>
#include<LEDA/graph_misc.h>
#include<LEDA/delaunay.h>
#include<LEDA/stream.h>
#include<LEDA/string.h>

using namespace LEDA;
using namespace std;

#include"compute_steiner.c"

double string_to_double(const LEDA::string& s) {
  LEDA::string_istream s1(s.cstring()); //, s.length());
  double d;
  s1>>d;
  return d;
};

void clear_nonred(GraphWin& GW) {
  edge e;
  GW.set_flush(false);
  forall_edges(e, GW.get_graph()) if(GW.get_color(e)!=red)
    GW.del_edge(e);

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


void read_steinlib(GraphWin& GW, LEDA::string& s) {
  int n, i, j, k;

  ifstream ifs(s);
  node* N;
  node lastterm;
  edge e;

  while(!ifs.eof()) {
    s.read_line(ifs);

    if(s.head(5)=="Nodes") {
      n=string_to_double(s.del(0,5));
      cout<<n<<" Nodes\n";
      N=new node[n];
      for(i=0; i<n; i++) {
        N[i]=GW.new_node(point(10*i,0));
      };
    };
    if(s.head(2)=="E ") {
      LEDA::string s1=s.del(0,1);
      string_istream is(s1); //,s1.length());
      is>>i;
      is>>j;
      LEDA::string s2;
      is>>s2;
      e=GW.new_edge(N[i-1],N[j-1]);
      GW.set_label(e, s2);
      e=GW.new_edge(N[j-1],N[i-1]);
      GW.set_label(e,s2);
    };
    if(s.head(2)=="A ") {
      LEDA::string s1=s.del(0,1);
      string_istream is(s1); //,s1.length());
      is>>i;
      is>>j;
      LEDA::string s2;
      is>>s2;
      if(s2!="1000000000") {
        e=GW.new_edge(N[i-1],N[j-1]);
        GW.set_label(e, s2);
      };
      is>>s2;
      if(s2!="1000000000") {
        e=GW.new_edge(N[j-1],N[i-1]);
        GW.set_label(e,s2);
      }
    };
    if(s.head(2)=="T ") {
      i=string_to_double(s.del(0,1));
      GW.set_color(N[i-1], red);
      lastterm=N[i-i];
    };
    if(s.head(3)=="DD ") {
      LEDA::string s1=s.del(0,2);
      string_istream is(s1); //,s1.length());
      is>>i;
      is>>j;
      is>>k;
      GW.set_position(N[i-1],point(j,k));
    };
  };

  node u;
  double xM,yM,xm,ym;
  bool haveroot=false;
  xM=-1e200;yM=-1e200; xm=1e200; ym=1e200;
  forall_nodes(u, GW.get_graph()) {
    xM=leda_max(xM,GW.get_position(u).xcoord());
    yM=leda_max(yM,GW.get_position(u).ycoord());
    xm=leda_min(xm,GW.get_position(u).xcoord());
    ym=leda_min(ym,GW.get_position(u).ycoord());
    if((GW.get_graph().indeg(u)==0)) {
      GW.set_color(u,green);
      haveroot=true;
      cout<<"Declare a root\n";
    };
  }

  if(haveroot==false) {
      GW.set_color(lastterm, green);
      cout<<"Declare last terminal as root\n";
  };

  double d=GW.get_xmax()/xM;
  d=leda_min(d, GW.get_ymax()/yM);

  forall_nodes(u,GW.get_graph()) {
    GW.set_position(u,point(GW.get_position(u).xcoord()*d, 
                            GW.get_position(u).ycoord()*d));
  };

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

void read_steinlib(GraphWin& GW) {
  GW.set_flush(false);
  cout<<"Filename : ";
  LEDA::string s;
  cin>>s;

  read_steinlib(GW, s);
};


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) 
      GW.new_edge(tr[T.source(e)],tr[T.target(e)]);
    GW.redraw();
    //  GW.set_flush(true);
    //GW.redraw();
  }
}

void node_handler(GraphWin&GW, const point& p) {
  graph& G=GW.get_graph();
  node v,u=G.first_node();

  forall_nodes(v, G) {
    if(GW.get_position(v).distance(p)<GW.get_position(u).distance(p))
      u=v;
  };

  if(GW.get_color(u)==red) GW.set_color(u, green);
  else {
    if(GW.get_color(u)==green) GW.set_color(u, white);
    else GW.set_color(u, red);
  }
  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);
}

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

  GraphWin GW;

// Setup of the graph window
  GW.set_node_width(12);
  GW.set_node_height(12);
  GW.set_flush(false);
  GW.set_node_color(white);
  GW.set_node_label_type(no_label);
  GW.set_edge_direction(directed_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,generate_del, "Generate random Delaunay-Graph",gn);
  gw_add_simple_call(GW,read_steinlib, "Read Steinlib Graph", gn);
  gw_add_simple_call(GW,clear_nonred, "Remove all black edges", gn);

  GW.set_action(A_LEFT |A_NODE | A_CTRL, node_handler);

  GW.display();

  if(argc==2) {
      LEDA::string s=argv[1];
      read_steinlib(GW, s);
      graph& G=GW.get_graph();

      edge e;
      edge_array<double> C(G);
      forall_edges(e, G) 
          C[e]=string_to_double(GW.get_label(e));
      
      node_array<bool> R(G, false);
      node u, r;
      forall_nodes(u, G) {
          if(GW.get_color(u)==red) R[u]=true;
          if(GW.get_color(u)==green) r=u;
      };

      list<edge> T;
      ComputeSteinerTree(G, C, r, R, T);

      return 0;
  };

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

    cout<<"l\n";

    edge e;
    edge_array<double> C(G);
    forall_edges(e, G) 
      C[e]=string_to_double(GW.get_label(e));

    cout<<"t\n";

    node_array<bool> R(G, false);
    node u, r;
    forall_nodes(u, G) {
      if(GW.get_color(u)==red) R[u]=true;
      if(GW.get_color(u)==green) r=u;
    };

    cout<<"HERE\n";

    list<edge> T;
    ComputeSteinerTree(G, C, r, R, T);

    forall_edges(e,G) {
      GW.set_color(e, black);
    }
    forall(e,T) { 
      GW.set_color(e,red);
    }
    GW.redraw();
  }
  return 0;
}

---