dmst.c

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

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

#include"compute_dmst.c"

void make_complete(GraphWin& GW) {
  GW.set_flush(false);
  graph& G=GW.get_graph();

  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 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 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()
{
  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,generate_del, "Generate random Delaunay-Graph",gn);
  gw_add_simple_call(GW,make_complete, "Make Complete Graph", gn);

  GW.display();

  while(GW.edit())
  {
    make_complete(GW);

    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;
    ComputeDMST(G, C, T);

    GW.set_flush(false);
    forall_edges(e,G) {
      GW.set_color(e, black);
    }
    forall(e,T) { 
      GW.set_color(e,red);
    }
    forall_edges(e,G) if(GW.get_color(e)==black) {
      GW.del_edge(e);
    }
    GW.redraw();
    GW.set_flush(true);
  }
  return 0;
}

---