Extended SWIG python interface (inspired by Kyle Ellrott): inference is possible...
[libdai.git] / include / dai / graph.h
index 02da765..d8ffb61 100644 (file)
@@ -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) 2006-2011, The libDAI authors. All rights reserved.
  *
- *  Copyright (C) 2006-2010  Joris Mooij  [joris dot mooij at libdai dot org]
- *  Copyright (C) 2006-2007  Radboud University Nijmegen, The Netherlands
+ *  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 <dai/smallset.h>
 
 
 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
+ *  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 <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
- *  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
-         *  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,
-         *  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
-         *  <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;
@@ -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<typename EdgeInputIterator>
-        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<typename EdgeInputIterator>
-        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
@@ -235,7 +234,7 @@ 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 or \a n2
          */
-        bool hasEdge( size_t n1, size_t n2 ) {
+        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 )
@@ -260,6 +259,9 @@ class GraphAL {
             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;
 
@@ -268,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<typename EdgeInputIterator>
-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 );
 }