Bug fixes.
5 // ///\ingroup gwrappers
7 ///\brief Graph generator functions.
9 ///This file contains several graph generator functions.
11 // ///\author Marton Makai
17 * Inicializalja a veletlenszamgeneratort.
18 * Figyelem, ez nem jo igazi random szamokhoz,
19 * erre ne bizzad a titkaidat!
23 unsigned int seed = getpid();
32 * Egy veletlen int-et ad vissza 0 es m-1 kozott.
36 return int( double(m) * rand() / (RAND_MAX + 1.0) );
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) {
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)]);
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) {
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)]);
72 /// Generates a complete graph in the undirected sense
74 /// Before generating the random graph, \c g.clear() is called.
75 template<typename Graph>
76 void completeGraph(Graph& g, int n) {
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]);
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) {
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]);
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) {
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]);