index b72a2b4..d8ffb61 100644 (file)
@@ -1,11 +1,8 @@
/*  This file is part of libDAI - http://www.libdai.org/
*
/*  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) 2006-2011, The libDAI authors. All rights reserved.
*
*
- *  Copyright (C) 2006-2010  Joris Mooij  [joris dot mooij at libdai dot org]
+ *  Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
*/

*/

#include <algorithm>
#include <dai/util.h>
#include <dai/exceptions.h>
#include <algorithm>
#include <dai/util.h>
#include <dai/exceptions.h>
+#include <dai/smallset.h>

namespace dai {

namespace dai {

+/// Describes the neighbor relationship of two nodes in a graph.
+/** Most graphs that libDAI deals with are sparse. Therefore,
+ *  a fast and memory-efficient 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
+ *  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 <tt>nb(i,_j)</tt>,
+ *  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 <tt>nb(i)</tt> of node \a i. The absolute
+ *  index of \a _j, which would be denoted \a j, can be recovered from the
+ *  \c node member, <tt>nb(i,_j).node</tt>. The \c iter member
+ *  <tt>nb(i,_j).iter</tt> gives the relative index \a _j, and the \c dual
+ *  member <tt>nb(i,_j).dual</tt> 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<Neighbor> 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<size_t,size_t> 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
/// 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
*
*  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 {
*  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
-         *  memory-efficient. 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,
-         *  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
-         *  <tt>nb(i)</tt>. The corresponding Neighbor structure can be
-         *  accessed as <tt>nb(i,_j)</tt> or <tt>nb(i)[_j]</tt>. The
-         *  absolute index of \a _j, which would be called \a j, can be
-         *  recovered from the \c node member: <tt>nb(i,_j).node</tt>.
-         *  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<Neighbor> 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<size_t,size_t> Edge;
-
private:
/// Contains for each node a vector of its neighbors
std::vector<Neighbors> _nb;
private:
/// Contains for each node a vector of its neighbors
std::vector<Neighbors> _nb;
@@ -129,7 +126,7 @@ class GraphAL {
GraphAL( size_t nr ) : _nb( nr ) {}

/// Constructs GraphAL from a range of edges.
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 nr The number of nodes.
*  \param begin Points to the first edge.
*  \param end Points just beyond the last edge.
@@ -171,7 +168,7 @@ class GraphAL {
/// \name Adding nodes and edges
//@{
/// (Re)constructs GraphAL from a range of edges.
/// \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 nr The number of nodes.
*  \param begin Points to the first edge.
*  \param end Points just beyond the last edge.
@@ -209,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.
*/
/// 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
//@}

/// \name Erasing nodes and edges
@@ -262,6 +259,9 @@ class GraphAL {
return nb(n1).size();
}

return nb(n1).size();
}

+        /// Returns neighbors of node \a n as a SmallSet<size_t>.
+        SmallSet<size_t> nbSet( size_t n ) const;
+
/// Returns true if the graph is connected
bool isConnected() const;

/// Returns true if the graph is connected
bool isConnected() const;

@@ -274,7 +274,7 @@ class GraphAL {
/// 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
/// 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
-         *  n1 and n2 if and only if \c *this has an edge between nodes n1 and n2).
+         *  \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() )
*/
bool operator==( const GraphAL& x ) const {
if( nrNodes() != x.nrNodes() )
@@ -282,10 +282,10 @@ class GraphAL {
for( size_t n1 = 0; n1 < nrNodes(); n1++ ) {
if( nb(n1).size() != x.nb(n1).size() )
return false;
for( size_t n1 = 0; n1 < nrNodes(); n1++ ) {
if( nb(n1).size() != x.nb(n1).size() )
return false;
-                foreach( const Neighbor &n2, nb(n1) )
+                bforeach( const Neighbor &n2, nb(n1) )
if( !x.hasEdge( n1, n2 ) )
return false;
if( !x.hasEdge( n1, n2 ) )
return false;
-                foreach( const Neighbor &n2, x.nb(n1) )
+                bforeach( const Neighbor &n2, x.nb(n1) )
if( !hasEdge( n1, n2 ) )
return false;
}
if( !hasEdge( n1, n2 ) )
return false;
}
@@ -295,8 +295,21 @@ class GraphAL {

/// \name Input and output
//@{

/// \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;
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();
+        }
//@}
};

//@}
};