COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/graph_gen.h @ 598:1faa5bec1717

Last change on this file since 598:1faa5bec1717 was 598:1faa5bec1717, checked in by marci, 17 years ago

complete graphs

File size: 3.3 KB
Line 
1// -*- c++ -*-
2#include <vector>
3#include <cstdlib>
4
5namespace 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
Note: See TracBrowser for help on using the repository browser.