home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / ledar34.zip / leda-r-3_4_tar / LEDA-3.4 / demo / graph / plan_demo.c < prev   
C/C++ Source or Header  |  1996-09-03  |  9KB  |  404 lines
  1. #include <math.h>
  2. #include <LEDA/graph.h>
  3. #include <LEDA/graph_alg.h>
  4. #include <LEDA/window.h>
  5. #include <LEDA/graph_edit.h>
  6.  
  7.  
  8. static int select_alg = 0;
  9.  
  10. bool PLAN_TEST(graph& G, bool embed)
  11. { switch (select_alg) {
  12.   case 0: return PLANAR(G,embed);
  13.   case 1: return PLANAR0(G,embed);
  14.   }
  15.   return false;
  16. }
  17.  
  18. bool PLAN_TEST(graph& G, list<edge>& P, bool embed)
  19. { switch (select_alg) {
  20.   case 0: return PLANAR(G,P,embed);
  21.   case 1: return PLANAR0(G,P,embed);
  22.   }
  23.   return false;
  24. }
  25.  
  26.  
  27.  
  28. void circular_embedding(GRAPH<point,int>& G, int x, int y, int radius)
  29. { int n = G.number_of_nodes();
  30.   float ang = 0;
  31.   node v;
  32.   forall_nodes(v,G)
  33.   { G[v] = point(x+radius*sin(ang),y+radius*cos(ang));
  34.     ang += 6.283/n;
  35.   }
  36. }
  37.  
  38. void grid_embedding(GRAPH<point,int>& G, int c0, int c1)
  39. { double n = G.number_of_nodes();
  40.   int l = int(sqrt(n+1));
  41.   int d = (c1-c0)/l;
  42.   int i = 0;
  43.   node v;
  44.   forall_nodes(v,G)
  45.   { int row = i/l;
  46.     int col = i%l;
  47.     G[v] = point(c0+col*d ,c0+row*d);
  48.     i++;
  49.    }
  50. }
  51.   
  52.  
  53. void random_embedding(GRAPH<point,int>& G, int c0, int c1)
  54. { int n = G.number_of_nodes();
  55.   random_source ran(c0,c1);
  56.   node v;
  57.   forall_nodes(v,G)
  58.   { int x,y;
  59.     ran >> x >> y;
  60.     G[v] = point(x,y);
  61.    }
  62. }
  63.   
  64.  
  65. void draw_graph(const GRAPH<point,int>& G, window& W, bool numbering=false)
  66. { node v;
  67.   edge e;
  68.  
  69.   if (numbering)
  70.      { int i = 0;
  71.        forall_nodes(v,G) W.draw_int_node(G[v],i++,red);
  72.       }
  73.   else
  74.      forall_nodes(v,G) W.draw_filled_node(G[v],red);
  75.  
  76.   forall_edges(e,G)
  77.     W.draw_edge(G[source(e)],G[target(e)],blue);
  78. }
  79.  
  80.  
  81. void draw_graph(const GRAPH<point,int>& G, window& W, 
  82.                 const node_array<double>& xc, const node_array<double>& yc,
  83.                 const node_array<double>& dx, const node_array<double>& dy)
  84. { node v;
  85.  
  86.   forall_nodes(v,G) W.draw_filled_node(xc[v]+dx[v],yc[v]+dy[v],red);
  87.  
  88.   edge e;
  89.   forall_edges(e,G)
  90.   { node v = source(e);
  91.     node w = target(e);
  92.     W.draw_edge(xc[v]+dx[v],yc[v]+dy[v],xc[w]+dx[w],yc[w]+dy[w],blue);
  93.    }
  94. }
  95.  
  96. void draw_graph(const GRAPH<point,int>& G, window& W, 
  97.                 const node_array<double>& xc, const node_array<double>& yc)
  98. { node v;
  99.  
  100.   forall_nodes(v,G) W.draw_filled_node(xc[v],yc[v],red);
  101.  
  102.   edge e;
  103.   forall_edges(e,G)
  104.   { node v = source(e);
  105.     node w = target(e);
  106.     W.draw_edge(xc[v],yc[v],xc[w],yc[w],blue);
  107.    }
  108. }
  109.  
  110.  
  111.  
  112.  
  113. void move_graph(window& W, GRAPH<point,int>& G, 
  114.                            node_array<double>& xc,
  115.                            node_array<double>& yc, int speed)
  116. {
  117.   node_array<double> dx(G);
  118.   node_array<double> dy(G);
  119.   int d = 400/speed;
  120.  
  121.   W.clear();
  122.  
  123.   W.set_mode(xor_mode);
  124.  
  125.   draw_graph(G,W);
  126.  
  127.  
  128.   node v;
  129.   forall_nodes(v,G) 
  130.   { dx[v] = (xc[v] - G[v].xcoord())/d;
  131.     dy[v] = (yc[v] - G[v].ycoord())/d;
  132.     xc[v] = G[v].xcoord();
  133.     yc[v] = G[v].ycoord();
  134.    }
  135.  
  136.   while(d--)
  137.   { draw_graph(G,W,xc,yc,dx,dy);
  138.     draw_graph(G,W,xc,yc);
  139.     forall_nodes(v,G) 
  140.     { xc[v] += dx[v];
  141.       yc[v] += dy[v];
  142.      }
  143.    }
  144.  
  145.   W.set_mode(src_mode);
  146.  
  147. }
  148.  
  149.  
  150.  
  151. int main()
  152. {
  153.  
  154. panel P("LEDA Planarity Test Demo");
  155.  
  156. P.text_item("");
  157. P.text_item("This demo illustrates planarity testing and straight-line");
  158. P.text_item("embedding. You have two ways to construct a graph: either");
  159. P.text_item("interactively by using the LEDA graph editor or by calling");
  160. P.text_item("one of two graph generators. The first generator constructs");
  161. P.text_item("a random graph with a certain number of nodes and edges and");
  162. P.text_item("the second constructs a planar graph with a certain number");
  163. P.text_item("of nodes by intersecting random lines in the unit square");
  164. P.text_item("");
  165. P.text_item("The graph is displayed and then tested for planarity. If it");
  166. P.text_item("is planar a straight-line drawing is produced, otherwise, a");
  167. P.text_item("Kuratowski subgraph is highlighted.");
  168. P.button("continue");
  169.  
  170. P.open();
  171.  
  172. window W;
  173.  
  174. GRAPH<point,int>G;
  175. node v,w;
  176. edge e;
  177.  
  178. int n = 30;
  179. int m = 40;
  180. int init_embed = 2;
  181. int final_embed = 0;
  182. int speed = 0;
  183.  
  184.  
  185. panel P1("PLANARITY TEST");
  186.  
  187. P1.text_item("The first slider asks for the number n of nodes and the second");
  188. P1.text_item("slider asks for the number m of edges. If you select the random");
  189. P1.text_item("button then a graph with n nodes and m edges is constructed, if");
  190. P1.text_item("you select the planar button then a set of random line segments");
  191. P1.text_item("is chosen and intersected to yield a planar graph with about n");
  192. P1.text_item("n nodes, and if you select the edit button the graph editor is");
  193. P1.text_item("called.");
  194. P1.text_item(" ");
  195.  
  196. P1.int_item("number of nodes",n,0,300);
  197. P1.int_item("number of edges",m,0,300);
  198. P1.choice_item("initial embedding",init_embed,"random","grid","circular");
  199. P1.choice_item("final embedding",final_embed,"fary","schnyder");
  200. P1.choice_item("planarity teset",select_alg,"[BL76]","[HT74]");
  201. P1.int_item("animation speed",speed,0,20);
  202.  
  203. P1.button("random",0);
  204. P1.button("planar",1);
  205. P1.button("triang",2);
  206. P1.button("edit",3);
  207. P1.button("repeat",4);
  208. P1.button("quit",5);
  209.  
  210. int inp = 0;
  211.  
  212. for(;;) 
  213. {
  214.   if (inp != 4 || W.get_button() != NO_BUTTON)  inp = P1.open(W);
  215.  
  216.   if (inp == 5) break;   // quit button pressed
  217.  
  218.   W.init(-50,950,-50);
  219.   W.set_node_width(4);
  220.  
  221.   G.clear();
  222.  
  223.   switch(inp) {
  224.  
  225.   case 4:
  226.   case 0: { random_graph(G,n,m);
  227.             eliminate_parallel_edges(G);
  228.             list<edge> Del;
  229.             forall_edges(e,G) 
  230.                if (source(e)==target(e)) Del.append(e);
  231.             forall(e,Del) G.del_edge(e);
  232.             break;
  233.            }
  234.   
  235.   case 1:  random_planar_graph(G,n);
  236.            break;
  237.  
  238.   case 2:  triangulated_planar_graph(G,n);
  239.            break;
  240.  
  241.   case 3:  W.set_node_width(7);
  242.            graph_edit(W,G,false);
  243.            break;
  244.   
  245.    }
  246.   
  247.    if (inp != 3)
  248.    { if (init_embed == 0) random_embedding(G,0,850);
  249.      if (init_embed == 1) grid_embedding(G,0,850);
  250.      if (init_embed == 2) circular_embedding(G,450,400,350);
  251.      draw_graph(G,W);
  252.     }
  253.  
  254.   G.write("graph.ggg");
  255.  
  256.   
  257.   if (PLAN_TEST(G,false))
  258.   { 
  259.     if(G.number_of_nodes()<4)
  260.         W.message("That's an insult: Every graph with |V| <= 4 is planar");
  261.     else
  262.       { 
  263.         W.message("G is planar. I compute a straight-line embedding ...");
  264.  
  265.         // first make graph biconnected and bidirected
  266.  
  267.         list<edge> bi_edges = Make_Biconnected(G);
  268.         list<edge> rev_edges = Make_Bidirected(G);
  269.  
  270.         PLAN_TEST(G,true);
  271.   
  272.         node_array<int> xcoord(G);
  273.         node_array<int> ycoord(G);
  274.  
  275.         float fx = 900.0/G.number_of_nodes();
  276.         float fy = fx;
  277.  
  278.         // currently, our embedding programs cannot embed multi-graphs
  279.  
  280.         //Make_Simple(G);
  281.   
  282.         if (final_embed == 0)
  283.           { STRAIGHT_LINE_EMBEDDING(G,xcoord,ycoord);
  284.             fx /= 2;
  285.            }
  286.         else
  287.             STRAIGHT_LINE_EMBEDDING2(G,xcoord,ycoord);
  288.  
  289.  
  290.         // restore original graph
  291.  
  292.         edge e;
  293.         forall(e,rev_edges) G.del_edge(e);
  294.         forall(e,bi_edges)  G.del_edge(e);
  295.  
  296.  
  297.         // display embedding
  298.  
  299.         node_array<double> xc(G);
  300.         node_array<double> yc(G);
  301.  
  302.         forall_nodes(v,G) 
  303.         { xc[v] = fx*xcoord[v];
  304.           yc[v] = fy*ycoord[v];
  305.          }
  306.  
  307.         if (speed > 0) // animate
  308.           { W.message("click any button");
  309.             if (inp != 4) W.read_mouse();
  310.             move_graph(W,G,xc,yc,speed);
  311.            }
  312.          else
  313.           { forall_nodes(v,G) G[v] = point(xc[v],yc[v]);
  314.             W.clear();
  315.             draw_graph(G,W);
  316.            }
  317.       }
  318.    }
  319.   else
  320.     { 
  321.       W.message("Graph is not planar. I compute the Kuratowski subgraph ...");
  322.  
  323.       list<edge> L;
  324.       node v;
  325.       edge e;
  326.  
  327.       PLAN_TEST(G,L,false);
  328.  
  329.  
  330.       // display Kuratowski subdivision with edge set L
  331.  
  332.       edge_array<bool> marked(G,false);
  333.  
  334.       forall(e,L) marked[e] = true;
  335.  
  336.       list<edge> el = G.all_edges();
  337.  
  338.       forall(e,el) 
  339.         if (!marked[e]) G.del_edge(e);
  340.  
  341.       G.make_undirected();
  342.  
  343.       int lw = W.set_line_width(3);
  344.  
  345.       forall_edges(e,G) W.draw_edge(G[source(e)],G[target(e)]);
  346.  
  347.       bool K33 = false;
  348.       forall_nodes(v,G) 
  349.       if (G.degree(v) == 3)
  350.       { K33 = true;
  351.         break; 
  352.        }
  353.  
  354.       node_array<int>  side(G,0);
  355.  
  356.       if (K33)
  357.       { // find sides of the K33
  358.         forall_adj_edges(e,v) // scan paths to the other side 
  359.         { edge x = e;
  360.           node w = G.opposite(v,e); 
  361.           while (G.degree(w) == 2) 
  362.           { x = G.cyclic_adj_succ(x,w); 
  363.             w = G.opposite(w,x);
  364.            }
  365.           side[w] = 1;
  366.          }
  367.         }
  368.         
  369.       int i = 0;
  370.  
  371.       forall_nodes(v,G) 
  372.       { 
  373.         if (G.degree(v) == 2) W.draw_filled_node(G[v],black);
  374.  
  375.         if (G.degree(v) > 2)
  376.         { int nw = W.set_node_width(7);
  377.           i++;
  378.           if (side[v]==0)
  379.              W.draw_int_node(G[v],i,green);
  380.           else
  381.              W.draw_int_node(G[v],i+3, W.mono() ? white : violet);
  382.           W.set_node_width(nw);
  383.          }
  384.       }
  385.  
  386.       W.set_line_width(lw);
  387.  
  388.       G.make_directed();
  389.    }
  390.  
  391.    W.set_show_coordinates(false);
  392.    if (inp != 4)
  393.    { W.set_frame_label("click any button to continue");
  394.      W.read_mouse();
  395.     }
  396.    W.reset_frame_label();
  397.    W.set_show_coordinates(true);
  398.  
  399.  } //  Main Loop
  400.  
  401. return 0;
  402.  
  403. }
  404.