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 | } //namespace hugo |
---|