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

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

数值算法/人工智能

开发平台：

MultiPlatform

_g_generate.c：源码内容
  1. #include <LEDA/array2.h>
  2. #include <LEDA/graph.h>
  3. #include <LEDA/ugraph.h>
  4. #include <ctype.h>
  5. #include <stdlib.h>
  7. // some graph generators
  9. void complete_graph(graph& G, int n)
  10. { node v,w;
  11.   G.clear();
  12.   while (n--) G.new_node();
  13.   forall_nodes(v,G)
  14.      forall_nodes(w,G) 
  15.         G.new_edge(v,w);
  16. }
  18. void complete_ugraph(ugraph& G, int n)
  19. { int i,j;
  20.   node* V = new node[n];
  21.   G.clear();
  22.   for(i=0;i<n;i++) V[i] = G.new_node();
  23.   for(i=0;i<n;i++) 
  24.     for(j=i+1;j<n;j++) 
  25.        G.new_edge(V[i],V[j]);
  26. }
  29. void grid_graph(graph& G, int n) 
  30. { node_array<double> xcoord; 
  31.   node_array<double> ycoord;
  32.   grid_graph(G,xcoord,ycoord,n);
  33.  }
  35. void grid_graph(graph& G, node_array<double>& xcoord, 
  36.                           node_array<double>& ycoord, int n) 
  37. {
  38.   array2<node>  A(n,n);
  39.   node v;
  40.   int N = n*n;
  41.   int x;
  42.   int y;
  44.   double d = 1.0/(n+1);
  46.   G.clear();
  48.   xcoord.init(G,N,0);
  49.   ycoord.init(G,N,0);
  51.   for(y=0; y<n; y++)
  52.     for(x=0; x<n; x++)
  53.       { A(x,y) = v = G.new_node();
  54.         xcoord[v] = (x+1)*d;
  55.         ycoord[v] = (y+1)*d;
  56.        }
  58.   for(x=0; x<n; x++)
  59.     for(y=0; y<n; y++)
  60.        { if (x < n-1) G.new_edge(A(x,y),A(x+1,y));
  61.          if (y < n-1) G.new_edge(A(x,y),A(x,y+1));
  62.         }
  63. }
  66. void complete_bigraph(graph& G, int n1, int n2, list<node>& A, list<node>& B)
  67. { node v,w;
  69.   for(int a=0; a < n1; a++)  A.append(G.new_node());
  70.   for(int b=0; b < n2; b++)  B.append(G.new_node());
  72.   forall(v,A) 
  73.   {  forall(w,B) 
  74.        G.new_edge(v,w);
  75.    }
  76.  }
  78. void user_graph(graph& G)
  79. { int  n = read_int("|V| = ");
  80.   int  i,j;
  82.   node* V = new node[n];
  83.   for(j=0; j<n; j++) V[j] = G.new_node();
  85.   for(j=0; j<n; j++) 
  86.   { list<int> il;
  87.     int ok = false;
  88.     while (!ok)
  89.     { ok = true;
  90.       cout << "edges from [" << j << "] to: ";
  91.       il.read();
  92.       forall(i,il) 
  93.         if (i < 0 || i >= n) 
  94.         { ok=false;
  95.           cout << "illegal node " << i << "n";
  96.          }
  97.      }
  98.     forall(i,il) G.new_edge(V[j],V[i]);
  99.   }
  100.   G.print();
  101.   if (Yes("save graph ? ")) G.write(read_string("file: "));
  102. }
  106. void test_graph(graph& G)
  107. { 
  108.   G.clear();
  109.   char c;
  111.   do c = read_char("graph: f(ile) r(andom) c(omplete) p(lanar) u(ser): ");
  112.   while (c!='f' && c!='r' && c!='c' && c!='p'&& c!='u');   
  114.   switch (c) {
  116.    case 'f' : { G.read(read_string("file: "));
  117.                 break;
  118.                }
  120.    case 'u' : { user_graph(G);
  121.                 break;
  122.                }
  124.    case 'c' : { complete_graph(G,read_int("|V| = "));
  125.                 break;
  126.                }
  128.    case 'r' : { int n = read_int("|V| = ");
  129.                 int m = read_int("|E| = ");
  130.                 random_graph(G,n,m);
  131.                 break;
  132.                }
  134.    case 'p' : { random_planar_graph(G,read_int("|V| = "));
  135.                 break;
  136.                }
  137.    }//switch
  139. }
  141. void test_ugraph(ugraph& G)
  142. { 
  143.   G.clear();
  144.   char c;
  146.   do c = read_char("graph: f(ile) r(andom) c(omplete) p(lanar) u(ser): ");
  147.   while (c!='f' && c!='r' && c!='c' && c!='p'&& c!='u');   
  149.   int  i;
  150.   node v;
  151.   
  152.   switch (c) {
  154.   case 'f' : { G.read(read_string("file: "));
  155.                break;
  156.               }
  158.    case 'u' : { int  n = read_int("|V| = ");
  159.                 int  j = 0;
  160.                 node* V = new node[n];
  161.                 for(i=0; i<n; i++) V[i] = G.new_node();
  162.                 forall_nodes(v,G)
  163.                   { list<int> il;
  164.                     cout << "edges from " << j++ << " to: ";
  165.                     il.read();
  166.                     forall(i,il) 
  167.                       if (i >= 0 && i < n) G.new_edge(v,V[i]);
  168.                       else cerr << "illegal node " << i << " (ignored)n";
  169.                    }
  170.                 G.print();
  171.                 if (Yes("save graph ? ")) G.write(read_string("file: "));
  172.                 break;
  173.                }
  175.    case 'c' : { int n = read_int("|V| = ");
  176.                 complete_graph(G,n);
  177.                 break;
  178.                }
  180.    case 'r' : { int n = read_int("|V| = ");
  181.                 int m = read_int("|E| = ");
  182.                 random_graph(G,n,m);
  183.                 break;
  184.                }
  186.    }//switch
  188. }
  194. void test_bigraph(graph& G, list<node>& A, list<node>& B)
  195. {
  196.   int  a,b,n1,n2;
  197.   char c;
  199.   do c = read_char("bipartite graph: f(ile) r(andom) c(omplete) u(ser): ");
  200.   while (c!='f' && c!='r' && c!='c' && c!='u');   
  202.   A.clear();
  203.   B.clear();
  204.   G.clear();
  206.   if (c!='f') 
  207.    { n1 = read_int("|A| = ");
  208.      n2 = read_int("|B| = ");
  209.     }
  210.   
  211.   
  212.   switch (c) {
  214.   case 'f' : { G.read(read_string("file: "));
  215.                node v;
  216.                forall_nodes(v,G) 
  217.                if (G.outdeg(v) > 0) A.append(v);
  218.                else B.append(v);
  220.                break;
  221.               }
  223.    case 'u' : { node* AV = new node[n1+1];
  224.                 node* BV = new node[n2+1];
  226.                 for(a=1; a<=n1; a++)  A.append(AV[a] = G.new_node());
  227.                 for(b=1; b<=n2; b++)  B.append(BV[b] = G.new_node());
  229.                 for(a=1; a<=n1; a++)
  230.                 { list<int> il;
  231.                   cout << "edges from " << a << " to: ";
  232.                   il.read();
  233.                   forall(b,il) 
  234.                     if (b<=n2) G.new_edge(AV[a],BV[b]);
  235.                     else break;
  236.                   if (b>n2) break;
  237.                  }
  238.                 break;
  239.                }
  241.    case 'c' : complete_bigraph(G,n1,n2,A,B);
  242.               break;
  244.    case 'r' : { int m = read_int("|E| = ");
  245.                 random_bigraph(G,n1,n2,m,A,B);
  246.                 break;
  247.                }
  249.        } // switch
  251. }
  255. void cmdline_graph(graph& G, int argc, char** argv)
  256. { 
  257.   // construct graph from cmdline arguments
  259.   if (argc == 1)           // no arguments 
  260.      { test_graph(G);
  261.        return;
  262.       }
  263.   else 
  264.      if (argc == 2)       // one argument
  265.         { if (isdigit(argv[1][0])) 
  266.              { cout << "complete graph |V| = " << argv[1];
  267.                newline;
  268.                newline;
  269.                complete_graph(G,atoi(argv[1]));
  270.               }
  271.           else 
  272.              { cout << "reading graph from file " << argv[1];
  273.                newline;
  274.                newline;
  275.                G.read(argv[1]);
  276.               }
  277.           return;
  278.          }
  279.      else
  280.         if (argc == 3 && isdigit(argv[1][0]) && isdigit(argv[1][0])) 
  281.            { cout << "random graph |V| = " << argv[1] << "  |E| = " << argv[2];
  282.              newline;
  283.              newline;
  284.              random_graph(G,atoi(argv[1]),atoi(argv[2]));
  285.              return;
  286.             }
  288.   error_handler(1,"cmdline_graph: illegal arguments");
  289. }
  294. //------------------------------------------------------------------------------
  295. // triangulated planar graph
  296. //------------------------------------------------------------------------------
  299. #include <LEDA/d_array.h>
  302. class triang_point {
  304. public:
  306. double x;
  307. double y;
  309. LEDA_MEMORY(triang_point)
  311. triang_point(double a=0, double b = 0) { x = a; y = b; }
  312. triang_point(const triang_point& p)    { x = p.x; y = p.y; }
  313. ~triang_point() {};
  315. bool operator==(const triang_point& p) { return x==p.x && y==p.y; }
  317. friend bool right_turn(const triang_point& a, const triang_point& b, const triang_point& c)
  318. { return (a.y-b.y)*(a.x-c.x)+(b.x-a.x)*(a.y-c.y) > 0; }
  320. friend bool left_turn(const triang_point& a, const triang_point& b, const triang_point& c)
  321. { return (a.y-b.y)*(a.x-c.x)+(b.x-a.x)*(a.y-c.y) < 0; }
  323. };
  325. inline int compare(const triang_point& p, const triang_point& q)
  326. { int c = compare(p.x,q.x);
  327.   if (c==0) c = compare(p.y,q.y);
  328.   return c;
  329.  }
  331. inline void Print(const triang_point&, ostream&) {}
  332. inline void Read(triang_point&, istream&) {}
  336. #if !defined(__TEMPLATE_FUNCTIONS__)
  337. LEDA_TYPE_PARAMETER(triang_point)
  338. #endif
  341. void triangulated_planar_graph(graph& G, node_array<double>& xcoord,
  342.                                          node_array<double>& ycoord, int n)
  343. { 
  344.   list<triang_point> L;
  345.   double x;
  346.   double y;
  348.   while(n--)
  349.   { rand_int >> x; 
  350.     rand_int >> y;
  351.     L.append(triang_point(x,y));
  352.    }
  354.   L.sort();  // sort triang_points lexicographically
  356.   list<triang_point> CH;
  357.   list_item last;
  358.   triang_point p,q;
  361.   // eliminate multiple triang_points
  363.   list_item it;
  364.   forall_items(it,L)
  365.   { list_item it1 = L.succ(it);
  366.     while (it1 != nil && L[it1] == L[it])
  367.     { L.del(it1);
  368.       it1 = L.succ(it);
  369.      }
  370.    }
  372.   n = L.length();
  374.   d_array<triang_point,node> V(nil);
  376.   xcoord.init(G,n,0);
  377.   ycoord.init(G,n,0);
  379.   forall(q,L) 
  380.   { node v = G.new_node();
  381.     xcoord[v] = q.x;
  382.     ycoord[v] = q.y;
  383.     V[q] = v;
  384.    }
  387.   // initialize convex hull with first two points
  389.   p = L.pop();
  390.   CH.append(p);
  392.   while (L.head() == p) L.pop();
  393.   q = L.pop();
  394.   last = CH.append(q);
  396.   G.new_edge(V[p],V[q]);
  399.   // scan remaining points
  401.   forall(p,L)
  402.   {
  403.     node v = V[p];
  405.     G.new_edge(v,V[CH[last]]);
  407.     // compute upper tangent (p,up)
  409.     list_item up = last;
  410.     list_item it = CH.cyclic_succ(up);
  412.     while (left_turn(CH[it],CH[up],p))
  413.     { up = it;
  414.       it = CH.cyclic_succ(up);
  415.       G.new_edge(v,V[CH[up]]);
  416.      }
  419.     // compute lower tangent (p,low)
  421.     list_item low = last;
  422.     it = CH.cyclic_pred(low);
  424.     while (right_turn(CH[it],CH[low],p))
  425.     { low = it;
  426.       it = CH.cyclic_pred(low);
  427.       G.new_edge(v,V[CH[low]]);
  428.      }
  431.     // remove all points between up and low
  433.     if (up != low)
  434.     { it = CH.cyclic_succ(low);
  436.       while (it != up)
  437.       { CH.del(it);
  438.         it = CH.cyclic_succ(low);
  439.        }
  440.      }
  442.     // insert new point
  444.     last = CH.insert(p,low);
  446.    }
  448. }
  450. void triangulated_planar_graph(graph& G, int m)
  451. { node_array<double> xcoord;
  452.   node_array<double> ycoord;
  453.   triangulated_planar_graph(G,xcoord,ycoord,m);
  454.  }