libDAI
graph.h
Go to the documentation of this file.
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 
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 
29 
73 struct Neighbor {
75  size_t iter;
77  size_t node;
79  size_t dual;
80 
82  Neighbor() {}
84  Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
85 
87  operator size_t () const { return node; }
88 };
89 
90 
92 typedef std::vector<Neighbor> Neighbors;
93 
94 
96 
100 typedef std::pair<size_t,size_t> Edge;
101 
102 
104 
114 class GraphAL {
115  private:
117  std::vector<Neighbors> _nb;
118 
119  public:
121 
122 
123  GraphAL() : _nb() {}
124 
126  GraphAL( size_t nr ) : _nb( nr ) {}
127 
129 
135  template<typename EdgeInputIterator>
136  GraphAL( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ) : _nb() {
137  construct( nr, begin, end, check );
138  }
140 
142 
143 
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  }
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 
157  const Neighbors & nb( size_t n ) const {
158  DAI_DEBASSERT( n < _nb.size() );
159  return _nb[n];
160  }
162  Neighbors & nb( size_t n ) {
163  DAI_DEBASSERT( n < _nb.size() );
164  return _nb[n];
165  }
167 
169 
170 
171 
177  template<typename EdgeInputIterator>
178  void construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true );
179 
181  size_t addNode() { _nb.push_back( Neighbors() ); return _nb.size() - 1; }
182 
184 
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 
207 
209  GraphAL& addEdge( size_t n1, size_t n2, bool check = true );
211 
213 
214 
215  void eraseNode( size_t n );
216 
218  void eraseEdge( size_t n1, size_t n2 );
220 
222 
223 
224  size_t nrNodes() const { return _nb.size(); }
225 
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 
235 
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 
251 
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 
263  SmallSet<size_t> nbSet( size_t n ) const;
264 
266  bool isConnected() const;
267 
269  bool isTree() const;
270 
272  void checkConsistency() const;
273 
275 
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  }
295 
297 
298 
299  void printDot( std::ostream& os ) const;
300 
302  friend std::ostream& operator<<( std::ostream& os, const GraphAL& g ) {
303  g.printDot( os );
304  return os;
305  }
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 
321 GraphAL createGraphFull( size_t N );
323 GraphAL createGraphGrid( size_t N1, size_t N2, bool periodic );
325 GraphAL createGraphGrid3D( size_t N1, size_t N2, size_t N3, bool periodic );
327 GraphAL createGraphLoop( size_t N );
329 GraphAL createGraphTree( size_t N );
331 
337 GraphAL createGraphRegular( size_t N, size_t d );
338 
339 
340 } // end of namespace dai
341 
342 
343 #endif