jacint@534: // -*- c++ -*-
jacint@534: #include <vector>
jacint@534: #include <cstdlib>
jacint@534: 
marci@605: // ///\ingroup gwrappers
marci@605: ///\file
marci@605: ///\brief Graph generator functions.
marci@605: ///
marci@605: ///This file contains several graph generator functions.
marci@605: ///
marci@605: // ///\author Marton Makai
marci@605: 
alpar@921: namespace lemon {
jacint@534: 
jacint@534: 
jacint@534:   /**
jacint@534:    * Inicializalja a veletlenszamgeneratort.
jacint@534:    * Figyelem, ez nem jo igazi random szamokhoz,
jacint@534:    * erre ne bizzad a titkaidat!
jacint@534:    */
jacint@534:   void random_init()
jacint@534:   {
jacint@534:     unsigned int seed = getpid();
jacint@534:     seed |= seed << 15;
jacint@534:     seed ^= time(0);
jacint@534: 
jacint@534:     srand(seed);
jacint@534:   }
jacint@534: 
jacint@534: 
jacint@534:   /**
jacint@534:    * Egy veletlen int-et ad vissza 0 es m-1 kozott.
jacint@534:    */
jacint@534:   int random(int m)
jacint@534:   {
jacint@534:     return int( double(m) * rand() / (RAND_MAX + 1.0) );
jacint@534:   }
jacint@534: 
jacint@534: 
marci@558:   /// Generates a random graph with n nodes and m edges.
marci@558:   /// Before generating the random graph, \c g.clear() is called.
jacint@534:   template<typename Graph>
marci@558:   void randomGraph(Graph& g, int n, int m) {
jacint@534:     g.clear();
marci@558:     std::vector<typename Graph::Node> nodes;
jacint@534:     for (int i=0; i<n; ++i)
jacint@534:       nodes.push_back(g.addNode());
jacint@534:     for (int i=0; i<m; ++i) 
jacint@534:       g.addEdge(nodes[random(n)], nodes[random(n)]);
jacint@534:   }
jacint@534: 
marci@558:   /// Generates a random bipartite graph with a and b nodes 
marci@558:   /// in the color classes and m edges.
marci@558:   /// According to the bipartite graph concept, the resulting 
marci@558:   /// graph is directed from the first class to the second one.
marci@558:   /// Before generating the random graph, \c g.clear() is called.
marci@558:   template<typename Graph>
marci@558:   void randomBipartiteGraph(Graph& g, int a, int b, int m) {
marci@558:     g.clear();
marci@558:     std::vector<typename Graph::Node> s_nodes;
marci@558:     std::vector<typename Graph::Node> t_nodes;
marci@558:     for (int i=0; i<a; ++i)
marci@558:       ///\bug g.addNode(g.S_CLASS) would be better.
marci@558:       s_nodes.push_back(g.addNode(false));
marci@558:     for (int i=0; i<b; ++i)
marci@558:       ///\bug g.addNode(g.T_CLASS) would be better.
marci@558:       t_nodes.push_back(g.addNode(true));
marci@558:     for (int i=0; i<m; ++i) 
marci@558:       g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
marci@558:   }
marci@558: 
marci@593:   /// Generates a complete graph in the undirected sense 
marci@598:   /// with n nodes.
marci@593:   /// Before generating the random graph, \c g.clear() is called.
marci@593:   template<typename Graph>
marci@593:   void completeGraph(Graph& g, int n) {
marci@593:     g.clear();
marci@593:     std::vector<typename Graph::Node> nodes;
marci@593:     for (int i=0; i<n; ++i)
marci@593:       nodes.push_back(g.addNode());
marci@593:     for (int i=0; i<n; ++i) 
marci@593:       for (int j=i+1; j<n; ++j)
marci@593: 	g.addEdge(nodes[i], nodes[j]);
marci@593:   }
marci@598: 
marci@598:   /// Generates a complete bidirected graph on n nodes.
marci@598:   /// Before generating the random graph, \c g.clear() is called.
marci@598:   template<typename Graph>
marci@598:   void completeBidirectedGraph(Graph& g, int n) {
marci@598:     g.clear();
marci@598:     std::vector<typename Graph::Node> nodes;
marci@598:     for (int i=0; i<n; ++i)
marci@598:       nodes.push_back(g.addNode());
marci@598:     for (int i=0; i<n; ++i) 
marci@598:       for (int j=i+1; j<n; ++j) {
marci@598: 	g.addEdge(nodes[i], nodes[j]);	
marci@598: 	g.addEdge(nodes[j], nodes[i]);
marci@598:       }
marci@598:   }
marci@598: 
marci@598:   /// Generates a complete bipartite graph with a and b nodes 
marci@598:   /// in the color classes.
marci@598:   /// Before generating the random graph, \c g.clear() is called.
marci@598:   template<typename Graph>
marci@598:   void completeBipartiteGraph(Graph& g, int a, int b) {
marci@598:     g.clear();
marci@598:     std::vector<typename Graph::Node> s_nodes;
marci@598:     std::vector<typename Graph::Node> t_nodes;
marci@598:     for (int i=0; i<a; ++i)
marci@598:       ///\bug g.addNode(g.S_CLASS) would be better.
marci@598:       s_nodes.push_back(g.addNode(false));
marci@598:     for (int i=0; i<b; ++i)
marci@598:       ///\bug g.addNode(g.T_CLASS) would be better.
marci@598:       t_nodes.push_back(g.addNode(true));
marci@598:     for (int i=0; i<a; ++i) 
marci@598:       for (int j=0; j<b; ++j)       
marci@598: 	g.addEdge(s_nodes[i], t_nodes[j]);
marci@598:   }
marci@593:   
alpar@921: } //namespace lemon