home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph / _g_misc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  7.2 KB  |  346 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _g_misc.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/graph.h>
  17. #include <LEDA/ugraph.h>
  18.  
  19. declare(list,int)
  20.  
  21. declare(node_array,int)
  22.  
  23. node_array(int)* num_ptr;
  24.  
  25. int epe_source_num(edge& e) { return (*num_ptr)[source(e)]; }
  26. int epe_target_num(edge& e) { return (*num_ptr)[target(e)]; }
  27.  
  28. void eliminate_parallel_edges(graph& G)
  29. { // eliminate parallel edges by bucket sort 
  30.  
  31.   list(edge) el = G.all_edges();
  32.   node v;
  33.   edge e;
  34.   int  n = 0;
  35.  
  36.   node_array(int) num(G);
  37.   forall_nodes(v,G) num[v] = n++;
  38.   
  39.   num_ptr = #
  40.  
  41.   el.bucket_sort(0,n-1,&epe_source_num);
  42.   el.bucket_sort(0,n-1,&epe_target_num);
  43.   
  44.   int i = -1;
  45.   int j = -1; 
  46.   forall(e,el)  
  47.     { if (j==num[source(e)] && i==num[target(e)]) 
  48.         G.del_edge(e);
  49.       else 
  50.         { j=num[source(e)];
  51.           i=num[target(e)];
  52.          }
  53.      }
  54.   
  55.  }
  56.  
  57.  
  58. // some special graphs
  59.  
  60. void complete_graph(graph& G, int n)
  61. { node v,w;
  62.   G.clear();
  63.   while (n--) G.new_node();
  64.   forall_node_pairs(v,w,G) G.new_edge(v,w);
  65. }
  66.  
  67. void complete_graph(ugraph& G, int n)
  68. { int i,j;
  69.   node* V = new node[n];
  70.   G.clear();
  71.   for(i=0;i<n;i++) V[i] = G.new_node();
  72.   for(i=0;i<n;i++) 
  73.     for(j=i+1;j<n;j++) 
  74.        G.new_edge(V[i],V[j]);
  75. }
  76.  
  77.  
  78. void random_graph(graph& G, int n, int m)
  79. { /* random graph with n nodes and m edges */ 
  80.  
  81.  int i;
  82.  node* V = new node[n];
  83.  G.clear();
  84.  for(i=0;i<n;i++) V[i] = G.new_node();
  85.  
  86.  init_random();
  87.  while (m--) G.new_edge(V[random(0,n-1)],V[random(0,n-1)]);
  88.  
  89. /*
  90.  int deg = m/n;
  91.  int r = m%n;
  92.  int k;
  93.  for(i=0;i<n;i++)
  94.    for(k=0;k<deg;k++)
  95.       G.new_edge(V[i],V[random(0,n-1)]);
  96.  while (r--) G.new_edge(V[random(0,n-1)],V[random(0,n-1)]);
  97. */
  98.  
  99. }
  100.  
  101. void random_graph(ugraph& G, int n, int m)
  102. { int i;
  103.  node* V = new node[n];
  104.  G.clear();
  105.  for(i=0;i<n;i++) V[i] = G.new_node();
  106.  init_random();
  107.  while (m--) G.new_edge(V[random(0,n-1)],V[random(0,n-1)]);
  108. }
  109.  
  110.  
  111. void random_planar_graph(graph& G, int n)
  112. { G.clear();
  113.  
  114.   edge*  R = new edge[2*n];
  115.   edge*  E = new edge[2*n];
  116.  
  117.   node a = G.new_node();
  118.   node b = G.new_node();
  119.  
  120.   E[3] = G.new_edge(a,b);
  121.   R[3] = G.new_edge(b,a);
  122.  
  123.   for (int i=4; i<2*n; i++)
  124.    { edge e = E[i-1];
  125.      edge r = R[i-1];
  126.  
  127.      a = G.new_node();
  128.  
  129.      E[i] = G.new_edge(a,source(e));
  130.      R[i] = G.new_edge(e,a,after);
  131.  
  132.      i++;
  133.  
  134.      E[i] = G.new_edge(r,a,before);
  135.      R[i] = G.new_edge(a,target(e));
  136.    }
  137.  
  138.  //for(i=3;i<2*n;i++) G.del_edge(R[i]);
  139.  
  140. }
  141.  
  142. void user_graph(graph& G)
  143. { int  n = read_int("|V| = ");
  144.   int  i,j;
  145.  
  146.   node* V = new node[n];
  147.   for(j=0; j<n; j++) V[j] = G.new_node();
  148.  
  149.   for(j=0; j<n; j++) 
  150.   { list(int) il;
  151.     bool ok = false;
  152.     while (!ok)
  153.     { ok = true;
  154.       cout << "edges from [" << j << "] to: ";
  155.       il.read();
  156.       forall(i,il) 
  157.         if (i < 0 || i >= n) 
  158.         { ok=false;
  159.           cout << "illegal node " << i << "\n";
  160.          }
  161.      }
  162.     forall(i,il) G.new_edge(V[j],V[i]);
  163.   }
  164.   G.print();
  165.   if (Yes("save graph ? ")) G.write(read_string("file: "));
  166. }
  167.  
  168.  
  169.  
  170. void test_graph(graph& G)
  171. { 
  172.   G.clear();
  173.   char c;
  174.  
  175.   do c = read_char("graph: f(ile) r(andom) c(omplete) p(lanar) u(ser): ");
  176.   while (c!='f' && c!='r' && c!='c' && c!='p'&& c!='u');   
  177.  
  178.   switch (c) {
  179.  
  180.    case 'f' : { G.read(read_string("file: "));
  181.                 break;
  182.                }
  183.  
  184.    case 'u' : { user_graph(G);
  185.                 break;
  186.                }
  187.  
  188.    case 'c' : { complete_graph(G,read_int("|V| = "));
  189.                 break;
  190.                }
  191.  
  192.    case 'r' : { int n = read_int("|V| = ");
  193.                 int m = read_int("|E| = ");
  194.                 random_graph(G,n,m);
  195.                 break;
  196.                }
  197.  
  198.    case 'p' : { random_planar_graph(G,read_int("|V| = "));
  199.                 break;
  200.                }
  201.    }//switch
  202.  
  203. }
  204.  
  205. void test_graph(ugraph& G)
  206. { 
  207.   G.clear();
  208.   char c;
  209.  
  210.   do c = read_char("graph: f(ile) r(andom) c(omplete) p(lanar) u(ser): ");
  211.   while (c!='f' && c!='r' && c!='c' && c!='p'&& c!='u');   
  212.  
  213.   int  i;
  214.   node v;
  215.   
  216.   switch (c) {
  217.  
  218.   case 'f' : { G.read(read_string("file: "));
  219.                break;
  220.               }
  221.  
  222.    case 'u' : { int  n = read_int("|V| = ");
  223.                 int  j = 0;
  224.                 node* V = new node[n];
  225.                 loop(i,0,n-1) V[i] = G.new_node();
  226.                 forall_nodes(v,G)
  227.                   { list(int) il;
  228.                     cout << "edges from " << j++ << " to: ";
  229.                     il.read();
  230.                     forall(i,il) 
  231.                       if (i >= 0 && i < n) G.new_edge(v,V[i]);
  232.                       else cerr << "illegal node " << i << " (ignored)\n";
  233.                    }
  234.                 G.print();
  235.                 if (Yes("save graph ? ")) G.write(read_string("file: "));
  236.                 break;
  237.                }
  238.  
  239.    case 'c' : { int n = read_int("|V| = ");
  240.                 complete_graph(G,n);
  241.                 break;
  242.                }
  243.  
  244.    case 'r' : { int n = read_int("|V| = ");
  245.                 int m = read_int("|E| = ");
  246.                 random_graph(G,n,m);
  247.                 break;
  248.                }
  249.  
  250.    }//switch
  251.  
  252. }
  253.  
  254.  
  255.  
  256.  
  257.  
  258. void test_bigraph(graph& G, list(node)& A, list(node)& B)
  259. {
  260.   int  a,b,n1,n2;
  261.   char c;
  262.  
  263.   do c = read_char("bipartite graph: f(ile) r(andom) c(omplete) u(ser): ");
  264.   while (c!='f' && c!='r' && c!='c' && c!='u');   
  265.  
  266.   A.clear();
  267.   B.clear();
  268.   G.clear();
  269.  
  270.   if (c!='f') 
  271.    { n1 = read_int("|A| = ");
  272.      n2 = read_int("|B| = ");
  273.     }
  274.   
  275.   
  276.   switch (c) {
  277.  
  278.   case 'f' : { G.read(read_string("file: "));
  279.                node v;
  280.                forall_nodes(v,G) 
  281.                if (G.outdeg(v) > 0) A.append(v);
  282.                else B.append(v);
  283.  
  284.                break;
  285.               }
  286.  
  287.    case 'u' : { node* AV = new node[n1+1];
  288.                 node* BV = new node[n2+1];
  289.  
  290.                 loop(a,1,n1)  A.append(AV[a] = G.new_node());
  291.                 loop(b,1,n2)  B.append(BV[b] = G.new_node());
  292.  
  293.                 loop(a,1,n1)
  294.                   { list(int) il;
  295.                     cout << "edges from " << a << " to: ";
  296.                     il.read();
  297.                     forall(b,il) if (b<=n2) G.new_edge(AV[a],BV[b]);
  298.                                  else break;
  299.                     if (b>n2) break;
  300.                    }
  301.                 break;
  302.                }
  303.  
  304.    case 'c' : { loop(a,1,n1)  A.append(G.new_node());
  305.                 loop(b,1,n2)  B.append(G.new_node());
  306.  
  307.                 node v,w;
  308.  
  309.                 forall(v,A) 
  310.                   forall(w,B) 
  311.                     G.new_edge(v,w);
  312.  
  313.                 break;
  314.                }
  315.  
  316.    case 'r' : { int  m = read_int("|E| = ");
  317.  
  318.                 int  d = m/n1; 
  319.                 int  r = m%n1; 
  320.  
  321.                 node* AV = new node[n1+1];
  322.                 node* BV = new node[n2+1];
  323.  
  324.                 loop(a,1,n1)  A.append(AV[a] = G.new_node());
  325.                 loop(b,1,n2)  B.append(BV[b] = G.new_node());
  326.  
  327.                 node v;
  328.                 int i;
  329.  
  330.                 init_random();
  331.                 forall(v,A)
  332.                   for(i=0;i<d;i++)
  333.                     G.new_edge(v,BV[random(1,n2)]);
  334.  
  335.                 while (r--) G.new_edge(AV[random(1,n1)], BV[random(1,n2)]);
  336.  
  337.  
  338.                 break;
  339.                }
  340.  
  341.        } // switch
  342.  
  343. }
  344.  
  345.  
  346.