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_random.c < prev    next >
C/C++ Source or Header  |  1996-09-03  |  13KB  |  561 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA 3.4
  4. +
  5. +  _g_random.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/graph.h>
  19. #include <LEDA/ugraph.h>
  20.  
  21. //------------------------------------------------------------------------------
  22. // generators for random graphs
  23. //
  24. // by S. Naeher  (1995)
  25. //------------------------------------------------------------------------------
  26.  
  27.  
  28. // we use the global random integer source "rand_int"
  29.  
  30. void random_graph(graph& G, int n, int m)
  31. { /* random graph with n nodes and m edges */ 
  32.  
  33.   node* V = new node[n];
  34.  
  35.   G.clear();
  36.  
  37.   for(int i=0;i<n;i++) V[i] = G.new_node();
  38.  
  39.   while (m--) G.new_edge(V[rand_int(0,n-1)],V[rand_int(0,n-1)]);
  40.  
  41.   delete[] V;
  42. }
  43.  
  44.  
  45. void random_ugraph(ugraph& G, int n, int m)
  46. { int i;
  47.   node* V = new node[n];
  48.  
  49.   G.clear();
  50.  
  51.   for(i=0;i<n;i++) V[i] = G.new_node();
  52.  
  53.   while (m--) G.new_edge(V[rand_int(0,n-1)],V[rand_int(0,n-1)]);
  54. }
  55.  
  56.  
  57. void random_bigraph(graph& G,int n1,int n2,int m,list<node>& A,list<node>& B)
  58. {
  59.    int  d = m/n1; 
  60.    int  r = m%n1; 
  61.  
  62.    node* AV = new node[n1];
  63.    node* BV = new node[n2];
  64.  
  65.    A.clear();
  66.    B.clear();
  67.    G.clear();
  68.  
  69.    for(int a = 0; a < n1; a++)  A.append(AV[a] = G.new_node());
  70.    for(int b = 0; b < n2; b++)  B.append(BV[b] = G.new_node());
  71.  
  72.    node v;
  73.    int i;
  74.  
  75.    forall(v,A)
  76.      for(i=0;i<d;i++)
  77.        G.new_edge(v,BV[rand_int(0,n2-1)]);
  78.  
  79.    while (r--) G.new_edge(AV[rand_int(0,n1-1)], BV[rand_int(0,n2-1)]);
  80.  
  81.    delete[] AV;
  82.    delete[] BV;
  83. }
  84.  
  85.  
  86.  
  87.  
  88. //------------------------------------------------------------------------------
  89. // random planar graph
  90. //------------------------------------------------------------------------------
  91.  
  92. #include <LEDA/sortseq.h>
  93. #include <LEDA/prio.h>
  94. #include <math.h>
  95.  
  96. #define YNIL seq_item(nil)
  97. #define XNIL pq_item(nil)
  98.  
  99.  
  100. #define EPS  0.00001
  101. #define EPS2 0.0000000001
  102.  
  103. class POINT;
  104. class SEGMENT;
  105. typedef POINT* point;
  106. typedef SEGMENT* segment;
  107.  
  108. enum point_type {Intersection=0,Rightend=1,Leftend=2}; 
  109.  
  110. class POINT
  111. {
  112.   friend class SEGMENT;
  113.  
  114.   segment seg;
  115.   int     kind;
  116.   double  x;
  117.   double  y;
  118.  
  119.   public:
  120.  
  121.   POINT(double a,double b)  
  122.   { 
  123.     x=a; y=b; seg=0; kind=Intersection;
  124.    }
  125.  
  126.  
  127.   LEDA_MEMORY(POINT);
  128.  
  129.   friend double    get_x(point p)    { return p->x; }
  130.   friend double    get_y(point p)    { return p->y; }
  131.   friend int       get_kind(point p) { return p->kind; }
  132.   friend segment get_seg(point p)  { return p->seg; }   
  133.  
  134.   friend bool intersection(segment, segment, point&);
  135. };
  136.  
  137.  
  138.  
  139. #if defined(__GNUC__)
  140. // if I declare compare static g++ does not use it
  141. // but instantiates the default error compare template
  142. inline
  143. #else
  144. static
  145. #endif
  146. int compare(const point& p1, const point& p2)
  147. { if (p1==p2) return 0;
  148.  
  149.   double diffx = get_x(p1) - get_x(p2);
  150.   if (diffx >  EPS2 ) return  1;
  151.   if (diffx < -EPS2 ) return -1;
  152.  
  153.   int    diffk = get_kind(p1)-get_kind(p2);
  154.   if (diffk != 0) return diffk;
  155.  
  156.   double diffy = get_y(p1) - get_y(p2);
  157.   if (diffy >  EPS2 ) return  1;
  158.   if (diffy < -EPS2 ) return -1;
  159.  
  160.   return 0;
  161.  
  162. }
  163.  
  164.  
  165. class SEGMENT
  166. {
  167.   point startpoint;
  168.   point endpoint;
  169.   double  slope;
  170.   double  yshift;
  171.   node  left_node;
  172.   int   orient;
  173.   int   color;
  174.   int   name;
  175.  
  176.  
  177.   public:
  178.  
  179.   SEGMENT(point, point,int,int);     
  180.  
  181.  ~SEGMENT() { delete startpoint; delete endpoint; }     
  182.  
  183.   LEDA_MEMORY(SEGMENT);
  184.  
  185.  
  186.   friend point get_startpoint(segment seg)     { return seg->startpoint; }
  187.   friend point get_endpoint(segment seg)       { return seg->endpoint; }
  188.   friend double get_slope(segment seg)           { return seg->slope; }
  189.   friend double get_yshift(segment seg)          { return seg->yshift; }
  190.   friend node get_left_node(segment seg)         { return seg->left_node; }
  191.   friend void set_left_node(segment seg, node v) { seg->left_node = v; }
  192.  
  193.   friend bool intersection(segment, segment, point&);
  194. };
  195.  
  196.  
  197.  
  198.  
  199. SEGMENT::SEGMENT(point p1,point p2,int c, int n)    
  200.   {
  201.     left_node  = nil;
  202.     color      = c;
  203.     name       = n;
  204.  
  205.     if (compare(p1,p2) < 0)
  206.      { startpoint = p1; 
  207.        endpoint = p2; 
  208.        orient = 0;
  209.       }
  210.     else
  211.      { startpoint = p2; 
  212.        endpoint = p1; 
  213.        orient = 1;
  214.       }
  215.  
  216.     startpoint->kind = Leftend; 
  217.     endpoint->kind = Rightend; 
  218.     startpoint->seg = this; 
  219.     endpoint->seg = this;
  220.  
  221.     if (endpoint->x != startpoint->x)
  222.     {
  223.       slope = (endpoint->y - startpoint->y)/(endpoint->x - startpoint->x);
  224.       yshift = startpoint->y - slope * startpoint->x;
  225.  
  226.       startpoint->x -= EPS;
  227.       startpoint->y -= EPS * slope;
  228.       endpoint->x += EPS;
  229.       endpoint->y += EPS * slope;
  230.     }
  231.     else //vertical segment
  232.     { startpoint->y -= EPS;
  233.       endpoint->y   += EPS;
  234.      }
  235.   }
  236.  
  237.  
  238. static double x_sweep;
  239. static double y_sweep;
  240.  
  241.  
  242. static int compare(const segment& s1, const segment& s2)
  243. {
  244.   double y1 = get_slope(s1)*x_sweep+get_yshift(s1);
  245.   double y2 = get_slope(s2)*x_sweep+get_yshift(s2);
  246.  
  247.   double diff = y1-y2;
  248.   if (diff >  EPS2 ) return  1;
  249.   if (diff < -EPS2 ) return -1;
  250.  
  251.   if (get_slope(s1) == get_slope(s2)) 
  252.         return compare(get_x(get_startpoint(s1)), get_x(get_startpoint(s2)));
  253.  
  254.   if (y1 <= y_sweep+EPS2)
  255.         return compare(get_slope(s1),get_slope(s2));
  256.   else
  257.         return compare(get_slope(s2),get_slope(s1));
  258.  
  259. }
  260.  
  261.  
  262.  
  263. static priority_queue<seq_item,point> X_structure;
  264.  
  265. static sortseq<segment,pq_item> Y_structure;
  266.  
  267.  
  268. bool intersection(segment seg1,segment seg2, point& inter)
  269. {
  270.   if (seg1->slope == seg2->slope)
  271.     return false;
  272.   else
  273.   { 
  274.     double cx = (seg2->yshift - seg1->yshift) / (seg1->slope - seg2->slope);
  275.  
  276.     if (cx <= x_sweep) return false;
  277.  
  278.     if (seg1->startpoint->x > cx || seg2->startpoint->x > cx ||
  279.         seg1->endpoint->x < cx || seg2->endpoint->x < cx ) return false;
  280.  
  281.     inter = new POINT(cx,seg1->slope * cx + seg1->yshift);
  282.  
  283.     return true;
  284.   }
  285. }
  286.  
  287.  
  288.  
  289. inline pq_item Xinsert(seq_item i, point p) 
  290. { return X_structure.insert(i,p); }
  291.  
  292.  
  293. inline point Xdelete(pq_item i) 
  294. { point p = X_structure.inf(i);
  295.   X_structure.del_item(i);
  296.   return p;
  297.  }
  298.  
  299.  
  300. void random_planar_graph(graph& G, int m)
  301. { node_array<double> xcoord;
  302.   node_array<double> ycoord;
  303.   random_planar_graph(G,xcoord,ycoord,m);
  304.  }
  305.  
  306. void random_planar_graph(graph& G, node_array<double>& xcoord,
  307.                                    node_array<double>& ycoord, int n)
  308. {
  309.   point    p,inter;
  310.   segment  seg, l,lsit,lpred,lsucc,lpredpred;
  311.   pq_item  pqit,pxmin;
  312.   seq_item sitmin,sit,sitpred,sitsucc,sitpredpred;
  313.  
  314.   int MAX_X = n;
  315.   int MAX_Y = n;
  316.  
  317.  
  318.   int N = n;  // number of random segments
  319.  
  320.   xcoord.init(G,n,0);
  321.   ycoord.init(G,n,0);
  322.  
  323.  
  324.   int count=1;
  325.  
  326.   //initialization of the X-structure
  327.  
  328.   for (int i = 0; i < N; i++)
  329.    { //point p = new POINT(rand_int(0,MAX_X/3), rand_int(0,MAX_Y));
  330.      //point q = new POINT(rand_int(2*MAX_X/3,MAX_X), rand_int(0,MAX_Y));
  331.      point p = new POINT(rand_int(0,MAX_X), rand_int(0,MAX_Y));
  332.      point q = new POINT(rand_int(0,MAX_X), rand_int(0,MAX_Y));
  333.      seg = new SEGMENT(p,q,0,count++);
  334.      Xinsert(YNIL,get_startpoint(seg));
  335.    }
  336.  
  337.   // we insert a long vertical segment to make the graph connected
  338.  
  339. /*
  340.  { point p = new POINT(MAX_X/2 - 1,0);
  341.    point q = new POINT(MAX_X/2 + 1,MAX_Y);
  342.    seg = new SEGMENT(p,q,0,count++);
  343.    Xinsert(YNIL,get_startpoint(seg));
  344.   }
  345. */
  346.  
  347.  
  348.   count = 0;
  349.  
  350.   x_sweep = -MAXINT;
  351.   y_sweep = -MAXINT;
  352.  
  353.  
  354.   while( !X_structure.empty()  && G.number_of_nodes() < n)
  355.   {
  356.     pxmin = X_structure.find_min();
  357.     p = X_structure.inf(pxmin);
  358.  
  359.     sitmin = X_structure.key(pxmin);
  360.  
  361.     Xdelete(pxmin);
  362.  
  363.  
  364.  
  365.     if (sitmin == YNIL) //left endpoint
  366.     { 
  367.       l = get_seg(p); 
  368.  
  369.       x_sweep = get_x(p);
  370.       y_sweep = get_y(p);
  371.  
  372.  
  373.       sit = Y_structure.insert(l,XNIL);
  374.  
  375.       Xinsert(sit,get_endpoint(l));
  376.  
  377.       sitpred = Y_structure.pred(sit);
  378.       sitsucc = Y_structure.succ(sit);
  379.  
  380.       if (sitpred != YNIL) 
  381.       { if ((pqit = Y_structure.inf(sitpred)) != XNIL)
  382.           delete Xdelete(pqit);
  383.  
  384.         lpred = Y_structure.key(sitpred);
  385.  
  386.         Y_structure.change_inf(sitpred,XNIL);
  387.  
  388.         if (intersection(lpred,l,inter))
  389.             Y_structure.change_inf(sitpred,Xinsert(sitpred,inter));
  390.       }
  391.  
  392.  
  393.       if (sitsucc != YNIL)
  394.       { lsucc = Y_structure.key(sitsucc);
  395.         if (intersection(lsucc,l,inter))
  396.            Y_structure.change_inf(sit,Xinsert(sit,inter));
  397.       }
  398.  
  399.     }
  400.     else if (get_kind(p) == Rightend)
  401.          //right endpoint
  402.          { 
  403.            x_sweep = get_x(p);
  404.            y_sweep = get_y(p);
  405.  
  406.            sit = sitmin;
  407.  
  408.            sitpred = Y_structure.pred(sit);
  409.            sitsucc = Y_structure.succ(sit);
  410.  
  411.            segment seg = Y_structure.key(sit);
  412.  
  413.            Y_structure.del_item(sit);
  414.  
  415.            delete seg;
  416.  
  417.            if((sitpred != YNIL)&&(sitsucc != YNIL))
  418.            {
  419.              lpred = Y_structure.key(sitpred);
  420.              lsucc = Y_structure.key(sitsucc);
  421.              if (intersection(lsucc,lpred,inter))
  422.                 Y_structure.change_inf(sitpred,Xinsert(sitpred,inter));
  423.            }
  424.          }
  425.          else // intersection point p
  426.          { 
  427.            node w = G.new_node();
  428.            xcoord[w] = get_x(p);
  429.            ycoord[w] = get_y(p);
  430.  
  431.            count++;
  432.  
  433.            /* Let L = list of all lines intersecting in p 
  434.  
  435.               we compute sit     = L.head();
  436.               and        sitpred = L.tail();
  437.  
  438.               by scanning the Y_structure in both directions 
  439.               starting at sitmin;
  440.  
  441.            */
  442.  
  443.            /* search for sitpred upwards from sitmin: */
  444.  
  445.            Y_structure.change_inf(sitmin,XNIL);
  446.  
  447.            sitpred = Y_structure.succ(sitmin);
  448.  
  449.  
  450.            while ((pqit=Y_structure.inf(sitpred)) != XNIL)
  451.            { point q = X_structure.inf(pqit);
  452.              if (compare(p,q) != 0) break; 
  453.              X_structure.del_item(pqit);
  454.              Y_structure.change_inf(sitpred,XNIL);
  455.              sitpred = Y_structure.succ(sitpred);
  456.             }
  457.  
  458.  
  459.            /* search for sit downwards from sitmin: */
  460.  
  461.            sit = sitmin;
  462.  
  463.            seq_item sit1;
  464.            
  465.            while ((sit1=Y_structure.pred(sit)) != YNIL)
  466.            { pqit = Y_structure.inf(sit1);
  467.              if (pqit == XNIL) break;
  468.              point q = X_structure.inf(pqit);
  469.              if (compare(p,q) != 0) break; 
  470.              X_structure.del_item(pqit);
  471.              Y_structure.change_inf(sit1,XNIL);
  472.              sit = sit1;
  473.             }
  474.  
  475.  
  476.  
  477.            // insert edges to p for all segments in sit, ..., sitpred into G
  478.            // and set left node to w 
  479.  
  480.            lsit = Y_structure.key(sitpred);
  481.  
  482.            node v = get_left_node(lsit);
  483.            if (v!=nil && w!=nil) G.new_edge(v,w);
  484.            set_left_node(lsit,w);
  485.  
  486.            for(sit1=sit; sit1!=sitpred; sit1 = Y_structure.succ(sit1))
  487.            { lsit = Y_structure.key(sit1);
  488.  
  489.              v = get_left_node(lsit);
  490.              if (v!=nil && w!=nil) G.new_edge(v,w);
  491.              set_left_node(lsit,w);
  492.             }
  493.  
  494.            lsit = Y_structure.key(sit);
  495.            lpred=Y_structure.key(sitpred);
  496.            sitpredpred = Y_structure.pred(sit);
  497.            sitsucc=Y_structure.succ(sitpred);
  498.  
  499.  
  500.            if (sitpredpred != YNIL)
  501.             { 
  502.               lpredpred=Y_structure.key(sitpredpred);
  503.  
  504.               if ((pqit = Y_structure.inf(sitpredpred)) != XNIL)
  505.                 delete Xdelete(pqit);
  506.  
  507.               Y_structure.change_inf(sitpredpred,XNIL);
  508.  
  509.  
  510.               if (intersection(lpred,lpredpred,inter))
  511.                 Y_structure.change_inf(sitpredpred,
  512.                                        Xinsert(sitpredpred,inter));
  513.              }
  514.  
  515.  
  516.            if (sitsucc != YNIL)
  517.             {
  518.               lsucc=Y_structure.key(sitsucc);
  519.  
  520.               if ((pqit = Y_structure.inf(sitpred)) != XNIL)
  521.                 delete Xdelete(pqit);
  522.                  
  523.               Y_structure.change_inf(sitpred,XNIL);
  524.  
  525.               if (intersection(lsucc,lsit,inter))
  526.                   Y_structure.change_inf(sit,Xinsert(sit,inter));
  527.              }
  528.  
  529.  
  530. // reverse the subsequence sit, ... ,sitpred  in the Y_structure
  531.  
  532.            x_sweep = get_x(p);
  533.            y_sweep = get_y(p);
  534.  
  535.            Y_structure.reverse_items(sit,sitpred);
  536.  
  537.           delete p;
  538.  
  539.          } // intersection
  540.  
  541.   }
  542.  
  543.   X_structure.clear();
  544.   Y_structure.clear();
  545.  
  546.  
  547.  
  548.   // normalize x and y coordinates 
  549.  
  550.   node v;
  551.   forall_nodes(v,G) 
  552.   { xcoord[v] /= x_sweep;
  553.     ycoord[v] /= MAX_Y;
  554.    }
  555.  
  556.   Make_Connected(G);
  557.  
  558. }
  559.  
  560.  
  561.