Hierarchical Index

00001 #include<LEDA/graph.h>
00002 #include<LEDA/graphwin.h>
00003 #include<LEDA/graph_misc.h>
00004 #include<LEDA/delaunay.h>
00005 
00006 using namespace LEDA;
00007 
00008 #include"compute_tour.c"
00009 
00010 void triang_points(GraphWin& GW) 
00011 {
00012   graph& G=GW.get_graph();
00013   int n=G.number_of_nodes();
00014   if (n!=0) {
00015   
00016     GW.set_flush(false);
00017 
00018     point_set T;  
00019     node_array<node> tr(T,n,nil);
00020     node_array<int> num(T,n,0);
00021     node v,v1;
00022     int i=0;
00023 
00024     double x,y;
00025     forall_nodes(v1,G) 
00026     {
00027       x=GW.get_position(v1).xcoord();
00028       y=GW.get_position(v1).ycoord();
00029       point p(x,y);
00030       v=T.insert(p);
00031       tr[v]=v1;
00032       num[v]=i++;
00033      }
00034 
00035     G.del_all_edges();
00036     GW.update_graph();
00037     edge e;
00038     forall_edges(e,T) if (num[T.source(e)]<num[T.target(e)])
00039                         GW.new_edge(tr[T.source(e)],tr[T.target(e)]);
00040     GW.redraw();
00041     GW.set_flush(true);
00042     GW.redraw();
00043   }
00044 }
00045 
00046 void generate_del(GraphWin& GW) 
00047 {
00048   GW.set_flush(false);
00049   graph& G=GW.get_graph();
00050   if (!G.empty()) GW.clear_graph();
00051 
00052   int n=10;
00053 
00054   panel p;
00055   p.int_item("Number of nodes : ",n);
00056   p.open(GW.get_window());
00057  
00058   random_source ran;
00059 
00060   double x,y;
00061   for(int i=0;i<n;i++) 
00062   { ran >> x >> y;
00063     x=(x+0.08)*(GW.get_xmax()-GW.get_xmin())*0.9+GW.get_xmin();
00064     y=(y+0.08)*(GW.get_ymax()-GW.get_ymin())*0.9+GW.get_ymin();
00065     point p1(x,y);
00066     GW.new_node(p1);
00067    }
00068   triang_points(GW);
00069 
00070   GW.set_flush(true);
00071   GW.redraw();
00072 }
00073 
00074 int main()
00075 {
00076   GraphWin GW;
00077 
00078 // Setup of the graph window
00079   GW.set_node_width(8);
00080   GW.set_node_height(8);
00081   GW.set_flush(true);
00082   GW.set_edge_direction(undirected_edge);
00083 
00084 // Additional functionality of the graph window; the implementation is hidden
00085   int gn=gw_add_menu(GW,"Generation");
00086   gw_add_simple_call(GW,triang_points,"Triangulate defined points",gn);
00087   gw_add_simple_call(GW,generate_del, "Generate random Delaunay-Graph",gn);
00088 
00089   GW.display();
00090 
00091   while(GW.edit())
00092   {
00093     graph& G=GW.get_graph();
00094 
00095     edge e;
00096     edge_array<double> C(G);
00097     forall_edges(e, G) 
00098       C[e]=GW.get_position(source(e)).distance(GW.get_position(target(e)));
00099 
00100     list<edge> T;
00101     ComputeTour(G, C, T);
00102 
00103     GW.set_flush(false);
00104     forall_edges(e,G) {
00105       GW.set_color(e, black);
00106     }
00107     forall(e,T) { 
00108       GW.set_color(e,red);
00109     }
00110     GW.set_flush(true);
00111     GW.redraw();
00112   }
00113   return 0;
00114 }
gtsp.c
