XGitUrl: http://git.tuebingen.mpg.de/?p=libdai.git;a=blobdiff_plain;f=include%2Fdai%2Fgraph.h;h=d8ffb6158c39fa0e484e12e35b0d98c889ed8bb1;hp=3526ef621926a2f9475127a106b05bd953e487b8;hb=1dcccafc7314ac809b84a76dfa7984d3b1c22980;hpb=7f20a1725febb77b5c0fe028f5a47629b5f62c66
diff git a/include/dai/graph.h b/include/dai/graph.h
index 3526ef6..d8ffb61 100644
 a/include/dai/graph.h
+++ b/include/dai/graph.h
@@ 1,11 +1,8 @@
/* This file is part of libDAI  http://www.libdai.org/
*
 * libDAI is licensed under the terms of the GNU General Public License version
 * 2, or (at your option) any later version. libDAI is distributed without any
 * warranty. See the file COPYING for more details.
+ * Copyright (c) 20062011, The libDAI authors. All rights reserved.
*
 * Copyright (C) 20062010 Joris Mooij [joris dot mooij at libdai dot org]
 * Copyright (C) 20062007 Radboud University Nijmegen, The Netherlands
+ * Use of this source code is governed by a BSDstyle license that can be found in the LICENSE file.
*/
@@ 22,15 +19,91 @@
#include
#include
#include
+#include
namespace dai {
+/// Describes the neighbor relationship of two nodes in a graph.
+/** Most graphs that libDAI deals with are sparse. Therefore,
+ * a fast and memoryefficient way of representing the structure
+ * of a sparse graph is needed. A frequently used operation that
+ * also needs to be fast is switching between viewing node \a a as a
+ * neighbor of node \a b, and node \a b as a neighbor of node \a a.
+ * The Neighbor struct solves both of these problems.
+ *
+ * Most sparse graphs in libDAI are represented by storing for each
+ * node in the graph the set of its neighbors. In practice, this set
+ * of neighbors is stored using the Neighbors type, which is simply a
+ * std::vector<\link Neighbor \endlink>. The Neighbor struct contains
+ * the label of the neighboring node (the \c node member) and
+ * additional information which allows to access a node as a neighbor
+ * of its neighbor (the \c dual member). For convenience, each Neighbor
+ * structure also stores its index in the Neighbors vector that it is
+ * part of (the \c iter member).
+ *
+ * By convention, variable identifiers naming indices into a vector
+ * of neighbors are prefixed with an underscore ("_"). The neighbor list
+ * which they point into is then understood from the context.
+ *
+ * Let us denote the \a _j 'th neighbor of node \a i by nb(i,_j),
+ * which is of the Neighbor type. Here, \a i is the "absolute" index of
+ * node \a i, but \a _j is understood as a "relative" index, giving node
+ * \a j 's entry in the Neighbors nb(i) of node \a i. The absolute
+ * index of \a _j, which would be denoted \a j, can be recovered from the
+ * \c node member, nb(i,_j).node. The \c iter member
+ * nb(i,_j).iter gives the relative index \a _j, and the \c dual
+ * member nb(i,_j).dual gives the "dual" relative index, i.e.,
+ * the index of \a i in \a j 's neighbor list.
+ *
+ * Iteration over edges can be easily accomplished:
+ * \code
+ * for( size_t i = 0; i < nrNodes(); ++i ) {
+ * size_t _j = 0;
+ * bforeach( const Neighbor &j, nb(i) ) {
+ * assert( j == nb(i,j.iter) );
+ * assert( nb(j.node,j.dual).node == i );
+ * assert( _j = j.iter );
+ * _j++;
+ * }
+ * }
+ * \endcode
+ */
+struct Neighbor {
+ /// Corresponds to the index of this Neighbor entry in the vector of neighbors
+ size_t iter;
+ /// Contains the absolute index of the neighboring node
+ size_t node;
+ /// Contains the "dual" index (i.e., the index of this node in the Neighbors vector of the neighboring node)
+ size_t dual;
+
+ /// Default constructor
+ Neighbor() {}
+ /// Constructor that allows setting the values of the member variables
+ Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
+
+ /// Cast to \c size_t returns \c node member
+ operator size_t () const { return node; }
+};
+
+
+/// Describes the set of neighbors of some node in a graph
+typedef std::vector Neighbors;
+
+
+/// Represents an edge in a graph: an Edge(\a i,\a j) corresponds to the edge between node \a i and node \a j.
+/** \note If the edge is interpreted as a directed edge, then it points from \a i to \a j.
+ * \note If the edge is part of a bipartite graph, \a i is understood to correspond to a node of type 1, and
+ * \a j to a node of type 2.
+ */
+typedef std::pair Edge;
+
+
/// Represents the neighborhood structure of nodes in an undirected graph.
/** A graph has nodes connected by edges. Nodes are indexed by an unsigned integer.
* If there are nrNodes() nodes, they are numbered 0,1,2,...,nrNodes()1. An edge
 * between node \a n1 and node \a n2 is represented by a GraphAL::Edge(\a n1,\a n2).
+ * between node \a n1 and node \a n2 is represented by a Edge(\a n1,\a n2).
*
* GraphAL is implemented as a sparse adjacency list, i.e., it stores for each node a list of
* its neighboring nodes. The list of neighboring nodes is implemented as a vector of Neighbor
@@ 39,82 +112,6 @@ namespace dai {
* neighboring nodes.
*/
class GraphAL {
 public:
 /// Describes the neighbor relationship of two nodes in a GraphAL.
 /** Sometimes we want to do an action, such as sending a
 * message, for all edges in a graph. However, most graphs
 * will be sparse, so we need some way of storing a set of
 * the neighbors of a node, which is both fast and
 * memoryefficient. We also need to be able to go between
 * viewing node \a a as a neighbor of node \a b, and node \a b
 * as a neighbor of node \a a. The Neighbor struct solves
 * both of these problems. Each node has a list of neighbors,
 * stored as a std::vector<\link Neighbor \endlink>, and
 * extra information is included in the Neighbor struct which
 * allows us to access a node as a neighbor of its neighbor
 * (the \c dual member).
 *
 * By convention, variable identifiers naming indices into a
 * vector of neighbors are prefixed with an underscore ("_").
 * The neighbor list which they point into is then understood
 * from context. For example:
 *
 * \code
 * Real MR::T( size_t i, size_t _j );
 * \endcode
 *
 * Here, \a i is the "absolute" index of node i, but \a _j is
 * understood as a "relative" index, giving node \a j 's entry in
 * nb(i). The corresponding Neighbor structure can be
 * accessed as nb(i,_j) or nb(i)[_j]. The
 * absolute index of \a _j, which would be called \a j, can be
 * recovered from the \c node member: nb(i,_j).node.
 * The \c iter member gives the relative index \a _j, and the
 * \c dual member gives the "dual" relative index, i.e., the
 * index of \a i in \a j 's neighbor list.
 *
 * \code
 * Neighbor n = nb(i,_j);
 * n.node == j &&
 * n.iter == _j &&
 * nb(n.node,n.dual).node == i
 * \endcode
 *
 * There is no easy way to transform a pair of absolute node
 * indices \a i and \a j into a Neighbor structure relative
 * to one of the nodes. Such a feature has never yet been
 * found to be necessary. Iteration over edges can always be
 * accomplished using the Neighbor lists, and by writing
 * functions that accept relative indices:
 * \code
 * for( size_t i = 0; i < nrNodes(); ++i )
 * foreach( const Neighbor &j, nb(i) )
 * T( i, j.iter );
 * \endcode
 */
 struct Neighbor {
 /// Corresponds to the index of this Neighbor entry in the vector of neighbors
 size_t iter;
 /// Contains the number of the neighboring node
 size_t node;
 /// Contains the "dual" iter
 size_t dual;

 /// Default constructor
 Neighbor() {}
 /// Constructor that sets the Neighbor members according to the parameters
 Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}

 /// Cast to \c size_t returns \c node member
 operator size_t () const { return node; }
 };

 /// Describes the neighbors of some node.
 typedef std::vector Neighbors;

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

private:
/// Contains for each node a vector of its neighbors
std::vector _nb;
@@ 129,14 +126,15 @@ class GraphAL {
GraphAL( size_t nr ) : _nb( nr ) {}
/// Constructs GraphAL from a range of edges.
 /** \tparam EdgeInputIterator Iterator that iterates over instances of GraphAL::Edge.
+ /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
* \param nr The number of nodes.
* \param begin Points to the first edge.
* \param end Points just beyond the last edge.
+ * \param check Whether to only add an edge if it does not exist already.
*/
template
 GraphAL( size_t nr, EdgeInputIterator begin, EdgeInputIterator end ) : _nb() {
 construct( nr, begin, end );
+ GraphAL( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ) : _nb() {
+ construct( nr, begin, end, check );
}
//@}
@@ 170,13 +168,14 @@ class GraphAL {
/// \name Adding nodes and edges
//@{
/// (Re)constructs GraphAL from a range of edges.
 /** \tparam EdgeInputIterator Iterator that iterates over instances of GraphAL::Edge.
+ /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
* \param nr The number of nodes.
* \param begin Points to the first edge.
* \param end Points just beyond the last edge.
+ * \param check Whether to only add an edge if it does not exist already.
*/
template
 void construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end );
+ void construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true );
/// Adds a node without neighbors and returns the index of the added node.
size_t addNode() { _nb.push_back( Neighbors() ); return _nb.size()  1; }
@@ 207,7 +206,7 @@ class GraphAL {
/// Adds an edge between node \a n1 and node \a n2.
/** If \a check == \c true, only adds the edge if it does not exist already.
*/
 void addEdge( size_t n1, size_t n2, bool check = true );
+ GraphAL& addEdge( size_t n1, size_t n2, bool check = true );
//@}
/// \name Erasing nodes and edges
@@ 233,12 +232,18 @@ class GraphAL {
}
/// Returns true if the graph contains an edge between nodes \a n1 and \a n2
 /** \note The time complexity is linear in the number of neighbors of \a n1
+ /** \note The time complexity is linear in the number of neighbors of \a n1 or \a n2
*/
 bool hasEdge( size_t n1, size_t n2 ) {
 for( size_t _n2 = 0; _n2 < nb(n1).size(); _n2++ )
 if( nb( n1, _n2 ) == n2 )
 return true;
+ bool hasEdge( size_t n1, size_t n2 ) const {
+ if( nb(n1).size() < nb(n2).size() ) {
+ for( size_t _n2 = 0; _n2 < nb(n1).size(); _n2++ )
+ if( nb( n1, _n2 ) == n2 )
+ return true;
+ } else {
+ for( size_t _n1 = 0; _n1 < nb(n2).size(); _n1++ )
+ if( nb( n2, _n1 ) == n1 )
+ return true;
+ }
return false;
}
@@ 254,6 +259,9 @@ class GraphAL {
return nb(n1).size();
}
+ /// Returns neighbors of node \a n as a SmallSet.
+ SmallSet nbSet( size_t n ) const;
+
/// Returns true if the graph is connected
bool isConnected() const;
@@ 262,28 +270,57 @@ class GraphAL {
/// Asserts internal consistency
void checkConsistency() const;
+
+ /// Comparison operator which returns true if two graphs are identical
+ /** \note Two graphs are called identical if they have the same number
+ * of nodes and the same edges (i.e., \a x has an edge between nodes
+ * \a n1 and \a n2 if and only if \c *this has an edge between nodes \a n1 and \a n2).
+ */
+ bool operator==( const GraphAL& x ) const {
+ if( nrNodes() != x.nrNodes() )
+ return false;
+ for( size_t n1 = 0; n1 < nrNodes(); n1++ ) {
+ if( nb(n1).size() != x.nb(n1).size() )
+ return false;
+ bforeach( const Neighbor &n2, nb(n1) )
+ if( !x.hasEdge( n1, n2 ) )
+ return false;
+ bforeach( const Neighbor &n2, x.nb(n1) )
+ if( !hasEdge( n1, n2 ) )
+ return false;
+ }
+ return true;
+ }
//@}
/// \name Input and output
//@{
 /// Writes this GraphAL to an output stream in GraphViz .dot syntax
+ /// Writes a GraphAL to an output stream in GraphViz .dot syntax
void printDot( std::ostream& os ) const;
+
+ /// Writes a GraphAL to an output stream
+ friend std::ostream& operator<<( std::ostream& os, const GraphAL& g ) {
+ g.printDot( os );
+ return os;
+ }
+
+ /// Formats a GraphAL as a string
+ std::string toString() const {
+ std::stringstream ss;
+ ss << *this;
+ return ss.str();
+ }
//@}
};
template
void GraphAL::construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end ) {
+void GraphAL::construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check ) {
_nb.clear();
_nb.resize( nr );
 for( EdgeInputIterator e = begin; e != end; e++ ) {
#ifdef DAI_DEBUG
 addEdge( e>first, e>second, true );
#else
 addEdge( e>first, e>second, false );
#endif
 }
+ for( EdgeInputIterator e = begin; e != end; e++ )
+ addEdge( e>first, e>second, check );
}