ab6857ac15bedd7a4f02bad6b598b65c49d59f5e
[libdai.git] / include / dai / graph.h
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
3 * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
4 *
5 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
6 */
7
8
9 /// \file
10 /// \brief Defines the GraphAL class, which represents an undirected graph as an adjacency list
11
12
13 #ifndef __defined_libdai_graph_h
14 #define __defined_libdai_graph_h
15
16
17 #include <ostream>
18 #include <vector>
19 #include <algorithm>
20 #include <dai/util.h>
21 #include <dai/exceptions.h>
22 #include <dai/smallset.h>
23
24
25 namespace dai {
26
27
28 /// Describes the neighbor relationship of two nodes in a graph.
29 /** Most graphs that libDAI deals with are sparse. Therefore,
30 * a fast and memory-efficient way of representing the structure
31 * of a sparse graph is needed. A frequently used operation that
32 * also needs to be fast is switching between viewing node \a a as a
33 * neighbor of node \a b, and node \a b as a neighbor of node \a a.
34 * The Neighbor struct solves both of these problems.
35 *
36 * Most sparse graphs in libDAI are represented by storing for each
37 * node in the graph the set of its neighbors. In practice, this set
38 * of neighbors is stored using the Neighbors type, which is simply a
39 * std::vector<\link Neighbor \endlink>. The Neighbor struct contains
40 * the label of the neighboring node (the \c node member) and
41 * additional information which allows to access a node as a neighbor
42 * of its neighbor (the \c dual member). For convenience, each Neighbor
43 * structure also stores its index in the Neighbors vector that it is
44 * part of (the \c iter member).
45 *
46 * By convention, variable identifiers naming indices into a vector
47 * of neighbors are prefixed with an underscore ("_"). The neighbor list
48 * which they point into is then understood from the context.
49 *
50 * Let us denote the \a _j 'th neighbor of node \a i by <tt>nb(i,_j)</tt>,
51 * which is of the Neighbor type. Here, \a i is the "absolute" index of
52 * node \a i, but \a _j is understood as a "relative" index, giving node
53 * \a j 's entry in the Neighbors <tt>nb(i)</tt> of node \a i. The absolute
54 * index of \a _j, which would be denoted \a j, can be recovered from the
55 * \c node member, <tt>nb(i,_j).node</tt>. The \c iter member
56 * <tt>nb(i,_j).iter</tt> gives the relative index \a _j, and the \c dual
57 * member <tt>nb(i,_j).dual</tt> gives the "dual" relative index, i.e.,
58 * the index of \a i in \a j 's neighbor list.
59 *
60 * Iteration over edges can be easily accomplished:
61 * \code
62 * for( size_t i = 0; i < nrNodes(); ++i ) {
63 * size_t _j = 0;
64 * bforeach( const Neighbor &j, nb(i) ) {
65 * assert( j == nb(i,j.iter) );
66 * assert( nb(j.node,j.dual).node == i );
67 * assert( _j = j.iter );
68 * _j++;
69 * }
70 * }
71 * \endcode
72 */
73 struct Neighbor {
74 /// Corresponds to the index of this Neighbor entry in the vector of neighbors
75 size_t iter;
76 /// Contains the absolute index of the neighboring node
77 size_t node;
78 /// Contains the "dual" index (i.e., the index of this node in the Neighbors vector of the neighboring node)
79 size_t dual;
80
81 /// Default constructor
82 Neighbor() {}
83 /// Constructor that allows setting the values of the member variables
84 Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
85
86 /// Cast to \c size_t returns \c node member
87 operator size_t () const { return node; }
88 };
89
90
91 /// Describes the set of neighbors of some node in a graph
92 typedef std::vector<Neighbor> Neighbors;
93
94
95 /// Represents an edge in a graph: an Edge(\a i,\a j) corresponds to the edge between node \a i and node \a j.
96 /** \note If the edge is interpreted as a directed edge, then it points from \a i to \a j.
97 * \note If the edge is part of a bipartite graph, \a i is understood to correspond to a node of type 1, and
98 * \a j to a node of type 2.
99 */
100 typedef std::pair<size_t,size_t> Edge;
101
102
103 /// Represents the neighborhood structure of nodes in an undirected graph.
104 /** A graph has nodes connected by edges. Nodes are indexed by an unsigned integer.
105 * If there are nrNodes() nodes, they are numbered 0,1,2,...,nrNodes()-1. An edge
106 * between node \a n1 and node \a n2 is represented by a Edge(\a n1,\a n2).
107 *
108 * GraphAL is implemented as a sparse adjacency list, i.e., it stores for each node a list of
109 * its neighboring nodes. The list of neighboring nodes is implemented as a vector of Neighbor
110 * structures (accessible by the nb() method). Thus, each node has an associated variable of
111 * type GraphAL::Neighbors, which is a vector of Neighbor structures, describing its
112 * neighboring nodes.
113 */
114 class GraphAL {
115 private:
116 /// Contains for each node a vector of its neighbors
117 std::vector<Neighbors> _nb;
118
119 public:
120 /// \name Constructors and destructors
121 //@{
122 /// Default constructor (creates an empty graph).
123 GraphAL() : _nb() {}
124
125 /// Constructs GraphAL with \a nr nodes and no edges.
126 GraphAL( size_t nr ) : _nb( nr ) {}
127
128 /// Constructs GraphAL from a range of edges.
129 /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
130 * \param nr The number of nodes.
131 * \param begin Points to the first edge.
132 * \param end Points just beyond the last edge.
133 * \param check Whether to only add an edge if it does not exist already.
134 */
135 template<typename EdgeInputIterator>
136 GraphAL( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ) : _nb() {
137 construct( nr, begin, end, check );
138 }
139 //@}
140
141 /// \name Accessors and mutators
142 //@{
143 /// Returns constant reference to the \a _n2 'th neighbor of node \a n1
144 const Neighbor & nb( size_t n1, size_t _n2 ) const {
145 DAI_DEBASSERT( n1 < _nb.size() );
146 DAI_DEBASSERT( _n2 < _nb[n1].size() );
147 return _nb[n1][_n2];
148 }
149 /// Returns reference to the \a _n2 'th neighbor of node \a n1
150 Neighbor & nb( size_t n1, size_t _n2 ) {
151 DAI_DEBASSERT( n1 < _nb.size() );
152 DAI_DEBASSERT( _n2 < _nb[n1].size() );
153 return _nb[n1][_n2];
154 }
155
156 /// Returns constant reference to all neighbors of node \a n
157 const Neighbors & nb( size_t n ) const {
158 DAI_DEBASSERT( n < _nb.size() );
159 return _nb[n];
160 }
161 /// Returns reference to all neighbors of node \a n
162 Neighbors & nb( size_t n ) {
163 DAI_DEBASSERT( n < _nb.size() );
164 return _nb[n];
165 }
166 //@}
167
168 /// \name Adding nodes and edges
169 //@{
170 /// (Re)constructs GraphAL from a range of edges.
171 /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
172 * \param nr The number of nodes.
173 * \param begin Points to the first edge.
174 * \param end Points just beyond the last edge.
175 * \param check Whether to only add an edge if it does not exist already.
176 */
177 template<typename EdgeInputIterator>
178 void construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true );
179
180 /// Adds a node without neighbors and returns the index of the added node.
181 size_t addNode() { _nb.push_back( Neighbors() ); return _nb.size() - 1; }
182
183 /// Adds a node, with neighbors specified by a range of nodes.
184 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
185 * \param begin Points to the first index of the nodes that should become neighbors of the added node.
186 * \param end Points just beyond the last index of the nodes that should become neighbors of the added node.
187 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
188 * \returns Index of the added node.
189 */
190 template <typename NodeInputIterator>
191 size_t addNode( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
192 Neighbors nbsnew;
193 nbsnew.reserve( sizeHint );
194 size_t iter = 0;
195 for( NodeInputIterator it = begin; it != end; ++it ) {
196 DAI_ASSERT( *it < nrNodes() );
197 Neighbor nb1new( iter, *it, nb(*it).size() );
198 Neighbor nb2new( nb(*it).size(), nrNodes(), iter++ );
199 nbsnew.push_back( nb1new );
200 nb( *it ).push_back( nb2new );
201 }
202 _nb.push_back( nbsnew );
203 return _nb.size() - 1;
204 }
205
206 /// Adds an edge between node \a n1 and node \a n2.
207 /** If \a check == \c true, only adds the edge if it does not exist already.
208 */
209 GraphAL& addEdge( size_t n1, size_t n2, bool check = true );
210 //@}
211
212 /// \name Erasing nodes and edges
213 //@{
214 /// Removes node \a n and all incident edges; indices of other nodes are changed accordingly.
215 void eraseNode( size_t n );
216
217 /// Removes edge between node \a n1 and node \a n2.
218 void eraseEdge( size_t n1, size_t n2 );
219 //@}
220
221 /// \name Queries
222 //@{
223 /// Returns number of nodes
224 size_t nrNodes() const { return _nb.size(); }
225
226 /// Calculates the number of edges, time complexity: O(nrNodes())
227 size_t nrEdges() const {
228 size_t sum = 0;
229 for( size_t i = 0; i < nrNodes(); i++ )
230 sum += nb(i).size();
231 return sum / 2;
232 }
233
234 /// Returns true if the graph contains an edge between nodes \a n1 and \a n2
235 /** \note The time complexity is linear in the number of neighbors of \a n1 or \a n2
236 */
237 bool hasEdge( size_t n1, size_t n2 ) const {
238 if( nb(n1).size() < nb(n2).size() ) {
239 for( size_t _n2 = 0; _n2 < nb(n1).size(); _n2++ )
240 if( nb( n1, _n2 ) == n2 )
241 return true;
242 } else {
243 for( size_t _n1 = 0; _n1 < nb(n2).size(); _n1++ )
244 if( nb( n2, _n1 ) == n1 )
245 return true;
246 }
247 return false;
248 }
249
250 /// Returns the index of a given node \a n2 amongst the neighbors of \a n1
251 /** \note The time complexity is linear in the number of neighbors of \a n1
252 * \throw OBJECT_NOT_FOUND if \a n2 is not a neighbor of \a n1
253 */
254 size_t findNb( size_t n1, size_t n2 ) {
255 for( size_t _n2 = 0; _n2 < nb(n1).size(); _n2++ )
256 if( nb( n1, _n2 ) == n2 )
257 return _n2;
258 DAI_THROW(OBJECT_NOT_FOUND);
259 return nb(n1).size();
260 }
261
262 /// Returns neighbors of node \a n as a SmallSet<size_t>.
263 SmallSet<size_t> nbSet( size_t n ) const;
264
265 /// Returns true if the graph is connected
266 bool isConnected() const;
267
268 /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
269 bool isTree() const;
270
271 /// Asserts internal consistency
272 void checkConsistency() const;
273
274 /// Comparison operator which returns true if two graphs are identical
275 /** \note Two graphs are called identical if they have the same number
276 * of nodes and the same edges (i.e., \a x has an edge between nodes
277 * \a n1 and \a n2 if and only if \c *this has an edge between nodes \a n1 and \a n2).
278 */
279 bool operator==( const GraphAL& x ) const {
280 if( nrNodes() != x.nrNodes() )
281 return false;
282 for( size_t n1 = 0; n1 < nrNodes(); n1++ ) {
283 if( nb(n1).size() != x.nb(n1).size() )
284 return false;
285 bforeach( const Neighbor &n2, nb(n1) )
286 if( !x.hasEdge( n1, n2 ) )
287 return false;
288 bforeach( const Neighbor &n2, x.nb(n1) )
289 if( !hasEdge( n1, n2 ) )
290 return false;
291 }
292 return true;
293 }
294 //@}
295
296 /// \name Input and output
297 //@{
298 /// Writes this GraphAL to an output stream in GraphViz .dot syntax
299 void printDot( std::ostream& os ) const;
300
301 /// Writes this GraphAL to an output stream
302 friend std::ostream& operator<<( std::ostream& os, const GraphAL& g ) {
303 g.printDot( os );
304 return os;
305 }
306 //@}
307 };
308
309
310 template<typename EdgeInputIterator>
311 void GraphAL::construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check ) {
312 _nb.clear();
313 _nb.resize( nr );
314
315 for( EdgeInputIterator e = begin; e != end; e++ )
316 addEdge( e->first, e->second, check );
317 }
318
319
320 /// Creates a fully-connected graph with \a N nodes
321 GraphAL createGraphFull( size_t N );
322 /// Creates a two-dimensional rectangular grid of \a N1 by \a N2 nodes, which can be \a periodic
323 GraphAL createGraphGrid( size_t N1, size_t N2, bool periodic );
324 /// Creates a three-dimensional rectangular grid of \a N1 by \a N2 by \a N3 nodes, which can be \a periodic
325 GraphAL createGraphGrid3D( size_t N1, size_t N2, size_t N3, bool periodic );
326 /// Creates a graph consisting of a single loop of \a N nodes
327 GraphAL createGraphLoop( size_t N );
328 /// Creates a random tree-structured graph of \a N nodes
329 GraphAL createGraphTree( size_t N );
330 /// Creates a random regular graph of \a N nodes with uniform connectivity \a d
331 /** Algorithm 1 in [\ref StW99].
332 * Draws a random graph of size \a N and uniform degree \a d
333 * from an almost uniform probability distribution over these graphs
334 * (which becomes uniform in the limit that \a d is small and \a N goes
335 * to infinity).
336 */
337 GraphAL createGraphRegular( size_t N, size_t d );
338
339
340 } // end of namespace dai
341
342
343 #endif