// -*- c++ -*-

#include <vector>

#include <cstdlib>

// ///\ingroup gwrappers

///\file

///\brief Graph generator functions.

///

///This file contains several graph generator functions.

///

// ///\author Marton Makai

namespace lemon {

  /**

   * 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 lemon