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