1 /* This file is part of libDAI - http://www.libdai.org/
3 * libDAI is licensed under the terms of the GNU General Public License version
4 * 2, or (at your option) any later version. libDAI is distributed without any
5 * warranty. See the file COPYING for more details.
7 * Copyright (C) 2006-2009 Joris Mooij [joris dot mooij at libdai dot org]
8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
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
24 #include <dai/exceptions.h>
30 /// Represents the neighborhood structure of nodes in an undirected graph.
31 /** A graph has nodes connected by edges. Nodes are indexed by an unsigned integer.
32 * If there are nrNodes() nodes, they are numbered 0,1,2,...,nrNodes()-1. An edge
33 * between node \a n1 and node \a n2 is represented by a GraphAL::Edge(\a n1,\a n2).
35 * GraphAL is implemented as a sparse adjacency list, i.e., it stores for each node a list of
36 * its neighboring nodes. The list of neighboring nodes is implemented as a vector of Neighbor
37 * structures (accessible by the nb() method). Thus, each node has an associated variable of
38 * type GraphAL::Neighbors, which is a vector of Neighbor structures, describing its
43 /// Describes the neighbor relationship of two nodes in a GraphAL.
44 /** Sometimes we want to do an action, such as sending a
45 * message, for all edges in a graph. However, most graphs
46 * will be sparse, so we need some way of storing a set of
47 * the neighbors of a node, which is both fast and
48 * memory-efficient. We also need to be able to go between
49 * viewing node \a a as a neighbor of node \a b, and node \a b
50 * as a neighbor of node \a a. The Neighbor struct solves
51 * both of these problems. Each node has a list of neighbors,
52 * stored as a std::vector<\link Neighbor \endlink>, and
53 * extra information is included in the Neighbor struct which
54 * allows us to access a node as a neighbor of its neighbor
55 * (the \c dual member).
57 * By convention, variable identifiers naming indices into a
58 * vector of neighbors are prefixed with an underscore ("_").
59 * The neighbor list which they point into is then understood
60 * from context. For example:
63 * Real MR::T( size_t i, size_t _j );
66 * Here, \a i is the "absolute" index of node i, but \a _j is
67 * understood as a "relative" index, giving node \a j 's entry in
68 * <tt>nb(i)</tt>. The corresponding Neighbor structure can be
69 * accessed as <tt>nb(i,_j)</tt> or <tt>nb(i)[_j]</tt>. The
70 * absolute index of \a _j, which would be called \a j, can be
71 * recovered from the \c node member: <tt>nb(i,_j).node</tt>.
72 * The \c iter member gives the relative index \a _j, and the
73 * \c dual member gives the "dual" relative index, i.e., the
74 * index of \a i in \a j 's neighbor list.
77 * Neighbor n = nb(i,_j);
80 * nb(n.node,n.dual).node == i
83 * There is no easy way to transform a pair of absolute node
84 * indices \a i and \a j into a Neighbor structure relative
85 * to one of the nodes. Such a feature has never yet been
86 * found to be necessary. Iteration over edges can always be
87 * accomplished using the Neighbor lists, and by writing
88 * functions that accept relative indices:
90 * for( size_t i = 0; i < nrNodes(); ++i )
91 * foreach( const Neighbor &j, nb(i) )
96 /// Corresponds to the index of this Neighbor entry in the vector of neighbors
98 /// Contains the number of the neighboring node
100 /// Contains the "dual" iter
103 /// Default constructor
105 /// Constructor that sets the Neighbor members according to the parameters
106 Neighbor( size_t iter
, size_t node
, size_t dual
) : iter(iter
), node(node
), dual(dual
) {}
108 /// Cast to \c size_t returns \c node member
109 operator size_t () const { return node
; }
112 /// Describes the neighbors of some node.
113 typedef std::vector
<Neighbor
> Neighbors
;
115 /// Represents an edge: an Edge(\a n1,\a n2) corresponds to the edge between node \a n1 and node \a n2.
116 typedef std::pair
<size_t,size_t> Edge
;
119 /// Contains for each node a vector of its neighbors
120 std::vector
<Neighbors
> _nb
;
122 /// Used internally by isTree()
123 typedef std::vector
<size_t> levelType
;
126 /// \name Constructors and destructors
128 /// Default constructor (creates an empty graph).
131 /// Constructs GraphAL with \a nr nodes and no edges.
132 GraphAL( size_t nr
) : _nb( nr
) {}
134 /// Constructs GraphAL from a range of edges.
135 /** \tparam EdgeInputIterator Iterator that iterates over instances of GraphAL::Edge.
136 * \param nr The number of nodes.
137 * \param begin Points to the first edge.
138 * \param end Points just beyond the last edge.
140 template<typename EdgeInputIterator
>
141 GraphAL( size_t nr
, EdgeInputIterator begin
, EdgeInputIterator end
) : _nb() {
142 construct( nr
, begin
, end
);
146 /// \name Accessors and mutators
148 /// Returns constant reference to the \a _n2 'th neighbor of node \a n1
149 const Neighbor
& nb( size_t n1
, size_t _n2
) const {
150 DAI_DEBASSERT( n1
< _nb
.size() );
151 DAI_DEBASSERT( _n2
< _nb
[n1
].size() );
154 /// Returns reference to the \a _n2 'th neighbor of node \a n1
155 Neighbor
& nb( size_t n1
, size_t _n2
) {
156 DAI_DEBASSERT( n1
< _nb
.size() );
157 DAI_DEBASSERT( _n2
< _nb
[n1
].size() );
161 /// Returns constant reference to all neighbors of node \a n
162 const Neighbors
& nb( size_t n
) const {
163 DAI_DEBASSERT( n
< _nb
.size() );
166 /// Returns reference to all neighbors of node \a n
167 Neighbors
& nb( size_t n
) {
168 DAI_DEBASSERT( n
< _nb
.size() );
173 /// \name Adding nodes and edges
175 /// (Re)constructs GraphAL from a range of edges.
176 /** \tparam EdgeInputIterator Iterator that iterates over instances of GraphAL::Edge.
177 * \param nr The number of nodes.
178 * \param begin Points to the first edge.
179 * \param end Points just beyond the last edge.
181 template<typename EdgeInputIterator
>
182 void construct( size_t nr
, EdgeInputIterator begin
, EdgeInputIterator end
);
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.
194 template <typename NodeInputIterator
>
195 size_t addNode( NodeInputIterator begin
, NodeInputIterator end
, size_t sizeHint
= 0 ) {
197 nbsnew
.reserve( sizeHint
);
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
);
206 _nb
.push_back( nbsnew
);
207 return _nb
.size() - 1;
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.
213 void addEdge( size_t n1
, size_t n2
, bool check
= true );
216 /// \name Erasing nodes and edges
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
);
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 {
233 for( size_t i
= 0; i
< nrNodes(); i
++ )
238 /// Returns true if the graph is connected
239 bool isConnected() const;
241 /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
244 /// Checks internal consistency
245 void checkConsistency() const;
248 /// \name Input and output
250 /// Writes this GraphAL to an output stream in GraphALViz .dot syntax
251 void printDot( std::ostream
& os
) const;
256 template<typename EdgeInputIterator
>
257 void GraphAL::construct( size_t nr
, EdgeInputIterator begin
, EdgeInputIterator end
) {
261 for( EdgeInputIterator e
= begin
; e
!= end
; e
++ ) {
263 addEdge( e
->first
, e
->second
, true );
265 addEdge( e
->first
, e
->second
, false );
271 /// Creates a fully-connected graph with \a N nodes
272 GraphAL
createGraphFull( size_t N
);
273 /// Creates a two-dimensional rectangular grid of \a n1 by \a n2 nodes, which can be \a periodic
274 GraphAL
createGraphGrid( size_t n1
, size_t n2
, bool periodic
);
275 /// Creates a three-dimensional rectangular grid of \a n1 by \a n2 by \a n3 nodes, which can be \a periodic
276 GraphAL
createGraphGrid3D( size_t n1
, size_t n2
, size_t n3
, bool periodic
);
277 /// Creates a graph consisting of a single loop of \a N nodes
278 GraphAL
createGraphLoop( size_t N
);
279 /// Creates a random tree-structured graph of \a N nodes
280 GraphAL
createGraphTree( size_t N
);
281 /// Creates a random regular graph of \a N nodes with uniform connectivity \a d
282 GraphAL
createGraphRegular( size_t N
, size_t d
);
285 } // end of namespace dai