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