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