source: lemon-0.x/src/work/jacint/graph_gen.h @ 628:a3a53d7cedc2

// -*- c++ -*-
#include <vector>
#include <cstdlib>

// ///\ingroup gwrappers
///\file
///\brief Graph generator functions.
///
///This file contains several graph generator functions.
///
// ///\author Marton Makai

namespace hugo {


  /**
   * Inicializalja a veletlenszamgeneratort.
   * Figyelem, ez nem jo igazi random szamokhoz,
   * erre ne bizzad a titkaidat!
   */
  void random_init()
  {
    unsigned int seed = getpid();
    seed |= seed << 15;
    seed ^= time(0);

    srand(seed);
  }


  /**
   * Egy veletlen int-et ad vissza 0 es m-1 kozott.
   */
  int random(int m)
  {
    return int( double(m) * rand() / (RAND_MAX + 1.0) );
  }


  /// Generates a random graph with n nodes and m edges.
  /// Before generating the random graph, \c g.clear() is called.
  template<typename Graph>
  void randomGraph(Graph& g, int n, int m) {
    g.clear();
    std::vector<typename Graph::Node> nodes;
    for (int i=0; i<n; ++i)
      nodes.push_back(g.addNode());
    for (int i=0; i<m; ++i) 
      g.addEdge(nodes[random(n)], nodes[random(n)]);
  }

  /// Generates a random bipartite graph with a and b nodes 
  /// in the color classes and m edges.
  /// According to the bipartite graph concept, the resulting 
  /// graph is directed from the first class to the second one.
  /// Before generating the random graph, \c g.clear() is called.
  template<typename Graph>
  void randomBipartiteGraph(Graph& g, int a, int b, int m) {
    g.clear();
    std::vector<typename Graph::Node> s_nodes;
    std::vector<typename Graph::Node> t_nodes;
    for (int i=0; i<a; ++i)
      ///\bug g.addNode(g.S_CLASS) would be better.
      s_nodes.push_back(g.addNode(false));
    for (int i=0; i<b; ++i)
      ///\bug g.addNode(g.T_CLASS) would be better.
      t_nodes.push_back(g.addNode(true));
    for (int i=0; i<m; ++i) 
      g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
  }

  /// Generates a complete graph in the undirected sense 
  /// with n nodes.
  /// Before generating the random graph, \c g.clear() is called.
  template<typename Graph>
  void completeGraph(Graph& g, int n) {
    g.clear();
    std::vector<typename Graph::Node> nodes;
    for (int i=0; i<n; ++i)
      nodes.push_back(g.addNode());
    for (int i=0; i<n; ++i) 
      for (int j=i+1; j<n; ++j)
        g.addEdge(nodes[i], nodes[j]);
  }

  /// Generates a complete bidirected graph on n nodes.
  /// Before generating the random graph, \c g.clear() is called.
  template<typename Graph>
  void completeBidirectedGraph(Graph& g, int n) {
    g.clear();
    std::vector<typename Graph::Node> nodes;
    for (int i=0; i<n; ++i)
      nodes.push_back(g.addNode());
    for (int i=0; i<n; ++i) 
      for (int j=i+1; j<n; ++j) {
        g.addEdge(nodes[i], nodes[j]);  
        g.addEdge(nodes[j], nodes[i]);
      }
  }

  /// Generates a complete bipartite graph with a and b nodes 
  /// in the color classes.
  /// Before generating the random graph, \c g.clear() is called.
  template<typename Graph>
  void completeBipartiteGraph(Graph& g, int a, int b) {
    g.clear();
    std::vector<typename Graph::Node> s_nodes;
    std::vector<typename Graph::Node> t_nodes;
    for (int i=0; i<a; ++i)
      ///\bug g.addNode(g.S_CLASS) would be better.
      s_nodes.push_back(g.addNode(false));
    for (int i=0; i<b; ++i)
      ///\bug g.addNode(g.T_CLASS) would be better.
      t_nodes.push_back(g.addNode(true));
    for (int i=0; i<a; ++i) 
      for (int j=0; j<b; ++j)       
        g.addEdge(s_nodes[i], t_nodes[j]);
  }
  
} //namespace hugo