_g_misc.c

数据类型和算法库LEDA 数据类型和算法库LEDA

/*******************************************************************************
+
+  LEDA  3.0
+
+
+  _g_misc.c
+
+
+  Copyright (c) 1992  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 6600 Saarbruecken, FRG     
+  All rights reserved.
+ 
*******************************************************************************/


#include <LEDA/graph.h>
#include <LEDA/ugraph.h>
#include <ctype.h>



node_array<int>* num_ptr;

int epe_source_num(edge& e) { return (*num_ptr)[source(e)]; }
int epe_target_num(edge& e) { return (*num_ptr)[target(e)]; }

void eliminate_parallel_edges(graph& G)
{ 
  //use bucket sort to find and eliminate parallel edges

  list<edge> el = G.all_edges();
  node v;
  edge e;
  int  n = 0;

  node_array<int> num(G);
  forall_nodes(v,G) num[v] = n++;
  
  num_ptr = &num;

  el.bucket_sort(0,n-1,&epe_source_num);
  el.bucket_sort(0,n-1,&epe_target_num);
  
  int i = -1;
  int j = -1; 
  forall(e,el)  
    { if (j==num[source(e)] && i==num[target(e)]) 
        G.del_edge(e);
      else 
        { j=num[source(e)];
          i=num[target(e)];
         }
     }
  
 }


// some special graphs

void complete_graph(graph& G, int n)
{ node v,w;
  G.clear();
  while (n--) G.new_node();
  forall_node_pairs(v,w,G) G.new_edge(v,w);
}

void complete_ugraph(ugraph& G, int n)
{ int i,j;
  node* V = new node[n];
  G.clear();
  for(i=0;i<n;i++) V[i] = G.new_node();
  for(i=0;i<n;i++) 
    for(j=i+1;j<n;j++) 
       G.new_edge(V[i],V[j]);
}

void complete_bigraph(graph& G, int n1, int n2, list<node>& A, list<node>& B)
{ node v,w;

  for(int a=0; a < n1; a++)  A.append(G.new_node());
  for(int b=0; b < n2; b++)  B.append(G.new_node());

  forall(v,A) 
    forall(w,B) 
       G.new_edge(v,w);
 }


void random_graph(graph& G, int n, int m)
{ /* random graph with n nodes and m edges */ 

 int i;
 node* V = new node[n];
 G.clear();
 for(i=0;i<n;i++) V[i] = G.new_node();

 while (m--) G.new_edge(V[random(0,n-1)],V[random(0,n-1)]);

/*
 int deg = m/n;
 int r = m%n;
 int k;
 for(i=0;i<n;i++)
   for(k=0;k<deg;k++)
      G.new_edge(V[i],V[random(0,n-1)]);
 while (r--) G.new_edge(V[random(0,n-1)],V[random(0,n-1)]);
*/

}

void random_ugraph(ugraph& G, int n, int m)
{ int i;
 node* V = new node[n];
 G.clear();
 for(i=0;i<n;i++) V[i] = G.new_node();
 while (m--) G.new_edge(V[random(0,n-1)],V[random(0,n-1)]);
}

void random_bigraph(graph& G,int n1,int n2,int m,list<node>& A,list<node>& B)
{
   int  d = m/n1; 
   int  r = m%n1; 

   node* AV = new node[n1];
   node* BV = new node[n2];

   for(int a = 0; a < n1; a++)  A.append(AV[a] = G.new_node());
   for(int b = 0; b < n2; b++)  B.append(BV[b] = G.new_node());

   node v;
   int i;

   forall(v,A)
     for(i=0;i<d;i++)
       G.new_edge(v,BV[random(0,n2-1)]);

   while (r--) G.new_edge(AV[random(0,n1-1)], BV[random(0,n2-1)]);

}


void random_planar_graph(graph& G, int n)
{ G.clear();

  edge*  R = new edge[2*n];
  edge*  E = new edge[2*n];

  node a = G.new_node();
  node b = G.new_node();

  E[3] = G.new_edge(a,b);
  R[3] = G.new_edge(b,a);

  for (int i=4; i<2*n; i++)
   { edge e = E[i-1];
     edge r = R[i-1];

     a = G.new_node();

     E[i] = G.new_edge(a,source(e));
     R[i] = G.new_edge(e,a,after);

     i++;

     E[i] = G.new_edge(r,a,before);
     R[i] = G.new_edge(a,target(e));
   }

 //for(i=3;i<2*n;i++) G.del_edge(R[i]);

}

void user_graph(graph& G)
{ int  n = read_int("|V| = ");
  int  i,j;

  node* V = new node[n];
  for(j=0; j<n; j++) V[j] = G.new_node();

  for(j=0; j<n; j++) 
  { list<int> il;
    bool ok = false;
    while (!ok)
    { ok = true;
      cout << "edges from [" << j << "] to: ";
      il.read();
      forall(i,il) 
        if (i < 0 || i >= n) 
        { ok=false;
          cout << "illegal node " << i << "\n";
         }
     }
    forall(i,il) G.new_edge(V[j],V[i]);
  }
  G.print();
  if (Yes("save graph ? ")) G.write(read_string("file: "));
}



void test_graph(graph& G)
{ 
  G.clear();
  char c;

  do c = read_char("graph: f(ile) r(andom) c(omplete) p(lanar) u(ser): ");
  while (c!='f' && c!='r' && c!='c' && c!='p'&& c!='u');   

  switch (c) {

   case 'f' : { G.read(read_string("file: "));
                break;
               }

   case 'u' : { user_graph(G);
                break;
               }

   case 'c' : { complete_graph(G,read_int("|V| = "));
                break;
               }

   case 'r' : { int n = read_int("|V| = ");
                int m = read_int("|E| = ");
                random_graph(G,n,m);
                break;
               }

   case 'p' : { random_planar_graph(G,read_int("|V| = "));
                break;
               }
   }//switch

}

void test_ugraph(ugraph& G)
{ 
  G.clear();
  char c;

  do c = read_char("graph: f(ile) r(andom) c(omplete) p(lanar) u(ser): ");
  while (c!='f' && c!='r' && c!='c' && c!='p'&& c!='u');   

  int  i;
  node v;
  
  switch (c) {

  case 'f' : { G.read(read_string("file: "));
               break;
              }

   case 'u' : { int  n = read_int("|V| = ");
                int  j = 0;
                node* V = new node[n];
                loop(i,0,n-1) V[i] = G.new_node();
                forall_nodes(v,G)
                  { list<int> il;
                    cout << "edges from " << j++ << " to: ";
                    il.read();
                    forall(i,il) 
                      if (i >= 0 && i < n) G.new_edge(v,V[i]);
                      else cerr << "illegal node " << i << " (ignored)\n";
                   }
                G.print();
                if (Yes("save graph ? ")) G.write(read_string("file: "));
                break;
               }

   case 'c' : { int n = read_int("|V| = ");
                complete_graph(G,n);
                break;
               }

   case 'r' : { int n = read_int("|V| = ");
                int m = read_int("|E| = ");
                random_graph(G,n,m);
                break;
               }

   }//switch

}





void test_bigraph(graph& G, list<node>& A, list<node>& B)
{
  int  a,b,n1,n2;
  char c;

  do c = read_char("bipartite graph: f(ile) r(andom) c(omplete) u(ser): ");
  while (c!='f' && c!='r' && c!='c' && c!='u');   

  A.clear();
  B.clear();
  G.clear();

  if (c!='f') 
   { n1 = read_int("|A| = ");
     n2 = read_int("|B| = ");
    }
  
  
  switch (c) {

  case 'f' : { G.read(read_string("file: "));
               node v;
               forall_nodes(v,G) 
               if (G.outdeg(v) > 0) A.append(v);
               else B.append(v);

               break;
              }

   case 'u' : { node* AV = new node[n1+1];
                node* BV = new node[n2+1];

                loop(a,1,n1)  A.append(AV[a] = G.new_node());
                loop(b,1,n2)  B.append(BV[b] = G.new_node());

                loop(a,1,n1)
                  { list<int> il;
                    cout << "edges from " << a << " to: ";
                    il.read();
                    forall(b,il) if (b<=n2) G.new_edge(AV[a],BV[b]);
                                 else break;
                    if (b>n2) break;
                   }
                break;
               }

   case 'c' : complete_bigraph(G,n1,n2,A,B);
              break;

   case 'r' : { int m = read_int("|E| = ");
                random_bigraph(G,n1,n2,m,A,B);
                break;
               }

       } // switch

}



void cmdline_graph(graph& G, int argc, char** argv)
{ 
  // construct graph from cmdline arguments

  if (argc == 1)           // no arguments 
     { test_graph(G);
       return;
      }
  else 
     if (argc == 2)       // one argument
        { if (isdigit(argv[1][0])) 
             { cout << "complete graph |V| = " << argv[1];
               newline;
               newline;
               complete_graph(G,atoi(argv[1]));
              }
          else 
             { cout << "reading graph from file " << argv[1];
               newline;
               newline;
               G.read(argv[1]);
              }
          return;
         }
     else
        if (argc == 3 && isdigit(argv[1][0]) && isdigit(argv[1][0])) 
           { cout << "random graph |V| = " << argv[1] << "  |E| = " << argv[2];
             newline;
             newline;
             random_graph(G,atoi(argv[1]),atoi(argv[2]));
             return;
            }

  error_handler(1,"cmdline_graph: illegal arguments");
}