libDAI
|
00001 /* This file is part of libDAI - http://www.libdai.org/ 00002 * 00003 * Copyright (c) 2006-2011, The libDAI authors. All rights reserved. 00004 * 00005 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file. 00006 */ 00007 00008 00011 00012 00013 #ifndef __defined_libdai_graph_h 00014 #define __defined_libdai_graph_h 00015 00016 00017 #include <ostream> 00018 #include <vector> 00019 #include <algorithm> 00020 #include <dai/util.h> 00021 #include <dai/exceptions.h> 00022 #include <dai/smallset.h> 00023 00024 00025 namespace dai { 00026 00027 00029 00073 struct Neighbor { 00075 size_t iter; 00077 size_t node; 00079 size_t dual; 00080 00082 Neighbor() {} 00084 Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {} 00085 00087 operator size_t () const { return node; } 00088 }; 00089 00090 00092 typedef std::vector<Neighbor> Neighbors; 00093 00094 00096 00100 typedef std::pair<size_t,size_t> Edge; 00101 00102 00104 00114 class GraphAL { 00115 private: 00117 std::vector<Neighbors> _nb; 00118 00119 public: 00121 00122 00123 GraphAL() : _nb() {} 00124 00126 GraphAL( size_t nr ) : _nb( nr ) {} 00127 00129 00135 template<typename EdgeInputIterator> 00136 GraphAL( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ) : _nb() { 00137 construct( nr, begin, end, check ); 00138 } 00140 00142 00143 00144 const Neighbor & nb( size_t n1, size_t _n2 ) const { 00145 DAI_DEBASSERT( n1 < _nb.size() ); 00146 DAI_DEBASSERT( _n2 < _nb[n1].size() ); 00147 return _nb[n1][_n2]; 00148 } 00150 Neighbor & nb( size_t n1, size_t _n2 ) { 00151 DAI_DEBASSERT( n1 < _nb.size() ); 00152 DAI_DEBASSERT( _n2 < _nb[n1].size() ); 00153 return _nb[n1][_n2]; 00154 } 00155 00157 const Neighbors & nb( size_t n ) const { 00158 DAI_DEBASSERT( n < _nb.size() ); 00159 return _nb[n]; 00160 } 00162 Neighbors & nb( size_t n ) { 00163 DAI_DEBASSERT( n < _nb.size() ); 00164 return _nb[n]; 00165 } 00167 00169 00170 00171 00177 template<typename EdgeInputIterator> 00178 void construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ); 00179 00181 size_t addNode() { _nb.push_back( Neighbors() ); return _nb.size() - 1; } 00182 00184 00190 template <typename NodeInputIterator> 00191 size_t addNode( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) { 00192 Neighbors nbsnew; 00193 nbsnew.reserve( sizeHint ); 00194 size_t iter = 0; 00195 for( NodeInputIterator it = begin; it != end; ++it ) { 00196 DAI_ASSERT( *it < nrNodes() ); 00197 Neighbor nb1new( iter, *it, nb(*it).size() ); 00198 Neighbor nb2new( nb(*it).size(), nrNodes(), iter++ ); 00199 nbsnew.push_back( nb1new ); 00200 nb( *it ).push_back( nb2new ); 00201 } 00202 _nb.push_back( nbsnew ); 00203 return _nb.size() - 1; 00204 } 00205 00207 00209 GraphAL& addEdge( size_t n1, size_t n2, bool check = true ); 00211 00213 00214 00215 void eraseNode( size_t n ); 00216 00218 void eraseEdge( size_t n1, size_t n2 ); 00220 00222 00223 00224 size_t nrNodes() const { return _nb.size(); } 00225 00227 size_t nrEdges() const { 00228 size_t sum = 0; 00229 for( size_t i = 0; i < nrNodes(); i++ ) 00230 sum += nb(i).size(); 00231 return sum / 2; 00232 } 00233 00235 00237 bool hasEdge( size_t n1, size_t n2 ) const { 00238 if( nb(n1).size() < nb(n2).size() ) { 00239 for( size_t _n2 = 0; _n2 < nb(n1).size(); _n2++ ) 00240 if( nb( n1, _n2 ) == n2 ) 00241 return true; 00242 } else { 00243 for( size_t _n1 = 0; _n1 < nb(n2).size(); _n1++ ) 00244 if( nb( n2, _n1 ) == n1 ) 00245 return true; 00246 } 00247 return false; 00248 } 00249 00251 00254 size_t findNb( size_t n1, size_t n2 ) { 00255 for( size_t _n2 = 0; _n2 < nb(n1).size(); _n2++ ) 00256 if( nb( n1, _n2 ) == n2 ) 00257 return _n2; 00258 DAI_THROW(OBJECT_NOT_FOUND); 00259 return nb(n1).size(); 00260 } 00261 00263 SmallSet<size_t> nbSet( size_t n ) const; 00264 00266 bool isConnected() const; 00267 00269 bool isTree() const; 00270 00272 void checkConsistency() const; 00273 00275 00279 bool operator==( const GraphAL& x ) const { 00280 if( nrNodes() != x.nrNodes() ) 00281 return false; 00282 for( size_t n1 = 0; n1 < nrNodes(); n1++ ) { 00283 if( nb(n1).size() != x.nb(n1).size() ) 00284 return false; 00285 foreach( const Neighbor &n2, nb(n1) ) 00286 if( !x.hasEdge( n1, n2 ) ) 00287 return false; 00288 foreach( const Neighbor &n2, x.nb(n1) ) 00289 if( !hasEdge( n1, n2 ) ) 00290 return false; 00291 } 00292 return true; 00293 } 00295 00297 00298 00299 void printDot( std::ostream& os ) const; 00300 00302 friend std::ostream& operator<<( std::ostream& os, const GraphAL& g ) { 00303 g.printDot( os ); 00304 return os; 00305 } 00307 }; 00308 00309 00310 template<typename EdgeInputIterator> 00311 void GraphAL::construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check ) { 00312 _nb.clear(); 00313 _nb.resize( nr ); 00314 00315 for( EdgeInputIterator e = begin; e != end; e++ ) 00316 addEdge( e->first, e->second, check ); 00317 } 00318 00319 00321 GraphAL createGraphFull( size_t N ); 00323 GraphAL createGraphGrid( size_t N1, size_t N2, bool periodic ); 00325 GraphAL createGraphGrid3D( size_t N1, size_t N2, size_t N3, bool periodic ); 00327 GraphAL createGraphLoop( size_t N ); 00329 GraphAL createGraphTree( size_t N ); 00331 00337 GraphAL createGraphRegular( size_t N, size_t d ); 00338 00339 00340 } // end of namespace dai 00341 00342 00343 #endif