MinLCA algorithms
graph_utils.hh
Go to the documentation of this file.
1 #ifndef __MINLCA_UTILS_GRAPH_UTILS_H
2 #define __MINLCA_UTILS_GRAPH_UTILS_H
3 
4 #include <lemon/core.h>
5 #include <lemon/smart_graph.h>
6 #include <lemon/random.h>
7 #include <lemon/dim2.h>
8 #include <algorithm>
9 #include <iostream>
10 
13 
14 namespace minlca
15 {
16 namespace utils
17 {
18 
21  RMF,
22  GRA
23 };
24 
30 template<typename IS, typename Graph>
32  Graph &g,
33  int seed,
34  IS &in
35 )
36 {
37  using namespace std;
38  using namespace lemon;
39  TEMPLATE_GRAPH_TYPEDEFS(Graph);
40  string aux;
41  int m, n;
42  in >> aux >> aux >> n >> m;
43  g.clear();
44  g.reserveNode(n);
45  g.reserveEdge(m);
46 
47  vector<Node> vertices;
48  vertices.reserve(n);
49 
50  for (int i = 0; i < n; ++i) {
51  vertices.push_back(g.addNode());
52  }
53 
54  if (seed != 0) {
55  Random r(seed);
56 
57  for (int i = 0; i < n; ++i) {
58  swap(vertices[i], vertices[r.integer(i, n)]);
59  }
60  }
61 
62  while (in >> aux) {
63  int u, v;
64  in >> u >> v;
65  g.addEdge(vertices[u - 1], vertices[v - 1]);
66 
67  in >> aux;
68  }
69 }
70 
76 template<typename IS, typename Graph>
78  Graph &g,
79  int seed,
80  IS &in
81 )
82 {
83  using namespace std;
84  using namespace lemon;
85  TEMPLATE_GRAPH_TYPEDEFS(Graph);
86  int m, n;
87  in >> n >> m;
88  g.clear();
89  g.reserveNode(n);
90  g.reserveEdge(m);
91 
92  vector<Node> vertices;
93  vertices.reserve(n);
94 
95  vector<int> degrees(n, 0);
96 
97  for (int i = 0; i < n; ++i) {
98  vertices.push_back(g.addNode());
99  in >> degrees[i];
100  }
101 
102  if (seed != 0) {
103  Random r(seed);
104 
105  for (int i = 0; i < n; ++i) {
106  swap(vertices[i], vertices[r.integer(i, n)]);
107  }
108  }
109 
110  for (int u = 0; u < n; ++u) {
111  for (int i = 0; i < degrees[u]; ++i) {
112  int v;
113  in >> v;
114 
115  if (findEdge(g, vertices[u], vertices[v]) == INVALID) {
116  g.addEdge(vertices[u], vertices[v]);
117  }
118  }
119  }
120 }
121 
130 template<typename IS = std::istream, typename Graph = lemon::SmartGraph>
132  Graph &g,
133  int seed = 0,
134  GraphFormat f = RMF,
135  IS &in = std::cin
136 )
137 {
138  switch (f) {
139  case RMF:
140  readGraphRmfRandomOrder(g, seed, in);
141  break;
142 
143  case GRA:
144  readGraphGraRandomOrder(g, seed, in);
145  break;
146 
147  default:
148  break;
149  }
150 }
151 
159 template<typename IS = std::istream, typename Graph = lemon::SmartGraph>
161  Graph &g,
162  GraphFormat f = RMF,
163  IS &in = std::cin
164 )
165 {
166  readGraphRandomOrder(g, 0, f, in);
167 }
168 
170 template<typename Graph>
171 inline int degree(
172  const Graph &g,
173  const typename Graph::Node &v
174 )
175 {
176  return lemon::countIncEdges(g, v);
177 }
178 
180 template<typename Graph>
181 inline int maxDegree(
182  const Graph &g
183 )
184 {
185  using namespace lemon;
186  TEMPLATE_GRAPH_TYPEDEFS(Graph);
187  int deg = 0;
188 
189  for (NodeIt v(g); v != INVALID; ++v) {
190  deg = std::max(deg, degree(g, v));
191  }
192 
193  return deg;
194 }
195 
196 }
197 }
198 
199 #endif
GraphFormat
Available graph formats.
Definition: graph_utils.hh:20
void readGraphRmfRandomOrder(Graph &g, int seed, IS &in)
Read a graph in RMF format.
Definition: graph_utils.hh:31
void readGraph(Graph &g, GraphFormat f=RMF, IS &in=std::cin)
Read a graph.
Definition: graph_utils.hh:160
void readGraphGraRandomOrder(Graph &g, int seed, IS &in)
Read a graph in GRA format.
Definition: graph_utils.hh:77
LEMON namespace.
Definition: grb.cc:29
Default namespace Default namespace for MinLCA algorithms.
Definition: base.hh:15
int degree(const Graph &g, const typename Graph::Node &v)
Degree of a vertex.
Definition: graph_utils.hh:171
void readGraphRandomOrder(Graph &g, int seed=0, GraphFormat f=RMF, IS &in=std::cin)
Read a graph in random order.
Definition: graph_utils.hh:131
int maxDegree(const Graph &g)
Maximum degree of a graph.
Definition: graph_utils.hh:181