COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/graph_gen.h @ 921:818510fa3d99

Last change on this file since 921:818510fa3d99 was 921:818510fa3d99, checked in by Alpar Juttner, 17 years ago

hugo -> lemon

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