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