mCRL2
Searching...
No Matches
Graph.h
Go to the documentation of this file.
1// Copyright (c) 2009-2013 University of Twente
2// Copyright (c) 2009-2013 Michael Weber <michaelw@cs.utwente.nl>
3// Copyright (c) 2009-2013 Maks Verver <maksverver@geocities.com>
4// Copyright (c) 2009-2013 Eindhoven University of Technology
5//
7// (See accompanying file LICENSE_1_0.txt or copy at
9
15#ifndef MCRL2_PG_GRAPH_H
16#define MCRL2_PG_GRAPH_H
17
18#include <algorithm>
19#include <iostream>
20#include <utility>
21#include <vector>
22
23// Note: these should be unsigned types; some algorithms depend on it!
24typedef std::size_t verti;
25typedef std::size_t edgei;
26
27#define NO_VERTEX ((verti)-1)
28
29class StaticGraph;
30
36{
37#if 0
38public:
40 class EdgeIterator
41 {
42 public:
43 EdgeIterator() { }
44 EdgeIterator(const EdgeIterator &ei) : g(ei.g), v(ei.v), e(ei.e) { }
45 inline EdgeIterator &operator=(const EdgeIterator &ei);
46 inline std::pair<verti, verti> operator*();
47 inline std::pair<verti, verti> operator++();
48 inline std::pair<verti, verti> operator++(int);
49
50 edgei operator-(const EdgeIterator &ei) { return e - ei.e; }
51
52 protected:
53 EdgeIterator(const StaticGraph *g, verti v, edgei e) : g(g), v(v), e(e) { }
54
55 private:
56 const StaticGraph *g;
57 verti v;
58 edgei e;
59
60 friend class StaticGraph;
61 };
62#endif
63
64public:
66 typedef const verti *const_iterator;
67
68#if 0
70 typedef EdgeIterator const_edge_iterator;
71#endif
72
74 typedef std::vector<std::pair<verti, verti> > edge_list;
75
84 {
85 EDGE_NONE = 0, /* for internal use only! */
89 };
90
91 StaticGraph();
92 ~StaticGraph();
95 void clear();
96
104 void make_random(verti V, unsigned outdeg, EdgeDirection edge_dir,
105 bool scc);
106
125 void make_random_clustered(verti cluster_size, verti V,
126 unsigned outdeg, EdgeDirection edge_dir);
127
130 void shuffle_vertices();
131
137 void shuffle_vertices(const std::vector<verti> &perm);
138
140 void assign(const StaticGraph &graph);
141
144
146 edge_list get_edges() const;
147
149 template<class ForwardIterator>
150 void make_subgraph( const StaticGraph &graph,
151 ForwardIterator vertices_begin,
152 ForwardIterator vertices_end,
153 bool proper,
155
157 const verti *verts,
158 const verti nvert,
159 bool proper,
161
164 void remove_edges(edge_list &edges);
165
167 void write_raw(std::ostream &os) const;
168
171
173 void swap(StaticGraph &g);
174
176 bool empty() const { return V_ == 0; }
177
179 verti V() const { return V_; }
180
182 edgei E() const { return E_; }
183
185 EdgeDirection edge_dir() const { return edge_dir_; }
186
189 return &successors_[successor_index_[v]];
190 }
191
194 return &successors_[successor_index_[v + 1]];
195 }
196
200 }
201
204 return &predecessors_[predecessor_index_[v + 1]];
205 }
206
208 bool has_succ(verti v, verti w) const {
209 return std::binary_search(succ_begin(v), succ_end(v), w);
210 }
211
213 bool has_pred(verti w, verti v) const {
214 return std::binary_search(pred_begin(w), pred_end(w), v);
215 }
216
218 edgei degree(verti v) const {
219 return indegree(v) + outdegree(v);
220 }
221
224 return succ_end(v) - succ_begin(v);
225 }
226
229 return pred_end(v) - pred_begin(v);
230 }
231
232#if 0
235 const_edge_iterator edges_begin(verti v = 0) const {
236 return EdgeIterator(this, v, successor_index_[v]);
237 }
238
241 const_edge_iterator edges_end() const {
242 return EdgeIterator(this, V_, E_);
243 }
244#endif
245
246protected:
250 void make_random_scc(edge_list &edges);
251
255
258 template<class ForwardIterator, class VertexMapT>
259 void make_subgraph( const StaticGraph &graph,
260 ForwardIterator vertices_begin,
261 ForwardIterator vertices_end,
262 VertexMapT &vertex_map,
263 bool proper,
265
266private:
267 explicit StaticGraph(const StaticGraph &graph);
269
270private:
279
284
287
288private:
289 /* This is a bit of a hack to allow the small progress measures code to
290 do a preprocessing pass for nodes with self-loops. */
292
293 friend class EdgeIterator;
294};
295
296
297inline void swap(StaticGraph &a, StaticGraph &b)
298{
299 a.swap(b);
300}
301
302#include "Graph_impl.h"
303
304#endif /* ndef MCRL2_PG_GRAPH_H */
std::size_t edgei
type used to number edges
Definition Graph.h:25
void swap(StaticGraph &a, StaticGraph &b)
Definition Graph.h:297
std::size_t verti
type used to number vertices
Definition Graph.h:24
std::vector< std::pair< verti, verti > > edge_list
Definition Graph.h:74
void make_random(verti V, unsigned outdeg, EdgeDirection edge_dir, bool scc)
Definition Graph.cpp:138
StaticGraph(const StaticGraph &graph)
verti * successors_
Definition Graph.h:278
edgei degree(verti v) const
Definition Graph.h:218
friend class EdgeIterator
Definition Graph.h:293
const_iterator succ_end(verti v) const
Definition Graph.h:193
~StaticGraph()
Definition Graph.cpp:22
void reset(verti V, edgei E, EdgeDirection edge_dir)
Definition Graph.cpp:35
edgei indegree(verti v) const
Definition Graph.h:228
EdgeDirection edge_dir() const
Definition Graph.h:185
StaticGraph & operator=(const StaticGraph &graph)
void make_subgraph(const StaticGraph &graph, ForwardIterator vertices_begin, ForwardIterator vertices_end, bool proper, EdgeDirection edge_dir=EDGE_NONE)
Definition Graph_impl.h:52
edgei * predecessor_index_
Definition Graph.h:283
verti V_
Definition Graph.h:271
void make_random_clustered(verti cluster_size, verti V, unsigned outdeg, EdgeDirection edge_dir)
Definition Graph.cpp:191
Definition Graph.cpp:474
void swap(StaticGraph &g)
Definition Graph.cpp:498
const_iterator succ_begin(verti v) const
Definition Graph.h:188
void make_subgraph_threads(const StaticGraph &graph, const verti *verts, const verti nvert, bool proper, EdgeDirection edge_dir=EDGE_NONE)
void make_random_scc(edge_list &edges)
Definition Graph.cpp:83
bool has_succ(verti v, verti w) const
Definition Graph.h:208
edgei * successor_index_
Definition Graph.h:283
void write_raw(std::ostream &os) const
Definition Graph.cpp:457
verti V() const
Definition Graph.h:179
edge_list get_edges() const
Definition Graph.cpp:438
void assign(const StaticGraph &graph)
Definition Graph.cpp:288
verti * predecessors_
Definition Graph.h:278
void remove_edges(edge_list &edges)
Definition Graph.cpp:365
const_iterator pred_begin(verti v) const
Definition Graph.h:198
void shuffle_vertices()
Definition Graph.cpp:269
EdgeDirection
Definition Graph.h:84
@ EDGE_SUCCESSOR
Definition Graph.h:86
@ EDGE_BIDIRECTIONAL
Definition Graph.h:88
@ EDGE_NONE
Definition Graph.h:85
@ EDGE_PREDECESSOR
Definition Graph.h:87
void clear()
Definition Graph.cpp:30
bool has_pred(verti w, verti v) const
Definition Graph.h:213
const_iterator pred_end(verti v) const
Definition Graph.h:203
edgei outdegree(verti v) const
Definition Graph.h:223
bool empty() const
Definition Graph.h:176
EdgeDirection edge_dir_
Definition Graph.h:286
const verti * const_iterator
Definition Graph.h:66
edgei E_
Definition Graph.h:272
StaticGraph()
Definition Graph.cpp:15
edgei E() const
Definition Graph.h:182