src/work/jacint/graph_gen.h
author deba
Wed, 08 Sep 2004 12:06:45 +0000 (2004-09-08)
changeset 822 88226d9fe821
parent 598 1faa5bec1717
child 921 818510fa3d99
permissions -rw-r--r--
The MapFactories have been removed from the code because
if we use macros then they increases only the complexity.

The pair iterators of the maps are separeted from the maps.

Some macros and comments has been changed.
     1 // -*- c++ -*-
     2 #include <vector>
     3 #include <cstdlib>
     4 
     5 // ///\ingroup gwrappers
     6 ///\file
     7 ///\brief Graph generator functions.
     8 ///
     9 ///This file contains several graph generator functions.
    10 ///
    11 // ///\author Marton Makai
    12 
    13 namespace hugo {
    14 
    15 
    16   /**
    17    * Inicializalja a veletlenszamgeneratort.
    18    * Figyelem, ez nem jo igazi random szamokhoz,
    19    * erre ne bizzad a titkaidat!
    20    */
    21   void random_init()
    22   {
    23     unsigned int seed = getpid();
    24     seed |= seed << 15;
    25     seed ^= time(0);
    26 
    27     srand(seed);
    28   }
    29 
    30 
    31   /**
    32    * Egy veletlen int-et ad vissza 0 es m-1 kozott.
    33    */
    34   int random(int m)
    35   {
    36     return int( double(m) * rand() / (RAND_MAX + 1.0) );
    37   }
    38 
    39 
    40   /// Generates a random graph with n nodes and m edges.
    41   /// Before generating the random graph, \c g.clear() is called.
    42   template<typename Graph>
    43   void randomGraph(Graph& g, int n, int m) {
    44     g.clear();
    45     std::vector<typename Graph::Node> nodes;
    46     for (int i=0; i<n; ++i)
    47       nodes.push_back(g.addNode());
    48     for (int i=0; i<m; ++i) 
    49       g.addEdge(nodes[random(n)], nodes[random(n)]);
    50   }
    51 
    52   /// Generates a random bipartite graph with a and b nodes 
    53   /// in the color classes and m edges.
    54   /// According to the bipartite graph concept, the resulting 
    55   /// graph is directed from the first class to the second one.
    56   /// Before generating the random graph, \c g.clear() is called.
    57   template<typename Graph>
    58   void randomBipartiteGraph(Graph& g, int a, int b, int m) {
    59     g.clear();
    60     std::vector<typename Graph::Node> s_nodes;
    61     std::vector<typename Graph::Node> t_nodes;
    62     for (int i=0; i<a; ++i)
    63       ///\bug g.addNode(g.S_CLASS) would be better.
    64       s_nodes.push_back(g.addNode(false));
    65     for (int i=0; i<b; ++i)
    66       ///\bug g.addNode(g.T_CLASS) would be better.
    67       t_nodes.push_back(g.addNode(true));
    68     for (int i=0; i<m; ++i) 
    69       g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
    70   }
    71 
    72   /// Generates a complete graph in the undirected sense 
    73   /// with n nodes.
    74   /// Before generating the random graph, \c g.clear() is called.
    75   template<typename Graph>
    76   void completeGraph(Graph& g, int n) {
    77     g.clear();
    78     std::vector<typename Graph::Node> nodes;
    79     for (int i=0; i<n; ++i)
    80       nodes.push_back(g.addNode());
    81     for (int i=0; i<n; ++i) 
    82       for (int j=i+1; j<n; ++j)
    83 	g.addEdge(nodes[i], nodes[j]);
    84   }
    85 
    86   /// Generates a complete bidirected graph on n nodes.
    87   /// Before generating the random graph, \c g.clear() is called.
    88   template<typename Graph>
    89   void completeBidirectedGraph(Graph& g, int n) {
    90     g.clear();
    91     std::vector<typename Graph::Node> nodes;
    92     for (int i=0; i<n; ++i)
    93       nodes.push_back(g.addNode());
    94     for (int i=0; i<n; ++i) 
    95       for (int j=i+1; j<n; ++j) {
    96 	g.addEdge(nodes[i], nodes[j]);	
    97 	g.addEdge(nodes[j], nodes[i]);
    98       }
    99   }
   100 
   101   /// Generates a complete bipartite graph with a and b nodes 
   102   /// in the color classes.
   103   /// Before generating the random graph, \c g.clear() is called.
   104   template<typename Graph>
   105   void completeBipartiteGraph(Graph& g, int a, int b) {
   106     g.clear();
   107     std::vector<typename Graph::Node> s_nodes;
   108     std::vector<typename Graph::Node> t_nodes;
   109     for (int i=0; i<a; ++i)
   110       ///\bug g.addNode(g.S_CLASS) would be better.
   111       s_nodes.push_back(g.addNode(false));
   112     for (int i=0; i<b; ++i)
   113       ///\bug g.addNode(g.T_CLASS) would be better.
   114       t_nodes.push_back(g.addNode(true));
   115     for (int i=0; i<a; ++i) 
   116       for (int j=0; j<b; ++j)       
   117 	g.addEdge(s_nodes[i], t_nodes[j]);
   118   }
   119   
   120 } //namespace hugo