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

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

数值算法/人工智能

开发平台：

MultiPlatform

_g_random.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _g_random.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #include <LEDA/graph.h>
  14. #include <LEDA/ugraph.h>
  16. // we use the global random integer source "rand_int"
  18. void random_graph(graph& G, int n, int m)
  19. { /* random graph with n nodes and m edges */ 
  21.   int i;
  22.   node* V = new node[n];
  23.   G.clear();
  25.   for(i=0;i<n;i++) V[i] = G.new_node();
  26.  
  27.   while (m--) G.new_edge(V[rand_int(0,n-1)],V[rand_int(0,n-1)]);
  28. }
  31. void random_ugraph(ugraph& G, int n, int m)
  32. { int i;
  33.   node* V = new node[n];
  34.   G.clear();
  36.   for(i=0;i<n;i++) V[i] = G.new_node();
  38.   while (m--) G.new_edge(V[rand_int(0,n-1)],V[rand_int(0,n-1)]);
  39. }
  42. void random_bigraph(graph& G,int n1,int n2,int m,list<node>& A,list<node>& B)
  43. {
  44.    int  d = m/n1; 
  45.    int  r = m%n1; 
  47.    node* AV = new node[n1];
  48.    node* BV = new node[n2];
  50.    A.clear();
  51.    B.clear();
  52.    G.clear();
  54.    for(int a = 0; a < n1; a++)  A.append(AV[a] = G.new_node());
  55.    for(int b = 0; b < n2; b++)  B.append(BV[b] = G.new_node());
  57.    node v;
  58.    int i;
  60.    forall(v,A)
  61.      for(i=0;i<d;i++)
  62.        G.new_edge(v,BV[rand_int(0,n2-1)]);
  64.    while (r--) G.new_edge(AV[rand_int(0,n1-1)], BV[rand_int(0,n2-1)]);
  66. }
  71. //------------------------------------------------------------------------------
  72. // random planar graph
  73. //------------------------------------------------------------------------------
  75. #include <LEDA/sortseq.h>
  76. #include <LEDA/prio.h>
  77. #include <math.h>
  80. #define EPS  0.00001
  81. #define EPS2 0.0000000001
  83. class POINT;
  84. class SEGMENT;
  85. typedef POINT* point;
  86. typedef SEGMENT* segment;
  88. enum point_type {Intersection=0,Rightend=1,Leftend=2}; 
  90. class POINT
  91. {
  92.   friend class SEGMENT;
  94.   segment seg;
  95.   int     kind;
  96.   double  x;
  97.   double  y;
  99.   public:
  101.   POINT(double a,double b)  
  102.   { 
  103.     x=a; y=b; seg=0; kind=Intersection;
  104.    }
  107.   LEDA_MEMORY(POINT);
  109.   friend double    get_x(point p)    { return p->x; }
  110.   friend double    get_y(point p)    { return p->y; }
  111.   friend int       get_kind(point p) { return p->kind; }
  112.   friend segment get_seg(point p)  { return p->seg; }   
  114.   friend bool intersection(segment, segment, point&);
  115. };
  119. #if defined(__GNUC__)
  120. // if I declare compare static g++ does not use it
  121. // but instantiates the default error compare template
  122. inline
  123. #else
  124. static
  125. #endif
  126. int compare(const point& p1, const point& p2)
  127. { if (p1==p2) return 0;
  129.   double diffx = get_x(p1) - get_x(p2);
  130.   if (diffx >  EPS2 ) return  1;
  131.   if (diffx < -EPS2 ) return -1;
  133.   int    diffk = get_kind(p1)-get_kind(p2);
  134.   if (diffk != 0) return diffk;
  136.   double diffy = get_y(p1) - get_y(p2);
  137.   if (diffy >  EPS2 ) return  1;
  138.   if (diffy < -EPS2 ) return -1;
  140.   return 0;
  142. }
  145. class SEGMENT
  146. {
  147.   point startpoint;
  148.   point endpoint;
  149.   double  slope;
  150.   double  yshift;
  151.   node  left_node;
  152.   int   orient;
  153.   int   color;
  154.   int   name;
  157.   public:
  159.   SEGMENT(point, point,int,int);     
  161.  ~SEGMENT() { delete startpoint; delete endpoint; }     
  163.   LEDA_MEMORY(SEGMENT);
  166.   friend point get_startpoint(segment seg)     { return seg->startpoint; }
  167.   friend point get_endpoint(segment seg)       { return seg->endpoint; }
  168.   friend double get_slope(segment seg)           { return seg->slope; }
  169.   friend double get_yshift(segment seg)          { return seg->yshift; }
  170.   friend node get_left_node(segment seg)         { return seg->left_node; }
  171.   friend void set_left_node(segment seg, node v) { seg->left_node = v; }
  173.   friend bool intersection(segment, segment, point&);
  174. };
  179. SEGMENT::SEGMENT(point p1,point p2,int c, int n)    
  180.   {
  181.     left_node  = nil;
  182.     color      = c;
  183.     name       = n;
  185.     if (compare(p1,p2) < 0)
  186.      { startpoint = p1; 
  187.        endpoint = p2; 
  188.        orient = 0;
  189.       }
  190.     else
  191.      { startpoint = p2; 
  192.        endpoint = p1; 
  193.        orient = 1;
  194.       }
  196.     startpoint->kind = Leftend; 
  197.     endpoint->kind = Rightend; 
  198.     startpoint->seg = this; 
  199.     endpoint->seg = this;
  201.     if (endpoint->x != startpoint->x)
  202.     {
  203.       slope = (endpoint->y - startpoint->y)/(endpoint->x - startpoint->x);
  204.       yshift = startpoint->y - slope * startpoint->x;
  206.       startpoint->x -= EPS;
  207.       startpoint->y -= EPS * slope;
  208.       endpoint->x += EPS;
  209.       endpoint->y += EPS * slope;
  210.     }
  211.     else //vertical segment
  212.     { startpoint->y -= EPS;
  213.       endpoint->y   += EPS;
  214.      }
  215.   }
  218. static double x_sweep;
  219. static double y_sweep;
  222. static int compare(const segment& s1, const segment& s2)
  223. {
  224.   double y1 = get_slope(s1)*x_sweep+get_yshift(s1);
  225.   double y2 = get_slope(s2)*x_sweep+get_yshift(s2);
  227.   double diff = y1-y2;
  228.   if (diff >  EPS2 ) return  1;
  229.   if (diff < -EPS2 ) return -1;
  231.   if (get_slope(s1) == get_slope(s2)) 
  232.         return compare(get_x(get_startpoint(s1)), get_x(get_startpoint(s2)));
  234.   if (y1 <= y_sweep+EPS2)
  235.         return compare(get_slope(s1),get_slope(s2));
  236.   else
  237.         return compare(get_slope(s2),get_slope(s1));
  239. }
  243. static priority_queue<seq_item,point> X_structure;
  245. static sortseq<segment,pq_item> Y_structure;
  248. bool intersection(segment seg1,segment seg2, point& inter)
  249. {
  250.   if (seg1->slope == seg2->slope)
  251.     return false;
  252.   else
  253.   { 
  254.     double cx = (seg2->yshift - seg1->yshift) / (seg1->slope - seg2->slope);
  255.  
  256.     if (cx <= x_sweep) return false;
  258.     if (seg1->startpoint->x > cx || seg2->startpoint->x > cx ||
  259.         seg1->endpoint->x < cx || seg2->endpoint->x < cx ) return false;
  261.     inter = new POINT(cx,seg1->slope * cx + seg1->yshift);
  263.     return true;
  264.   }
  265. }
  269. inline pq_item Xinsert(seq_item i, point p) 
  270. { return X_structure.insert(i,p); }
  273. inline point Xdelete(pq_item i) 
  274. { point p = X_structure.inf(i);
  275.   X_structure.del_item(i);
  276.   return p;
  277.  }
  280. void random_planar_graph(graph& G, int m)
  281. { node_array<double> xcoord;
  282.   node_array<double> ycoord;
  283.   random_planar_graph(G,xcoord,ycoord,m);
  284.  }
  286. void random_planar_graph(graph& G, node_array<double>& xcoord,
  287.                                    node_array<double>& ycoord, int n)
  288. {
  289.   point    p,inter;
  290.   segment  seg, l,lsit,lpred,lsucc,lpredpred;
  291.   pq_item  pqit,pxmin;
  292.   seq_item sitmin,sit,sitpred,sitsucc,sitpredpred;
  294.   int MAX_X = 1000;
  295.   int MAX_Y = 1000;
  297.   int N = int(2.5*sqrt(n)); // number of random segments
  299.   xcoord.init(G,n,0);
  300.   ycoord.init(G,n,0);
  303.   int count=1;
  304.  
  305.   //initialization of the X-structure
  307.   for (int i = 0; i < N; i++)
  308.    { point p = new POINT(rand_int(0,MAX_X/3), rand_int(0,MAX_Y));
  309.      point q = new POINT(rand_int(2*MAX_X/3,MAX_X), rand_int(0,MAX_Y));
  310.      seg = new SEGMENT(p,q,0,count++);
  311.      Xinsert(nil,get_startpoint(seg));
  312.    }
  314.   // we insert a long vertical segment to make the graph connecte
  316.  { point p = new POINT(MAX_X/2 - 1,0);
  317.    point q = new POINT(MAX_X/2 + 1,MAX_Y);
  318.    seg = new SEGMENT(p,q,0,count++);
  319.    Xinsert(nil,get_startpoint(seg));
  320.   }
  323.   count = 0;
  325.   x_sweep = -MAXINT;
  326.   y_sweep = -MAXINT;
  329.   while( !X_structure.empty() && G.number_of_nodes() < n)
  330.   {
  331.     pxmin = X_structure.find_min();
  332.     p = X_structure.inf(pxmin);
  334.     sitmin = X_structure.key(pxmin);
  336.     Xdelete(pxmin);
  340.     if (sitmin == nil) //left endpoint
  341.     { 
  342.       l = get_seg(p); 
  344.       x_sweep = get_x(p);
  345.       y_sweep = get_y(p);
  348.       sit = Y_structure.insert(l,nil);
  350.       Xinsert(sit,get_endpoint(l));
  352.       sitpred = Y_structure.pred(sit);
  353.       sitsucc = Y_structure.succ(sit);
  355.       if (sitpred != nil) 
  356.       { if ((pqit = Y_structure.inf(sitpred)) != nil)
  357.           delete Xdelete(pqit);
  359.         lpred = Y_structure.key(sitpred);
  361.         Y_structure.change_inf(sitpred,nil);
  363.         if (intersection(lpred,l,inter))
  364.             Y_structure.change_inf(sitpred,Xinsert(sitpred,inter));
  365.       }
  368.       if (sitsucc != nil)
  369.       { lsucc = Y_structure.key(sitsucc);
  370.         if (intersection(lsucc,l,inter))
  371.            Y_structure.change_inf(sit,Xinsert(sit,inter));
  372.       }
  374.     }
  375.     else if (get_kind(p) == Rightend)
  376.          //right endpoint
  377.          { 
  378.            x_sweep = get_x(p);
  379.            y_sweep = get_y(p);
  381.            sit = sitmin;
  383.            sitpred = Y_structure.pred(sit);
  384.            sitsucc = Y_structure.succ(sit);
  386.            segment seg = Y_structure.key(sit);
  388.            Y_structure.del_item(sit);
  390.            delete seg;
  392.            if((sitpred != nil)&&(sitsucc != nil))
  393.            {
  394.              lpred = Y_structure.key(sitpred);
  395.              lsucc = Y_structure.key(sitsucc);
  396.              if (intersection(lsucc,lpred,inter))
  397.                 Y_structure.change_inf(sitpred,Xinsert(sitpred,inter));
  398.            }
  399.          }
  400.          else // intersection point p
  401.          { 
  402.            node w = G.new_node();
  404.            xcoord[w] = get_x(p);
  405.            ycoord[w] = get_y(p);
  407.            count++;
  409.            /* Let L = list of all lines intersecting in p 
  410.  
  411.               we compute sit     = L.head();
  412.               and        sitpred = L.tail();
  414.               by scanning the Y_structure in both directions 
  415.               starting at sitmin;
  417.            */
  419.            /* search for sitpred upwards from sitmin: */
  421.            Y_structure.change_inf(sitmin,nil);
  423.            sitpred = Y_structure.succ(sitmin);
  426.            while ((pqit=Y_structure.inf(sitpred)) != nil)
  427.            { point q = X_structure.inf(pqit);
  428.              if (compare(p,q) != 0) break; 
  429.              X_structure.del_item(pqit);
  430.              Y_structure.change_inf(sitpred,nil);
  431.              sitpred = Y_structure.succ(sitpred);
  432.             }
  435.            /* search for sit downwards from sitmin: */
  437.            sit = sitmin;
  439.            seq_item sit1;
  440.            
  441.            while ((sit1=Y_structure.pred(sit)) != nil)
  442.            { pqit = Y_structure.inf(sit1);
  443.              if (pqit == nil) break;
  444.              point q = X_structure.inf(pqit);
  445.              if (compare(p,q) != 0) break; 
  446.              X_structure.del_item(pqit);
  447.              Y_structure.change_inf(sit1,nil);
  448.              sit = sit1;
  449.             }
  453.            // insert edges to p for all segments in sit, ..., sitpred into G
  454.            // and set left node to w 
  456.            lsit = Y_structure.key(sitpred);
  458.            node v = get_left_node(lsit);
  459.            if (v!=nil) G.new_edge(v,w);
  460.            set_left_node(lsit,w);
  462.            for(sit1=sit; sit1!=sitpred; sit1 = Y_structure.succ(sit1))
  463.            { lsit = Y_structure.key(sit1);
  465.              v = get_left_node(lsit);
  466.              if (v!=nil) G.new_edge(v,w);
  467.              set_left_node(lsit,w);
  468.             }
  470.            lsit = Y_structure.key(sit);
  471.            lpred=Y_structure.key(sitpred);
  472.            sitpredpred = Y_structure.pred(sit);
  473.            sitsucc=Y_structure.succ(sitpred);
  476.            if (sitpredpred != nil)
  477.             { 
  478.               lpredpred=Y_structure.key(sitpredpred);
  480.               if ((pqit = Y_structure.inf(sitpredpred)) != nil)
  481.                 delete Xdelete(pqit);
  483.               Y_structure.change_inf(sitpredpred,nil);
  486.               if (intersection(lpred,lpredpred,inter))
  487.                 Y_structure.change_inf(sitpredpred,
  488.                                        Xinsert(sitpredpred,inter));
  489.              }
  492.            if (sitsucc != nil)
  493.             {
  494.               lsucc=Y_structure.key(sitsucc);
  496.               if ((pqit = Y_structure.inf(sitpred)) != nil)
  497.                 delete Xdelete(pqit);
  498.                  
  499.               Y_structure.change_inf(sitpred,nil);
  501.               if (intersection(lsucc,lsit,inter))
  502.                   Y_structure.change_inf(sit,Xinsert(sit,inter));
  503.              }
  506. // reverse the subsequence sit, ... ,sitpred  in the Y_structure
  508.            x_sweep = get_x(p);
  509.            y_sweep = get_y(p);
  511.            Y_structure.reverse_items(sit,sitpred);
  513.           delete p;
  515.          } // intersection
  517.   }
  519.   X_structure.clear();
  520.   Y_structure.clear();
  524.   // normalize x and y coordinates 
  526.   node v;
  527.   forall_nodes(v,G) 
  528.   { xcoord[v] /= (x_sweep + MAX_X/12);
  529.     ycoord[v] /= MAX_Y;
  530.    }
  532. }