36 { |
27 { |
37 return int( double(m) * rand() / (RAND_MAX + 1.0) ); |
28 return int( double(m) * rand() / (RAND_MAX + 1.0) ); |
38 } |
29 } |
39 |
30 |
40 |
31 |
|
32 /// Generates a random graph with n nodes and m edges. |
|
33 /// Before generating the random graph, \c g.clear() is called. |
41 template<typename Graph> |
34 template<typename Graph> |
42 void randomGraph (Graph& g, int n, int m) { |
35 void randomGraph(Graph& g, int n, int m) { |
43 typedef typename Graph::Node Node; |
|
44 g.clear(); |
36 g.clear(); |
45 std::vector<Node> nodes; |
37 std::vector<typename Graph::Node> nodes; |
46 for (int i=0; i<n; ++i) |
38 for (int i=0; i<n; ++i) |
47 nodes.push_back(g.addNode()); |
39 nodes.push_back(g.addNode()); |
48 for (int i=0; i<m; ++i) |
40 for (int i=0; i<m; ++i) |
49 g.addEdge(nodes[random(n)], nodes[random(n)]); |
41 g.addEdge(nodes[random(n)], nodes[random(n)]); |
50 } |
42 } |
51 |
43 |
52 } |
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 } //namespace hugo |