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: jacint@534: namespace hugo { 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: marci@558: } //namespace hugo