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 / src / graph / _g_generate.c < prev    next >
C/C++ Source or Header  |  1996-09-03  |  11KB  |  490 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA 3.4
  4. +
  5. +  _g_generate.c
  6. +
  7. +  This file is part of the LEDA research version (LEDA-R) that can be 
  8. +  used free of charge in academic research and teaching. Any commercial
  9. +  use of this software requires a license which is distributed by the
  10. +  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
  11. +  (fax +49 681 31104).
  12. +
  13. +  Copyright (c) 1991-1996  by  Max-Planck-Institut fuer Informatik
  14. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  15. +  All rights reserved.
  16. + 
  17. *******************************************************************************/
  18. #include <LEDA/array2.h>
  19. #include <LEDA/graph.h>
  20. #include <LEDA/ugraph.h>
  21. #include <ctype.h>
  22.  
  23. //------------------------------------------------------------------------------
  24. // some graph generators
  25. //
  26. // S. Naeher  (1995)
  27. //------------------------------------------------------------------------------
  28.  
  29. void complete_graph(graph& G, int n, bool directed)
  30. { 
  31.   G.clear();
  32.  
  33.   node* V = new node[n];
  34.  
  35.   for(int i=0;i<n;i++) V[i] = G.new_node();
  36.  
  37.   if (directed)
  38.     { //memory_allocate_block(sizeof(node_struct),n);
  39.       for(int i=0;i<n;i++) 
  40.         for(int j=0;j<n;j++) G.new_edge(V[i],V[j]);
  41.      }
  42.   else
  43.     { //memory_allocate_block(sizeof(edge_struct),n*n/2);
  44.       for(int i=0; i<n; i++) 
  45.         for(int j=i+1; j<n; j++) G.new_edge(V[i],V[j]);
  46.      }
  47.  
  48.   delete[] V;
  49. }
  50.  
  51.  
  52.  
  53. void grid_graph(graph& G, int n) 
  54. { node_array<double> xcoord; 
  55.   node_array<double> ycoord;
  56.   grid_graph(G,xcoord,ycoord,n);
  57.  }
  58.  
  59. void grid_graph(graph& G, node_array<double>& xcoord, 
  60.                           node_array<double>& ycoord, int n) 
  61. {
  62.   array2<node>  A(n,n);
  63.   node v;
  64.   int N = n*n;
  65.   int x;
  66.   int y;
  67.  
  68.   double d = 1.0/(n+1);
  69.  
  70.   G.clear();
  71.  
  72.   xcoord.init(G,N,0);
  73.   ycoord.init(G,N,0);
  74.  
  75.   for(y=0; y<n; y++)
  76.     for(x=0; x<n; x++)
  77.       { A(x,y) = v = G.new_node();
  78.         xcoord[v] = (x+1)*d;
  79.         ycoord[v] = (y+1)*d;
  80.        }
  81.  
  82.   for(x=0; x<n; x++)
  83.     for(y=0; y<n; y++)
  84.        { if (x < n-1) G.new_edge(A(x,y),A(x+1,y));
  85.          if (y < n-1) G.new_edge(A(x,y),A(x,y+1));
  86.         }
  87. }
  88.  
  89.  
  90. void complete_bigraph(graph& G, int n1, int n2, list<node>& A, list<node>& B)
  91. { node v,w;
  92.  
  93.   G.clear();
  94.   //memory_allocate_block(sizeof(node_struct),n1+n2);
  95.   //memory_allocate_block(sizeof(edge_struct),n1*n2);
  96.  
  97.   for(int a=0; a < n1; a++)  A.append(G.new_node());
  98.   for(int b=0; b < n2; b++)  B.append(G.new_node());
  99.  
  100.   forall(v,A) 
  101.   {  forall(w,B) 
  102.        G.new_edge(v,w);
  103.    }
  104.  }
  105.  
  106. void user_graph(graph& G)
  107. { int  n = read_int("|V| = ");
  108.   int  i,j;
  109.  
  110.   node* V = new node[n];
  111.   for(j=0; j<n; j++) V[j] = G.new_node();
  112.  
  113.   for(j=0; j<n; j++) 
  114.   { list<int> il;
  115.     int ok = false;
  116.     while (!ok)
  117.     { ok = true;
  118.       cout << "edges from [" << j << "] to: ";
  119.       il.read();
  120.       forall(i,il) 
  121.         if (i < 0 || i >= n) 
  122.         { ok=false;
  123.           cout << "illegal node " << i << "\n";
  124.          }
  125.      }
  126.     forall(i,il) G.new_edge(V[j],V[i]);
  127.   }
  128.   G.print();
  129.   if (Yes("save graph ? ")) G.write(read_string("file: "));
  130.  
  131.   delete[] V;
  132. }
  133.  
  134.  
  135.  
  136. void test_graph(graph& G)
  137. { 
  138.   G.clear();
  139.   char c;
  140.  
  141.   do c = read_char("graph: f(ile) r(andom) c(omplete) p(lanar) u(ser): ");
  142.   while (c!='f' && c!='r' && c!='c' && c!='p'&& c!='u');   
  143.  
  144.   switch (c) {
  145.  
  146.    case 'f' : { G.read(read_string("file: "));
  147.                 break;
  148.                }
  149.  
  150.    case 'u' : { user_graph(G);
  151.                 break;
  152.                }
  153.  
  154.    case 'c' : { complete_graph(G,read_int("|V| = "));
  155.                 break;
  156.                }
  157.  
  158.    case 'r' : { int n = read_int("|V| = ");
  159.                 int m = read_int("|E| = ");
  160.                 random_graph(G,n,m);
  161.                 break;
  162.                }
  163.  
  164.    case 'p' : { random_planar_graph(G,read_int("|V| = "));
  165.                 break;
  166.                }
  167.    }//switch
  168.  
  169. }
  170.  
  171. void test_ugraph(ugraph& G)
  172. { 
  173.   G.clear();
  174.   char c;
  175.  
  176.   do c = read_char("graph: f(ile) r(andom) c(omplete) p(lanar) u(ser): ");
  177.   while (c!='f' && c!='r' && c!='c' && c!='p'&& c!='u');   
  178.  
  179.   int  i;
  180.   node v;
  181.   
  182.   switch (c) {
  183.  
  184.   case 'f' : { G.read(read_string("file: "));
  185.                break;
  186.               }
  187.  
  188.    case 'u' : { int  n = read_int("|V| = ");
  189.                 int  j = 0;
  190.                 node* V = new node[n];
  191.                 for(i=0; i<n; i++) V[i] = G.new_node();
  192.                 forall_nodes(v,G)
  193.                   { list<int> il;
  194.                     cout << "edges from " << j++ << " to: ";
  195.                     il.read();
  196.                     forall(i,il) 
  197.                       if (i >= 0 && i < n) G.new_edge(v,V[i]);
  198.                       else cerr << "illegal node " << i << " (ignored)\n";
  199.                    }
  200.                 G.print();
  201.                 if (Yes("save graph ? ")) G.write(read_string("file: "));
  202.                 delete[] V;
  203.                 break;
  204.                }
  205.  
  206.    case 'c' : { int n = read_int("|V| = ");
  207.                 complete_graph(G,n);
  208.                 break;
  209.                }
  210.  
  211.    case 'r' : { int n = read_int("|V| = ");
  212.                 int m = read_int("|E| = ");
  213.                 random_graph(G,n,m);
  214.                 break;
  215.                }
  216.  
  217.    }//switch
  218.  
  219. }
  220.  
  221.  
  222.  
  223.  
  224.  
  225. void test_bigraph(graph& G, list<node>& A, list<node>& B)
  226. {
  227.   int  a,b,n1,n2;
  228.   char c;
  229.  
  230.   do c = read_char("bipartite graph: f(ile) r(andom) c(omplete) u(ser): ");
  231.   while (c!='f' && c!='r' && c!='c' && c!='u');   
  232.  
  233.   A.clear();
  234.   B.clear();
  235.   G.clear();
  236.  
  237.   if (c!='f') 
  238.    { n1 = read_int("|A| = ");
  239.      n2 = read_int("|B| = ");
  240.     }
  241.   
  242.   
  243.   switch (c) {
  244.  
  245.   case 'f' : { G.read(read_string("file: "));
  246.                node v;
  247.                forall_nodes(v,G) 
  248.                if (G.outdeg(v) > 0) A.append(v);
  249.                else B.append(v);
  250.  
  251.                break;
  252.               }
  253.  
  254.    case 'u' : { node* AV = new node[n1+1];
  255.                 node* BV = new node[n2+1];
  256.  
  257.                 for(a=1; a<=n1; a++)  A.append(AV[a] = G.new_node());
  258.                 for(b=1; b<=n2; b++)  B.append(BV[b] = G.new_node());
  259.  
  260.                 for(a=1; a<=n1; a++)
  261.                 { list<int> il;
  262.                   cout << "edges from " << a << " to: ";
  263.                   il.read();
  264.                   forall(b,il) 
  265.                     if (b<=n2) G.new_edge(AV[a],BV[b]);
  266.                     else break;
  267.                   if (b>n2) break;
  268.                  }
  269.                 delete[] AV;
  270.                 delete[] BV;
  271.                 break;
  272.                }
  273.  
  274.    case 'c' : complete_bigraph(G,n1,n2,A,B);
  275.               break;
  276.  
  277.    case 'r' : { int m = read_int("|E| = ");
  278.                 random_bigraph(G,n1,n2,m,A,B);
  279.                 break;
  280.                }
  281.  
  282.        } // switch
  283.  
  284. }
  285.  
  286.  
  287.  
  288. void cmdline_graph(graph& G, int argc, char** argv)
  289. { 
  290.   // construct graph from cmdline arguments
  291.  
  292.   if (argc == 1)           // no arguments 
  293.      { test_graph(G);
  294.        return;
  295.       }
  296.   else 
  297.      if (argc == 2)       // one argument
  298.         { if (isdigit(argv[1][0])) 
  299.              { cout << "complete graph |V| = " << argv[1];
  300.                newline;
  301.                newline;
  302.                complete_graph(G,atoi(argv[1]));
  303.               }
  304.           else 
  305.              { cout << "reading graph from file " << argv[1];
  306.                newline;
  307.                newline;
  308.                G.read(argv[1]);
  309.               }
  310.           return;
  311.          }
  312.      else
  313.         if (argc == 3 && isdigit(argv[1][0]) && isdigit(argv[1][0])) 
  314.            { cout << "random graph |V| = " << argv[1] << "  |E| = " << argv[2];
  315.              newline;
  316.              newline;
  317.              random_graph(G,atoi(argv[1]),atoi(argv[2]));
  318.              return;
  319.             }
  320.  
  321.   error_handler(1,"cmdline_graph: illegal arguments");
  322. }
  323.  
  324.  
  325.  
  326.  
  327. //------------------------------------------------------------------------------
  328. // triangulated planar graph
  329. //------------------------------------------------------------------------------
  330.  
  331.  
  332. #include <LEDA/d_array.h>
  333.  
  334.  
  335. class triang_point {
  336.  
  337. public:
  338.  
  339. double x;
  340. double y;
  341.  
  342. LEDA_MEMORY(triang_point)
  343.  
  344. triang_point(double a=0, double b = 0) { x = a; y = b; }
  345. triang_point(const triang_point& p)    { x = p.x; y = p.y; }
  346. ~triang_point() {};
  347.  
  348. bool operator==(const triang_point& p) { return x==p.x && y==p.y; }
  349.  
  350. friend bool right_turn(const triang_point& a, const triang_point& b, const triang_point& c)
  351. { return (a.y-b.y)*(a.x-c.x)+(b.x-a.x)*(a.y-c.y) > 0; }
  352.  
  353. friend bool left_turn(const triang_point& a, const triang_point& b, const triang_point& c)
  354. { return (a.y-b.y)*(a.x-c.x)+(b.x-a.x)*(a.y-c.y) < 0; }
  355.  
  356. };
  357.  
  358. inline int compare(const triang_point& p, const triang_point& q)
  359. { int c = compare(p.x,q.x);
  360.   if (c==0) c = compare(p.y,q.y);
  361.   return c;
  362.  }
  363.  
  364. inline void Print(const triang_point&, ostream&) {}
  365. inline void Read(triang_point&, istream&) {}
  366.  
  367.  
  368.  
  369. #if !defined(__TEMPLATE_FUNCTIONS__)
  370. LEDA_TYPE_PARAMETER(triang_point)
  371. #endif
  372.  
  373.  
  374. void triangulated_planar_graph(graph& G, node_array<double>& xcoord,
  375.                                          node_array<double>& ycoord, int n)
  376. { 
  377.   list<triang_point> L;
  378.   double x;
  379.   double y;
  380.  
  381.   while(n--)
  382.   { rand_int >> x; 
  383.     rand_int >> y;
  384.     L.append(triang_point(x,y));
  385.    }
  386.  
  387.   L.sort();  // sort triang_points lexicographically
  388.  
  389.   list<triang_point> CH;
  390.   list_item last;
  391.   triang_point p,q;
  392.  
  393.  
  394.   // eliminate multiple triang_points
  395.  
  396.   list_item it;
  397.   forall_items(it,L)
  398.   { list_item it1 = L.succ(it);
  399.     while (it1 != nil && L[it1] == L[it])
  400.     { L.del(it1);
  401.       it1 = L.succ(it);
  402.      }
  403.    }
  404.  
  405.   n = L.length();
  406.  
  407.   d_array<triang_point,node> V(nil);
  408.  
  409.   xcoord.init(G,n,0);
  410.   ycoord.init(G,n,0);
  411.  
  412.   forall(q,L) 
  413.   { node v = G.new_node();
  414.     xcoord[v] = q.x;
  415.     ycoord[v] = q.y;
  416.     V[q] = v;
  417.    }
  418.  
  419.  
  420.   // initialize convex hull with first two points
  421.  
  422.   p = L.pop();
  423.   CH.append(p);
  424.  
  425.   while (L.head() == p) L.pop();
  426.   q = L.pop();
  427.   last = CH.append(q);
  428.  
  429.   G.new_edge(V[p],V[q]);
  430.  
  431.  
  432.   // scan remaining points
  433.  
  434.   forall(p,L)
  435.   {
  436.     node v = V[p];
  437.  
  438.     G.new_edge(v,V[CH[last]]);
  439.  
  440.     // compute upper tangent (p,up)
  441.  
  442.     list_item up = last;
  443.     list_item it = CH.cyclic_succ(up);
  444.  
  445.     while (left_turn(CH[it],CH[up],p))
  446.     { up = it;
  447.       it = CH.cyclic_succ(up);
  448.       G.new_edge(v,V[CH[up]]);
  449.      }
  450.  
  451.  
  452.     // compute lower tangent (p,low)
  453.  
  454.     list_item low = last;
  455.     it = CH.cyclic_pred(low);
  456.  
  457.     while (right_turn(CH[it],CH[low],p))
  458.     { low = it;
  459.       it = CH.cyclic_pred(low);
  460.       G.new_edge(v,V[CH[low]]);
  461.      }
  462.  
  463.  
  464.     // remove all points between up and low
  465.  
  466.     if (up != low)
  467.     { it = CH.cyclic_succ(low);
  468.  
  469.       while (it != up)
  470.       { CH.del(it);
  471.         it = CH.cyclic_succ(low);
  472.        }
  473.      }
  474.  
  475.     // insert new point
  476.  
  477.     last = CH.insert(p,low);
  478.  
  479.    }
  480.  
  481. }
  482.  
  483. void triangulated_planar_graph(graph& G, int m)
  484. { node_array<double> xcoord;
  485.   node_array<double> ycoord;
  486.   triangulated_planar_graph(G,xcoord,ycoord,m);
  487.  }
  488.  
  489.  
  490.