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 |
|
13 namespace 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 |
|