开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
graph_alg.c
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：8k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

graph_alg.c：源码内容
  1. #include <LEDA/ugraph.h>
  2. #include <LEDA/graph_alg.h>
  3. #include <LEDA/graph_edit.h>
  4. #include <math.h>
  8. window W;
  9. //window w1(440,440,0,125);
  11. void bold_edge(GRAPH<point,int>& G, edge e)
  12. { point p = G[source(e)];
  13.   point q = G[target(e)];
  14.   W.set_mode(xor_mode);
  15.   W.draw_edge_arrow(p,q,blue);
  16.   int save = W.set_line_width(5);
  17.   W.draw_edge(p,q,blue);
  18.   W.set_line_width(save);
  19.   W.set_mode(src_mode);
  20. }
  22. void unbold_edge(GRAPH<point,int>& G, edge e)
  23. { int save = W.set_line_width(5);
  24.   point p = G[source(e)];
  25.   point q = G[target(e)];
  26.   W.set_mode(xor_mode);
  27.   W.draw_edge(p,q,blue);
  28.   W.set_line_width(save);
  29.   W.draw_edge_arrow(p,q,blue);
  30.   W.set_mode(src_mode);
  31. }
  33. void show_edge_inf(GRAPH<point,int>& G, edge_array<int>& edge_num)
  34. { edge e;
  35.   W.set_mode(xor_mode);
  36.   forall_edges(e,G)
  37.   { point p = G[source(e)];
  38.     point q = G[target(e)];
  39.     W.draw_text((p.xcoord()+q.xcoord())/2, (p.ycoord()+q.ycoord())/2,
  40.                   string("%d", edge_num[e]));
  41.    }
  42.   W.set_mode(src_mode);
  43.  }
  45. void show_edge_inf(UGRAPH<point,int>& G, edge_array<int>& edge_num)
  46. { edge e;
  47.   W.set_mode(xor_mode);
  48.   forall_edges(e,G)
  49.   { point p = G[source(e)];
  50.     point q = G[target(e)];
  51.     W.draw_text((p.xcoord()+q.xcoord())/2, (p.ycoord()+q.ycoord())/2,
  52.                   string("%d", edge_num[e]));
  53.    }
  54.   W.set_mode(src_mode);
  55.  }
  58. void show_node_inf(UGRAPH<point,int>& G, node_array<int>& node_num)
  59. { node v;
  60.   forall_nodes(v,G)
  61.     W.draw_int_node(G[v],node_num[v],violet);
  62. }
  64. void show_node_inf(GRAPH<point,int>& G, node_array<int>& node_num)
  65. { node v;
  66.   forall_nodes(v,G)
  67.      W.draw_int_node(G[v],node_num[v],violet);
  68. }
  70. void show_two_node_inf(GRAPH<point,int>& G, node_array<int>& node_num1,
  71.                                             node_array<int>& node_num2)
  72. { node v;
  73.   forall_nodes(v,G)
  74.   { string s("%d|%d",node_num1[v],node_num2[v]);
  75.     W.draw_text_node(G[v],s);
  76.    }
  77. }
  79. void draw_graph(GRAPH<point,int>& G) 
  80. { node v,w;
  81.   int i = 0;
  82.   forall_nodes(v,G)
  83.    { W.draw_int_node(G[v],i++,yellow);
  84.      forall_adj_nodes(w,v)
  85.         W.draw_edge_arrow(G[v],G[w],blue);
  86.     }
  87. }
  89. void draw_graph(UGRAPH<point,int>& G) 
  90. { node v,w;
  91.   int i = 0;
  92.   forall_nodes(v,G)
  93.    { W.draw_int_node(G[v],i++,yellow);
  94.      forall_adj_nodes(w,v)
  95.         W.draw_edge(G[v],G[w],blue);
  96.     }
  97. }
  100. void generate_graph(GRAPH<point,int>& G)
  101. {
  102.   panel P_gen;
  104.   int n = 0;
  105.   int m = 0;
  107.   P_gen.int_item("# nodes", n);
  108.   P_gen.int_item("# edges", m);
  110.   P_gen.button("random");
  111.   P_gen.button("complete");
  112.   P_gen.button("bi_random");
  113.   P_gen.button("bi_complete");
  115.   list<node> A,B;
  116.   node v;
  118.   int xmin = (int)W.xmin();
  119.   int ymin = (int)W.ymin();
  120.   int xmax = (int)W.xmax();
  121.   int ymax = (int)W.ymax();
  123.   int i = P_gen.open();
  125.   switch(i)
  126.   {
  127.     case 0: random_graph(G,n,m);
  128.             break;
  129.     case 1: complete_graph(G,n);
  130.             break;
  132.     case 2: random_bigraph(G,n,n,m,A,B);
  133.             break;
  135.     case 3: complete_bigraph(G,n,n,A,B);
  136.             break;
  137.    }
  139.    if (i > 1)
  140.       { double dy = (ymax-ymin)/(n+1);
  141.         double y = ymin + dy;
  142.         forall(v,A) 
  143.         { G[v] = point(xmin + (xmax-xmin)/4,y);
  144.           y += dy;
  145.          }
  146.         y = ymin + dy;
  147.         forall(v,B) 
  148.         { G[v] = point(xmax - (xmax-xmin)/4,y);
  149.           y += dy;
  150.          }
  151.         }
  152.     else // circular embedding 
  153.        { double R  = (xmax-xmin)/2.5;
  154.          double x0 = (xmax-xmin)/2;
  155.          double y0 = (ymax-ymin)/2;
  156.          point  M(x0,y0);
  157.          double alpha = 0;
  158.          double step  = 2*LEDA_PI/n;
  159.          forall_nodes(v,G)  
  160.          { G[v] = M.translate(alpha,R);
  161.            alpha+=step;
  162.           }
  163.         }
  165. }
  168. main()
  169. {
  170.   panel P("Graph Algorithms");
  172.   list<string> alg_menu;
  173.   alg_menu.append(string("topsort"));
  174.   alg_menu.append(string("dfsnum"));
  175.   alg_menu.append(string("components"));
  176.   alg_menu.append(string("strongcomp"));
  177.   alg_menu.append(string("bicomp"));
  178.   alg_menu.append(string("matching"));
  180.   string alg = alg_menu.head();
  182.   P.string_item("algorithm", alg, alg_menu);
  183.   P.button("file");   // 0
  184.   P.button("gen");    // 1
  185.   P.button("edit");   // 2
  186.   P.button("run");    // 3
  187.   P.button("quit");   // 4
  189.   P.display(0,0);
  191.   string file      = "graph.1";
  193.   panel file_panel("FILE PANEL");
  194.   file_panel.string_item("file", file);
  195.   file_panel.button("load");
  196.   file_panel.button("save");
  198.   GRAPH<point,int>  G;
  199.   edge e;
  201.   for(;;)
  202.   { 
  203.     W.del_messages();
  205.     int key = P.read();
  207.     if (key == 4) break;
  209.     switch(key) 
  210.     {
  211.       case 0: { int b = file_panel.open(); 
  212.                 if (b==0)  // load
  213.                 { W.message(string("loading graph from %s",~file));
  214.                   G.clear();
  215.                   G.read(file);
  216.                   W.clear();
  217.                   draw_graph(G);
  218.                  }
  219.                 if (b==1)  // save
  220.                 { G.write(file);
  221.                   W.message(string("writing graph to %s",~file));
  222.                 }
  223.                 break;
  224.                }
  226.       case 1: G.clear();
  227.               generate_graph(G);
  228.               W.clear();
  229.               draw_graph(G);
  230.               break;
  232.       case 2: { //graph_edit(w1,G);
  233.                 //W.clear();
  234.                 //draw_graph(G);
  235.                 graph_edit(W,G);
  236.                 break;
  237.                }
  239.       case 3: { if (alg == "bicomp")
  240.                 { W.message("BICONNECTED COMPONENTS");
  241.                   UGRAPH<point,int> U = G;
  242.                   edge_array<int> edge_num(U);
  243.                   BICONNECTED_COMPONENTS(U,edge_num);
  244.                   show_edge_inf(U,edge_num);
  245.                   W.read_mouse();
  246.                   show_edge_inf(U,edge_num);
  247.                   break;
  248.                  }
  250.                 if (alg == "dfsnum")
  251.                 { W.message("DFS NUMBERING");
  252.                   node_array<int> dfs_num(G);
  253.                   node_array<int> comp_num(G);
  254.                   DFS_NUM(G,dfs_num,comp_num);
  255.                   show_two_node_inf(G,dfs_num,comp_num);
  256.                   W.read_mouse();
  257.                   draw_graph(G);
  258.                   break;
  259.                  }
  261.                 if (alg == "components")
  262.                 { W.message("COMPONENTS");
  263.                   UGRAPH<point,int> U = G;
  264.                   node_array<int> node_num(U);
  265.                   COMPONENTS(U,node_num);
  266.                   show_node_inf(U,node_num);
  267.                   W.read_mouse();
  268.                   draw_graph(G);
  269.                   break;
  270.                  }
  271.           
  272.                 if (alg == "strongcomp")
  273.                 { W.message("STRONG COMPONENTS");
  274.                   node_array<int> node_num(G);
  275.                   STRONG_COMPONENTS(G,node_num);
  276.                   show_node_inf(G,node_num);
  277.                   W.read_mouse();
  278.                   draw_graph(G);
  279.                   break;
  280.                  }
  282.                 if (alg == "topsort")
  283.                 { W.message("TOPSORT");
  284.                   node_array<int> node_num(G);
  285.                   if (TOPSORT(G,node_num)==false)
  286.                   { W.acknowledge("Graph is cyclic, cannot sort");
  287.                     break;
  288.                    }
  289.                   show_node_inf(G,node_num);
  290.                   W.read_mouse();
  291.                   draw_graph(G);
  292.                   break;
  293.                  }
  295.                 if (alg == "matching")
  296.                 { W.message("MAX_CARD_MATCHING");
  297.                   list<edge> L = MAX_CARD_MATCHING(G);
  298.                   forall(e,L) bold_edge(G,e);       
  299.                   W.read_mouse();
  300.                   forall(e,L) unbold_edge(G,e);       
  301.                   break;
  302.                  }
  304.                 W.acknowledge(alg + " not found");
  305.                 break;
  306.           
  307.               }
  309.     } //switch
  311.   } // for(;;)
  313.   return 0;
  314. }