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

2 *

3 * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.

4 *

5 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

6 */

9 /// \file

10 /// \brief Defines the GraphAL class, which represents an undirected graph as an adjacency list

13 #ifndef __defined_libdai_graph_h

14 #define __defined_libdai_graph_h

17 #include <ostream>

18 #include <vector>

19 #include <algorithm>

20 #include <dai/util.h>

21 #include <dai/exceptions.h>

22 #include <dai/smallset.h>

28 /// Describes the neighbor relationship of two nodes in a graph.

29 /** Most graphs that libDAI deals with are sparse. Therefore,

30 * a fast and memory-efficient way of representing the structure

31 * of a sparse graph is needed. A frequently used operation that

32 * also needs to be fast is switching between viewing node \a a as a

33 * neighbor of node \a b, and node \a b as a neighbor of node \a a.

34 * The Neighbor struct solves both of these problems.

35 *

36 * Most sparse graphs in libDAI are represented by storing for each

37 * node in the graph the set of its neighbors. In practice, this set

38 * of neighbors is stored using the Neighbors type, which is simply a

39 * std::vector<\link Neighbor \endlink>. The Neighbor struct contains

40 * the label of the neighboring node (the \c node member) and

41 * additional information which allows to access a node as a neighbor

42 * of its neighbor (the \c dual member). For convenience, each Neighbor

43 * structure also stores its index in the Neighbors vector that it is

44 * part of (the \c iter member).

45 *

46 * By convention, variable identifiers naming indices into a vector

47 * of neighbors are prefixed with an underscore ("_"). The neighbor list

48 * which they point into is then understood from the context.

49 *

50 * Let us denote the \a _j 'th neighbor of node \a i by <tt>nb(i,_j)</tt>,

51 * which is of the Neighbor type. Here, \a i is the "absolute" index of

52 * node \a i, but \a _j is understood as a "relative" index, giving node

53 * \a j 's entry in the Neighbors <tt>nb(i)</tt> of node \a i. The absolute

54 * index of \a _j, which would be denoted \a j, can be recovered from the

55 * \c node member, <tt>nb(i,_j).node</tt>. The \c iter member

56 * <tt>nb(i,_j).iter</tt> gives the relative index \a _j, and the \c dual

57 * member <tt>nb(i,_j).dual</tt> gives the "dual" relative index, i.e.,

58 * the index of \a i in \a j 's neighbor list.

59 *

60 * Iteration over edges can be easily accomplished:

61 * \code

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

63 * size_t _j = 0;

64 * bforeach( const Neighbor &j, nb(i) ) {

65 * assert( j == nb(i,j.iter) );

66 * assert( nb(j.node,j.dual).node == i );

67 * assert( _j = j.iter );

68 * _j++;

69 * }

70 * }

71 * \endcode

72 */

74 /// Corresponds to the index of this Neighbor entry in the vector of neighbors

76 /// Contains the absolute index of the neighboring node

78 /// Contains the "dual" index (i.e., the index of this node in the Neighbors vector of the neighboring node)

81 /// Default constructor

83 /// Constructor that allows setting the values of the member variables

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

88 };

91 /// Describes the set of neighbors of some node in a graph

95 /// Represents an edge in a graph: an Edge(\a i,\a j) corresponds to the edge between node \a i and node \a j.

96 /** \note If the edge is interpreted as a directed edge, then it points from \a i to \a j.

97 * \note If the edge is part of a bipartite graph, \a i is understood to correspond to a node of type 1, and

98 * \a j to a node of type 2.

99 */

103 /// Represents the neighborhood structure of nodes in an undirected graph.

104 /** A graph has nodes connected by edges. Nodes are indexed by an unsigned integer.

105 * If there are nrNodes() nodes, they are numbered 0,1,2,...,nrNodes()-1. An edge

106 * between node \a n1 and node \a n2 is represented by a Edge(\a n1,\a n2).

107 *

108 * GraphAL is implemented as a sparse adjacency list, i.e., it stores for each node a list of

109 * its neighboring nodes. The list of neighboring nodes is implemented as a vector of Neighbor

110 * structures (accessible by the nb() method). Thus, each node has an associated variable of

111 * type GraphAL::Neighbors, which is a vector of Neighbor structures, describing its

112 * neighboring nodes.

113 */

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

120 /// \name Constructors and destructors

121 //@{

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

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

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

129 /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.

130 * \param nr The number of nodes.

131 * \param begin Points to the first edge.

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

133 * \param check Whether to only add an edge if it does not exist already.

134 */

138 }

139 //@}

141 /// \name Accessors and mutators

142 //@{

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

148 }

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

154 }

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

160 }

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

165 }

166 //@}

168 /// \name Adding nodes and edges

169 //@{

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

171 /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.

172 * \param nr The number of nodes.

173 * \param begin Points to the first edge.

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

175 * \param check Whether to only add an edge if it does not exist already.

176 */

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

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

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

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

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

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

188 * \returns Index of the added node.

189 */

192 Neighbors nbsnew;

201 }

204 }

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

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

208 */

210 //@}

212 /// \name Erasing nodes and edges

213 //@{

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

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

219 //@}

221 /// \name Queries

222 //@{

223 /// Returns number of nodes

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

232 }

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

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

236 */

246 }

248 }

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

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

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

253 */

260 }

262 /// Returns neighbors of node \a n as a SmallSet<size_t>.

265 /// Returns true if the graph is connected

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

271 /// Asserts internal consistency

274 /// Comparison operator which returns true if two graphs are identical

275 /** \note Two graphs are called identical if they have the same number

276 * of nodes and the same edges (i.e., \a x has an edge between nodes

277 * \a n1 and \a n2 if and only if \c *this has an edge between nodes \a n1 and \a n2).

278 */

291 }

293 }

294 //@}

296 /// \name Input and output

297 //@{

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

301 /// Writes this GraphAL to an output stream

305 }

306 //@}

307 };

311 void GraphAL::construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check ) {

317 }

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

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

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

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

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

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

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

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

333 * from an almost uniform probability distribution over these graphs

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

335 * to infinity).

336 */

343 #endif