1 /* This file is part of libDAI - http://www.libdai.org/

2 *

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.

6 *

7 * Copyright (C) 2006-2010 Joris Mooij [joris dot mooij at libdai dot org]

8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands

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>

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).

34 *

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

39 * neighboring nodes.

40 */

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).

56 *

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:

61 *

62 * \code

63 * Real MR::T( size_t i, size_t _j );

64 * \endcode

65 *

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.

75 *

76 * \code

77 * Neighbor n = nb(i,_j);

78 * n.node == j &&

79 * n.iter == _j &&

80 * nb(n.node,n.dual).node == i

81 * \endcode

82 *

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:

89 * \code

90 * for( size_t i = 0; i < nrNodes(); ++i )

91 * foreach( const Neighbor &j, nb(i) )

92 * T( i, j.iter );

93 * \endcode

94 */

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

108 /// Cast to \c size_t returns \c node member

110 };

112 /// Describes the neighbors of some node.

115 /// Represents an edge: an Edge(\a n1,\a n2) corresponds to the edge between node \a n1 and node \a n2.

119 /// Contains for each node a vector of its neighbors

123 /// \name Constructors and destructors

124 //@{

125 /// Default constructor (creates an empty graph).

128 /// Constructs GraphAL with \a nr nodes and no edges.

131 /// Constructs GraphAL from a range of edges.

132 /** \tparam EdgeInputIterator Iterator that iterates over instances of GraphAL::Edge.

133 * \param nr The number of nodes.

134 * \param begin Points to the first edge.

135 * \param end Points just beyond the last edge.

136 */

140 }

141 //@}

143 /// \name Accessors and mutators

144 //@{

145 /// Returns constant reference to the \a _n2 'th neighbor of node \a n1

150 }

151 /// Returns reference to the \a _n2 'th neighbor of node \a n1

156 }

158 /// Returns constant reference to all neighbors of node \a n

162 }

163 /// Returns reference to all neighbors of node \a n

167 }

168 //@}

170 /// \name Adding nodes and edges

171 //@{

172 /// (Re)constructs GraphAL from a range of edges.

173 /** \tparam EdgeInputIterator Iterator that iterates over instances of GraphAL::Edge.

174 * \param nr The number of nodes.

175 * \param begin Points to the first edge.

176 * \param end Points just beyond the last edge.

177 */

181 /// Adds a node without neighbors and returns the index of the added node.

184 /// Adds a node, with neighbors specified by a range of nodes.

185 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.

186 * \param begin Points to the first index of the nodes that should become neighbors of the added node.

187 * \param end Points just beyond the last index of the nodes that should become neighbors of the added node.

188 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.

189 * \returns Index of the added node.

190 */

193 Neighbors nbsnew;

202 }

205 }

207 /// Adds an edge between node \a n1 and node \a n2.

208 /** If \a check == \c true, only adds the edge if it does not exist already.

209 */

211 //@}

213 /// \name Erasing nodes and edges

214 //@{

215 /// Removes node \a n and all incident edges; indices of other nodes are changed accordingly.

218 /// Removes edge between node \a n1 and node \a n2.

220 //@}

222 /// \name Queries

223 //@{

224 /// Returns number of nodes

227 /// Calculates the number of edges, time complexity: O(nrNodes())

233 }

235 /// Returns true if the graph contains an edge between nodes \a n1 and \a n2

236 /** \note The time complexity is linear in the number of neighbors of \a n1

237 */

243 }

245 /// Returns the index of a given node \a n2 amongst the neighbors of \a n1

246 /** \note The time complexity is linear in the number of neighbors of \a n1

247 * \throw OBJECT_NOT_FOUND if \a n2 is not a neighbor of \a n1

248 */

255 }

257 /// Returns true if the graph is connected

260 /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.

263 /// Asserts internal consistency

265 //@}

267 /// \name Input and output

268 //@{

269 /// Writes this GraphAL to an output stream in GraphViz .dot syntax

271 //@}

272 };

281 #ifdef DAI_DEBUG

283 #else

285 #endif

286 }

287 }

290 /// Creates a fully-connected graph with \a N nodes

292 /// Creates a two-dimensional rectangular grid of \a N1 by \a N2 nodes, which can be \a periodic

294 /// Creates a three-dimensional rectangular grid of \a N1 by \a N2 by \a N3 nodes, which can be \a periodic

296 /// Creates a graph consisting of a single loop of \a N nodes

298 /// Creates a random tree-structured graph of \a N nodes

300 /// Creates a random regular graph of \a N nodes with uniform connectivity \a d

301 /** Algorithm 1 in [\ref StW99].

302 * Draws a random graph of size \a N and uniform degree \a d

303 * from an almost uniform probability distribution over these graphs

304 * (which becomes uniform in the limit that \a d is small and \a N goes

305 * to infinity).

306 */

313 #endif