00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00014
00015
00016 #ifndef __defined_libdai_graph_h
00017 #define __defined_libdai_graph_h
00018
00019
00020 #include <ostream>
00021 #include <vector>
00022 #include <algorithm>
00023 #include <dai/util.h>
00024 #include <dai/exceptions.h>
00025
00026
00027 namespace dai {
00028
00029
00031
00041 class GraphAL {
00042 public:
00044
00095 struct Neighbor {
00097 size_t iter;
00099 size_t node;
00101 size_t dual;
00102
00104 Neighbor() {}
00106 Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
00107
00109 operator size_t () const { return node; }
00110 };
00111
00113 typedef std::vector<Neighbor> Neighbors;
00114
00116 typedef std::pair<size_t,size_t> Edge;
00117
00118 private:
00120 std::vector<Neighbors> _nb;
00121
00123 typedef std::vector<size_t> levelType;
00124
00125 public:
00127
00128
00129 GraphAL() : _nb() {}
00130
00132 GraphAL( size_t nr ) : _nb( nr ) {}
00133
00135
00140 template<typename EdgeInputIterator>
00141 GraphAL( size_t nr, EdgeInputIterator begin, EdgeInputIterator end ) : _nb() {
00142 construct( nr, begin, end );
00143 }
00145
00147
00148
00149 const Neighbor & nb( size_t n1, size_t _n2 ) const {
00150 DAI_DEBASSERT( n1 < _nb.size() );
00151 DAI_DEBASSERT( _n2 < _nb[n1].size() );
00152 return _nb[n1][_n2];
00153 }
00155 Neighbor & nb( size_t n1, size_t _n2 ) {
00156 DAI_DEBASSERT( n1 < _nb.size() );
00157 DAI_DEBASSERT( _n2 < _nb[n1].size() );
00158 return _nb[n1][_n2];
00159 }
00160
00162 const Neighbors & nb( size_t n ) const {
00163 DAI_DEBASSERT( n < _nb.size() );
00164 return _nb[n];
00165 }
00167 Neighbors & nb( size_t n ) {
00168 DAI_DEBASSERT( n < _nb.size() );
00169 return _nb[n];
00170 }
00172
00174
00175
00176
00181 template<typename EdgeInputIterator>
00182 void construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end );
00183
00185 size_t addNode() { _nb.push_back( Neighbors() ); return _nb.size() - 1; }
00186
00188
00194 template <typename NodeInputIterator>
00195 size_t addNode( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
00196 Neighbors nbsnew;
00197 nbsnew.reserve( sizeHint );
00198 size_t iter = 0;
00199 for( NodeInputIterator it = begin; it != end; ++it ) {
00200 DAI_ASSERT( *it < nrNodes() );
00201 Neighbor nb1new( iter, *it, nb(*it).size() );
00202 Neighbor nb2new( nb(*it).size(), nrNodes(), iter++ );
00203 nbsnew.push_back( nb1new );
00204 nb( *it ).push_back( nb2new );
00205 }
00206 _nb.push_back( nbsnew );
00207 return _nb.size() - 1;
00208 }
00209
00211
00213 void addEdge( size_t n1, size_t n2, bool check = true );
00215
00217
00218
00219 void eraseNode( size_t n );
00220
00222 void eraseEdge( size_t n1, size_t n2 );
00224
00226
00227
00228 size_t nrNodes() const { return _nb.size(); }
00229
00231 size_t nrEdges() const {
00232 size_t sum = 0;
00233 for( size_t i = 0; i < nrNodes(); i++ )
00234 sum += nb(i).size();
00235 return sum;
00236 }
00237
00239 bool isConnected() const;
00240
00242 bool isTree() const;
00243
00245 void checkConsistency() const;
00247
00249
00250
00251 void printDot( std::ostream& os ) const;
00253 };
00254
00255
00256 template<typename EdgeInputIterator>
00257 void GraphAL::construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end ) {
00258 _nb.clear();
00259 _nb.resize( nr );
00260
00261 for( EdgeInputIterator e = begin; e != end; e++ ) {
00262 #ifdef DAI_DEBUG
00263 addEdge( e->first, e->second, true );
00264 #else
00265 addEdge( e->first, e->second, false );
00266 #endif
00267 }
00268 }
00269
00270
00272 GraphAL createGraphFull( size_t N );
00274 GraphAL createGraphGrid( size_t n1, size_t n2, bool periodic );
00276 GraphAL createGraphGrid3D( size_t n1, size_t n2, size_t n3, bool periodic );
00278 GraphAL createGraphLoop( size_t N );
00280 GraphAL createGraphTree( size_t N );
00282 GraphAL createGraphRegular( size_t N, size_t d );
00283
00284
00285 }
00286
00287
00288 #endif