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-2009 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

122 /// Used internally by isTree()

126 /// \name Constructors and destructors

127 //@{

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

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

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.

139 */

143 }

144 //@}

146 /// \name Accessors and mutators

147 //@{

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

153 }

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

159 }

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

165 }

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

170 }

171 //@}

173 /// \name Adding nodes and edges

174 //@{

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.

180 */

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

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.

193 */

196 Neighbors nbsnew;

205 }

208 }

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.

212 */

214 //@}

216 /// \name Erasing nodes and edges

217 //@{

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

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

223 //@}

225 /// \name Queries

226 //@{

227 /// Returns number of nodes

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

236 }

238 /// Returns true if the graph is connected

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

244 /// Checks internal consistency

246 //@}

248 /// \name Input and output

249 //@{

250 /// Writes this GraphAL to an output stream in GraphALViz .dot syntax

252 //@}

253 };

262 #ifdef DAI_DEBUG

264 #else

266 #endif

267 }

268 }

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

273 /// Creates a two-dimensional rectangular grid of \a n1 by \a n2 nodes, which can be \a periodic

275 /// Creates a three-dimensional rectangular grid of \a n1 by \a n2 by \a n3 nodes, which can be \a periodic

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

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

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

288 #endif