Line data Source code
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 : //
6 : // Distributed under the Boost Software License, Version 1.0.
7 : // (See accompanying file LICENSE_1_0.txt or copy at
8 : // http://www.boost.org/LICENSE_1_0.txt)
9 :
10 : /*! \file Graph.h
11 :
12 : Data structures to define vertices, edges and graphs.
13 : */
14 :
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!
24 : typedef std::size_t verti; //!< type used to number vertices
25 : typedef std::size_t edgei; //!< type used to number edges
26 :
27 : #define NO_VERTEX ((verti)-1)
28 :
29 : class StaticGraph;
30 :
31 : /*! \ingroup ParityGameData
32 :
33 : A static graph consists of V vertices (numbered from 0 to V, exclusive)
34 : and E edges, and can store either edge successors, predecessors, or both. */
35 : class StaticGraph
36 : {
37 : #if 0
38 : public:
39 : //! A not-completely-standard-compliant class to iterate over a graph's edges.
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; //! underlying graph whose edges are being iterated
57 : verti v; //! current vertex index
58 : edgei e; //! current edge index
59 :
60 : friend class StaticGraph;
61 : };
62 : #endif
63 :
64 : public:
65 : /*! Iterator used to iterate over predecessor/successor vertices. */
66 : typedef const verti *const_iterator;
67 :
68 : #if 0
69 : /*! Iterator used to iterate over edges. */
70 : typedef EdgeIterator const_edge_iterator;
71 : #endif
72 :
73 : /*! A list of edges */
74 : typedef std::vector<std::pair<verti, verti> > edge_list;
75 :
76 : /*! Specifies which parts of the edges are stored.
77 : When storing successors only, the functions succ_begin() and succ_end()
78 : can be used to iterate over the successors of a given vertex.
79 : Conversely, when storing predecessors, pred_begin() and pred_end()
80 : can be used to iterate over predecessors.
81 : When storing bidirectional edges, both pairs of functions can be used,
82 : but this requires more memory. */
83 : enum EdgeDirection
84 : {
85 : EDGE_NONE = 0, /* for internal use only! */
86 : EDGE_SUCCESSOR = 1,
87 : EDGE_PREDECESSOR = 2,
88 : EDGE_BIDIRECTIONAL = 3
89 : };
90 :
91 : StaticGraph(); /*!< Construct an empty static graph. */
92 : ~StaticGraph(); /*!< Destroy the static graph. */
93 :
94 : /*! Reset to an empty graph. */
95 : void clear();
96 :
97 : /*! Generate a random graph (replacing the old contents).
98 : The resulting game does not contain loops.
99 :
100 : \param V number of vertices to generate
101 : \param outdeg desired average outdegree (at least 1)
102 : \param edge_dir which parts of edges to store
103 : \param scc create a single strongly-connected component */
104 : void make_random(verti V, unsigned outdeg, EdgeDirection edge_dir,
105 : bool scc);
106 :
107 : /*! Generate a random clustered game, which is based on random games of
108 : size `cluster_size` each, which are connected recursively by being
109 : substituting for the vertices of another game of size `cluster_size`,
110 : repeatedly, until a single game remains.
111 :
112 : The resulting game is always a single connected component without loops.
113 :
114 : Passing `V` <= `cluster_size` is equivalent to calling make_random()
115 : with `scc` = true. Choosing `V` = `cluster_size`<sup>d</sup>
116 : creates a game with recursion depth <em>d</em>.
117 :
118 : @param cluster_size number of vertices per cluster
119 : @param V total number of vertices to generate
120 : @param outdeg average outdegree (at least 1)
121 : @param edge_dir which parts of the edges to store
122 :
123 : \see make_random
124 : */
125 : void make_random_clustered(verti cluster_size, verti V,
126 : unsigned outdeg, EdgeDirection edge_dir);
127 :
128 : /*! Randomly shuffles vertex indices. This is useful to obfuscate some of
129 : the structure remaining after make_random_clustered(). */
130 : void shuffle_vertices();
131 :
132 : /*! Shuffle vertex indices by the given permutation.
133 : Vertex v becomes perm[v], for all v.
134 :
135 : \see ParityGame::shuffle
136 : */
137 : void shuffle_vertices(const std::vector<verti> &perm);
138 :
139 : /*! Reset the graph to a copy of `graph`. */
140 : void assign(const StaticGraph &graph);
141 :
142 : /*! Reset the graph based on the given edge structure. */
143 : void assign(edge_list edges, EdgeDirection edge_dir);
144 :
145 : /*! Convert the graph into a list of edges. */
146 : edge_list get_edges() const;
147 :
148 : /*! Reset the graph to the subgraph induced by the given vertex set. */
149 : template<class ForwardIterator>
150 : void make_subgraph( const StaticGraph &graph,
151 : ForwardIterator vertices_begin,
152 : ForwardIterator vertices_end,
153 : bool proper,
154 : EdgeDirection edge_dir = EDGE_NONE );
155 :
156 : void make_subgraph_threads( const StaticGraph &graph,
157 : const verti *verts,
158 : const verti nvert,
159 : bool proper,
160 : EdgeDirection edge_dir = EDGE_NONE );
161 :
162 : /*! Removes the given edges from the graph. The contents of the edge list
163 : may be reordered by this function! */
164 : void remove_edges(edge_list &edges);
165 :
166 : /*! Write raw graph data to output stream */
167 : void write_raw(std::ostream &os) const;
168 :
169 : /*! Read raw graph data from input stream */
170 : void read_raw(std::istream &is);
171 :
172 : /*! Swaps the contents of this graph with another one. */
173 : void swap(StaticGraph &g);
174 :
175 : /*! Returns whether the graph is empty. */
176 0 : bool empty() const { return V_ == 0; }
177 :
178 : /*! Returns the number of vertices in the graph. */
179 0 : verti V() const { return V_; }
180 :
181 : /*! Returns the number of edges in the graph. */
182 : edgei E() const { return E_; }
183 :
184 : /*! Return direction of edges stored. */
185 0 : EdgeDirection edge_dir() const { return edge_dir_; }
186 :
187 : /*! Returns an iterator pointing to the first successor of vertex `v`. */
188 0 : const_iterator succ_begin(verti v) const {
189 0 : return &successors_[successor_index_[v]];
190 : }
191 :
192 : /*! Returns an iterator pointing past the last successor of vertex `v`. */
193 0 : const_iterator succ_end(verti v) const {
194 0 : return &successors_[successor_index_[v + 1]];
195 : }
196 :
197 : /*! Returns an iterator pointing to the first predecessor of vertex `v`. */
198 0 : const_iterator pred_begin(verti v) const {
199 0 : return &predecessors_[predecessor_index_[v]];
200 : }
201 :
202 : /*! Returns an iterator pointing past the last predecessor of vertex `v`. */
203 0 : const_iterator pred_end(verti v) const {
204 0 : return &predecessors_[predecessor_index_[v + 1]];
205 : }
206 :
207 : /*! Returns whether `v` has a successor `w`. */
208 0 : bool has_succ(verti v, verti w) const {
209 0 : return std::binary_search(succ_begin(v), succ_end(v), w);
210 : }
211 :
212 : /*! Returns whether `w` has a predecessor `v`. */
213 : bool has_pred(verti w, verti v) const {
214 : return std::binary_search(pred_begin(w), pred_end(w), v);
215 : }
216 :
217 : /*! Returns the degree for vertex `v`. */
218 : edgei degree(verti v) const {
219 : return indegree(v) + outdegree(v);
220 : }
221 :
222 : /*! Returns the outdegree for vertex `v`. */
223 0 : edgei outdegree(verti v) const {
224 0 : return succ_end(v) - succ_begin(v);
225 : }
226 :
227 : /*! Returns the indegree for vertex `v`. */
228 : edgei indegree(verti v) const {
229 : return pred_end(v) - pred_begin(v);
230 : }
231 :
232 : #if 0
233 : /*! Returns an edge iterator starting at the given vertex.
234 : Currently, this requires the graph to store successors. */
235 : const_edge_iterator edges_begin(verti v = 0) const {
236 : return EdgeIterator(this, v, successor_index_[v]);
237 : }
238 :
239 : /*! Returns an edge iterator pointing to the end of the edge list.
240 : Currently, this requires the graph to store successors. */
241 : const_edge_iterator edges_end() const {
242 : return EdgeIterator(this, V_, E_);
243 : }
244 : #endif
245 :
246 : protected:
247 : /*! Turn the current graph (with current edge list passed in `edges`) into
248 : a strongly connected component by randomly adding edges where necessary.
249 : */
250 : void make_random_scc(edge_list &edges);
251 :
252 : /*! Frees allocated memory and then reallocates memory to store a graph
253 : with `V` vertices and `E` edges. */
254 : void reset(verti V, edgei E, EdgeDirection edge_dir);
255 :
256 : /*! Reset the graph to the subgraph induced by the given vertex set, using
257 : the given map data structure to create the vertex mapping. */
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,
264 : EdgeDirection edge_dir = EDGE_NONE );
265 :
266 : private:
267 : explicit StaticGraph(const StaticGraph &graph);
268 : StaticGraph &operator=(const StaticGraph &graph);
269 :
270 : private:
271 : verti V_; /*!< number of vertices */
272 : edgei E_; /*!< number of edges */
273 :
274 : /*! Successor/predecessor lists (of size E).
275 : If edges are pairs of nodes (i,j), then `successors` is the list of
276 : successors (j's) obtained after sorting edges by predecessors (i's),
277 : and vice versa for `predecessors`. */
278 : verti *successors_, *predecessors_;
279 :
280 : /*! Indices into the successor/predecessor lists (of size V + 1).
281 : successor_index[i] is the lowest index of an edge in `successors` with
282 : a predecessor >= i; successor_index[V] is E. */
283 : edgei *successor_index_, *predecessor_index_;
284 :
285 : /*! Direction of stored edges. */
286 : EdgeDirection edge_dir_;
287 :
288 : private:
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. */
291 : friend class SmallProgressMeasures;
292 :
293 : friend class EdgeIterator;
294 : };
295 :
296 :
297 0 : inline void swap(StaticGraph &a, StaticGraph &b)
298 : {
299 0 : a.swap(b);
300 0 : }
301 :
302 : #include "Graph_impl.h"
303 :
304 : #endif /* ndef MCRL2_PG_GRAPH_H */
|
