Added DAG class and various minor improvements
[libdai.git] / include / dai / bipgraph.h
index d6e720e..4dbd543 100644 (file)
@@ -1,22 +1,16 @@
-/*  Copyright (C) 2006-2008  Joris Mooij  [j dot mooij at science dot ru dot nl]
-    Radboud University Nijmegen, The Netherlands
-    
-    This file is part of libDAI.
-
-    libDAI is free software; you can redistribute it and/or modify
-    it under the terms of the GNU General Public License as published by
-    the Free Software Foundation; either version 2 of the License, or
-    (at your option) any later version.
+/*  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-2010  Joris Mooij  [joris dot mooij at libdai dot org]
+ *  Copyright (C) 2006-2007  Radboud University Nijmegen, The Netherlands
+ */
 
-    libDAI is distributed in the hope that it will be useful,
-    but WITHOUT ANY WARRANTY; without even the implied warranty of
-    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-    GNU General Public License for more details.
 
-    You should have received a copy of the GNU General Public License
-    along with libDAI; if not, write to the Free Software
-    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
-*/
+/// \file
+/// \brief Defines the BipartiteGraph class, which represents a bipartite graph
 
 
 #ifndef __defined_libdai_bipgraph_h
 
 #include <ostream>
 #include <vector>
-#include <cassert>
 #include <algorithm>
 #include <dai/util.h>
+#include <dai/smallset.h>
+#include <dai/exceptions.h>
 
 
 namespace dai {
 
 
-/// A BipartiteGraph represents the neighborhood structure of nodes in a bipartite graph.
+/// Represents the neighborhood structure of nodes in an undirected, bipartite graph.
 /** A bipartite graph has two types of nodes: type 1 and type 2. Edges can occur only between
- *  nodes of different type. Nodes are indexed by an unsigned integer, edges are indexed as
- *  a pair of unsigned integers (where the pair (a,b) means the b'th neighbor of the a'th node).
- *  The BipartiteGraph stores neighborhood structures as vectors of vectors of Neighbor entries.
+ *  nodes of different type. Nodes are indexed by an unsigned integer. If there are nrNodes1()
+ *  nodes of type 1 and nrNodes2() nodes of type 2, the nodes of type 1 are numbered
+ *  0,1,2,...,nrNodes1()-1 and the nodes of type 2 are numbered 0,1,2,...,nrNodes2()-1. An edge
+ *  between node \a n1 of type 1 and node \a n2 of type 2 is represented by a BipartiteGraph::Edge(\a n1,\a n2).
+ *
+ *  A BipartiteGraph is implemented as a sparse adjacency list, i.e., it stores for each node a list of
+ *  its neighboring nodes. More precisely: it stores for each node of type 1 a vector of Neighbor structures
+ *  (accessible by the nb1() method) describing the neighboring nodes of type 2; similarly, for each node
+ *  of type 2 it stores a vector of Neighbor structures (accessibly by the nb2() method) describing the
+ *  neighboring nodes of type 1.
+ *  Thus, each node has an associated variable of type BipartiteGraph::Neighbors, which is a vector of
+ *  Neighbor structures, describing its neighboring nodes of the other type.
+ *  \idea Cache second-order neighborhoods in BipartiteGraph.
  */
 class BipartiteGraph {
     public:
-        /// A Neighbor describes a neighboring node of some other node.
-        /** Iterating over all neighbors of node n1 of type 1 can be done in the following way:
+        /// Describes the neighbor relationship of two nodes in a BipartiteGraph.
+        /** 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
-         *      foreach( const BipartiteGraph::Neighbor &n2, nb1(n1) ) {
-         *          size_t _n2 = n2.iter;
-         *          size_t _n1 = n2.dual;
-         *          // n2 == n2.node;
-         *          // The _n2'th neighbor of n1 is n2, and the _n1'th neighbor of n2 is n1:
-         *          // nb1(n1)[_n2] == n2, nb2(n2)[_n1] == n1 
-         *      }
+         *  void BP::calcNewMessage( size_t i, size_t _I )
+         *  \endcode
+         *
+         *  Here, \a i is the "absolute" index of node i, but \a _I is
+         *  understood as a "relative" index, giving node \a I 's entry in
+         *  <tt>nb1(i)</tt>. The corresponding Neighbor structure can be
+         *  accessed as <tt>nb1(i,_I)</tt> or <tt>nb1(i)[_I]</tt>. The 
+         *  absolute index of \a _I, which would be called \a I, can be 
+         *  recovered from the \c node member: <tt>nb1(i,_I).node</tt>. 
+         *  The \c iter member gives the relative index \a _I, and the 
+         *  \c dual member gives the "dual" relative index, i.e., the 
+         *  index of \a i in \a I 's neighbor list.
+         *
+         *  \code
+         *  Neighbor n = nb1(i,_I);
+         *  n.node == I &&
+         *  n.iter == _I &&
+         *  nb2(n.node,n.dual).node == i
+         *  \endcode
+         *
+         *  In a FactorGraph, the nodes of type 1 represent variables, and
+         *  the nodes of type 2 represent factors. For convenience, nb1() is 
+         *  called FactorGraph::nbV(), and nb2() is called FactorGraph::nbF().
+         *
+         *  There is no easy way to transform a pair of absolute node
+         *  indices \a i and \a I 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 < nrVars(); ++i )
+         *      foreach( const Neighbor &I, nbV(i) )
+         *          calcNewMessage( i, I.iter );
          *  \endcode
          */
         struct Neighbor {
             /// Corresponds to the index of this Neighbor entry in the vector of neighbors
-            unsigned iter;
+            size_t iter;
             /// Contains the number of the neighboring node
-            unsigned node;
+            size_t node;
             /// Contains the "dual" iter
-            unsigned dual;
-            /// Cast to unsigned returns node
-            operator unsigned () const { return node; }
+            size_t dual;
+
             /// Default constructor
             Neighbor() {}
-            /// Constructor
+            /// 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; }
         };
 
-        /// Neighbors is a vector of Neighbor entries; each node has an associated Neighbors variable, which describes its neighbors.
+        /// Describes the neighbors of some node.
         typedef std::vector<Neighbor> Neighbors;
 
-        /// Edge is used as index of an edge: an Edge(a,b) corresponds to the edge between the a'th node and its b'th neighbor.
+        /// Represents an edge: an Edge(\a n1,\a n2) corresponds to the edge between node \a n1 of type 1 and node \a n2 of type 2.
         typedef std::pair<size_t,size_t> Edge;
 
     private:
-        /// _nb1 contains for each node of type 1 a vector of its neighbors
+        /// Contains for each node of type 1 a vector of its neighbors
         std::vector<Neighbors> _nb1;
-        /// _nb2 contains for each node of type 2 a vector of its neighbors
+
+        /// Contains for each node of type 2 a vector of its neighbors
         std::vector<Neighbors> _nb2;
 
         /// Used internally by isTree()
         struct levelType {
-            std::vector<size_t> ind1;       // indices of vertices of type 1
-            std::vector<size_t> ind2;       // indices of vertices of type 2
+            /// Indices of nodes of type 1
+            std::vector<size_t> ind1;       
+            /// Indices of nodes of type 2
+            std::vector<size_t> ind2;
         };
 
     public:
-        /// Default constructor
+    /// \name Constructors and destructors
+    //@{
+        /// Default constructor (creates an empty bipartite graph)
         BipartiteGraph() : _nb1(), _nb2() {}
 
-        /// Copy constructor
-        BipartiteGraph( const BipartiteGraph & x ) : _nb1(x._nb1), _nb2(x._nb2) {}
+        /// Constructs BipartiteGraph with \a nr1 nodes of type 1, \a nr2 nodes of type 2 and no edges.
+        BipartiteGraph( size_t nr1, size_t nr2 ) : _nb1(nr1), _nb2(nr2) {}
 
-        /// Assignment operator
-        BipartiteGraph & operator=( const BipartiteGraph & x ) {
-            if( this != &x ) {
-                _nb1 = x._nb1;
-                _nb2 = x._nb2;
-            }
-            return *this;
-        }
-
-        /// Create bipartite graph from a range of edges. 
-        /** nr1 is the number of nodes of type 1, nr2 the number of nodes of type 2. 
-         *  The value_type of an EdgeInputIterator should be Edge.
+        /// Constructs BipartiteGraph from a range of edges.
+        /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
+         *  \param nrNodes1 The number of nodes of type 1.
+         *  \param nrNodes2 The number of nodes of type 2.
+         *  \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 create( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
+        BipartiteGraph( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ) : _nb1(), _nb2() {
+            construct( nrNodes1, nrNodes2, begin, end, check );
+        }
+    //@}
+
+    /// \name Accessors and mutators
+    //@{
+        /// Returns constant reference to the \a _i2 'th neighbor of node \a i1 of type 1
+        const Neighbor & nb1( size_t i1, size_t _i2 ) const {
+            DAI_DEBASSERT( i1 < _nb1.size() );
+            DAI_DEBASSERT( _i2 < _nb1[i1].size() );
+            return _nb1[i1][_i2];
+        }
+        /// Returns reference to the \a _i2 'th neighbor of node \a i1 of type 1
+        Neighbor & nb1( size_t i1, size_t _i2 ) {
+            DAI_DEBASSERT( i1 < _nb1.size() );
+            DAI_DEBASSERT( _i2 < _nb1[i1].size() );
+            return _nb1[i1][_i2];
+        }
 
-        /// Construct bipartite graph from a range of edges. 
-        /** nr1 is the number of nodes of type 1, nr2 the number of nodes of type 2. 
-         *  The value_type of an EdgeInputIterator should be Edge.
-         */
-        template<typename EdgeInputIterator>
-        BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ) {
-            create( nr1, nr2, begin, end );
+        /// Returns constant reference to the \a _i1 'th neighbor of node \a i2 of type 2
+        const Neighbor & nb2( size_t i2, size_t _i1 ) const {
+            DAI_DEBASSERT( i2 < _nb2.size() );
+            DAI_DEBASSERT( _i1 < _nb2[i2].size() );
+            return _nb2[i2][_i1];
+        }
+        /// Returns reference to the \a _i1 'th neighbor of node \a i2 of type 2
+        Neighbor & nb2( size_t i2, size_t _i1 ) {
+            DAI_DEBASSERT( i2 < _nb2.size() );
+            DAI_DEBASSERT( _i1 < _nb2[i2].size() );
+            return _nb2[i2][_i1];
         }
 
-        /// Returns constant reference to the _i2'th neighbor of node i1 of type 1
-        const Neighbor & nb1( size_t i1, size_t _i2 ) const { return _nb1[i1][_i2]; }
-        /// Returns reference to the _i2'th neighbor of node i1 of type 1
-        Neighbor & nb1( size_t i1, size_t _i2 ) { return _nb1[i1][_i2]; }
+        /// Returns constant reference to all neighbors of node \a i1 of type 1
+        const Neighbors & nb1( size_t i1 ) const {
+            DAI_DEBASSERT( i1 < _nb1.size() );
+            return _nb1[i1];
+        }
+        /// Returns reference to all neighbors of node \a i1 of type 1
+        Neighbors & nb1( size_t i1 ) {
+            DAI_DEBASSERT( i1 < _nb1.size() );
+            return _nb1[i1];
+        }
 
-        /// Returns constant reference to the _i1'th neighbor of node i2 of type 2
-        const Neighbor & nb2( size_t i2, size_t _i1 ) const { return _nb2[i2][_i1]; }
-        /// Returns reference to the _i1'th neighbor of node i2 of type 2
-        Neighbor & nb2( size_t i2, size_t _i1 ) { return _nb2[i2][_i1]; }
+        /// Returns constant reference to all neighbors of node \a i2 of type 2
+        const Neighbors & nb2( size_t i2 ) const {
+            DAI_DEBASSERT( i2 < _nb2.size() );
+            return _nb2[i2];
+        }
+        /// Returns reference to all neighbors of node \a i2 of type 2
+        Neighbors & nb2( size_t i2 ) {
+            DAI_DEBASSERT( i2 < _nb2.size() );
+            return _nb2[i2];
+        }
+    //@}
+
+    /// \name Adding nodes and edges
+    //@{
+        /// (Re)constructs BipartiteGraph from a range of edges.
+        /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
+         *  \param nrNodes1 The number of nodes of type 1.
+         *  \param nrNodes2 The number of nodes of type 2.
+         *  \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 nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check=true );
 
-        /// Returns constant reference to all neighbors of node i1 of type 1
-        const Neighbors & nb1( size_t i1 ) const { return _nb1[i1]; }
-        /// Returns reference to all neighbors of node of i1 type 1
-        Neighbors & nb1( size_t i1 ) { return _nb1[i1]; }
+        /// Adds a node of type 1 without neighbors and returns the index of the added node.
+        size_t addNode1() { _nb1.push_back( Neighbors() ); return _nb1.size() - 1; }
 
-        /// Returns constant reference to all neighbors of node i2 of type 2
-        const Neighbors & nb2( size_t i2 ) const { return _nb2[i2]; }
-        /// Returns reference to all neighbors of node i2 of type 2
-        Neighbors & nb2( size_t i2 ) { return _nb2[i2]; }
+        /// Adds a node of type 2 without neighbors and returns the index of the added node.
+        size_t addNode2() { _nb2.push_back( Neighbors() ); return _nb2.size() - 1; }
 
-        /// Returns number of nodes of type 1
-        size_t nr1() const { return _nb1.size(); }
-        /// Returns number of nodes of type 2
-        size_t nr2() const { return _nb2.size(); }
-        
-        /// Calculates the number of edges
-        size_t nrEdges() const {
-            size_t sum = 0;
-            for( size_t i1 = 0; i1 < nr1(); i1++ )
-                sum += nb1(i1).size();
-            return sum;
-        }
-        
-        /// Add node of type 1 without neighbors.
-        void add1() {
-            _nb1.push_back( Neighbors() );
-        }
-        
-        /// Add node of type 2 without neighbors.
-        void add2() {
-            _nb2.push_back( Neighbors() );
-        }
 
-        /// Add node of type 1 with neighbors specified by a range.
-        /** The value_type of an NodeInputIterator should be a size_t, corresponding to
-         *  the indices of nodes of type 2 that should become neighbors of the added node.
-         *  For improved efficiency, the size of the range may be specified by sizeHint.
+        /// Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
+        /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
+         *  \param begin Points to the first index of the nodes of type 2 that should become neighbors of the added node.
+         *  \param end Points just beyond the last index of the nodes of type 2 that should become neighbors of the added node.
+         *  \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
+         *  \returns Index of the added node.
          */
         template <typename NodeInputIterator>
-        void add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
+        size_t addNode1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
             Neighbors nbs1new;
             nbs1new.reserve( sizeHint );
             size_t iter = 0;
             for( NodeInputIterator it = begin; it != end; ++it ) {
-                assert( *it < nr2() );
+                DAI_ASSERT( *it < nrNodes2() );
                 Neighbor nb1new( iter, *it, nb2(*it).size() );
-                Neighbor nb2new( nb2(*it).size(), nr1(), iter++ );
+                Neighbor nb2new( nb2(*it).size(), nrNodes1(), iter++ );
                 nbs1new.push_back( nb1new );
                 nb2( *it ).push_back( nb2new );
             }
             _nb1.push_back( nbs1new );
+            return _nb1.size() - 1;
         }
 
-        /// Add node of type 2 with neighbors specified by a range.
-        /** The value_type of an NodeInputIterator should be a size_t, corresponding to
-         *  the indices of nodes of type 1 that should become neighbors of the added node.
-         *  For improved efficiency, the size of the range may be specified by sizeHint.
+        /// Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
+        /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
+         *  \param begin Points to the first index of the nodes of type 1 that should become neighbors of the added node.
+         *  \param end Points just beyond the last index of the nodes of type 1 that should become neighbors of the added node.
+         *  \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
+         *  \returns Index of the added node.
          */
         template <typename NodeInputIterator>
-        void add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
+        size_t addNode2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
             Neighbors nbs2new;
             nbs2new.reserve( sizeHint );
             size_t iter = 0;
             for( NodeInputIterator it = begin; it != end; ++it ) {
-                assert( *it < nr1() );
+                DAI_ASSERT( *it < nrNodes1() );
                 Neighbor nb2new( iter, *it, nb1(*it).size() );
-                Neighbor nb1new( nb1(*it).size(), nr2(), iter++ );
+                Neighbor nb1new( nb1(*it).size(), nrNodes2(), iter++ );
                 nbs2new.push_back( nb2new );
                 nb1( *it ).push_back( nb1new );
             }
             _nb2.push_back( nbs2new );
+            return _nb2.size() - 1;
         }
 
-        /// Remove node of type 1 and all incident edges.
-        void erase1( size_t n1 ) {
-            assert( n1 < nr1() );
-            // Erase neighbor entry of node n1
-            _nb1.erase( _nb1.begin() + n1 );
-            // Adjust neighbor entries of nodes of type 2
-            for( size_t n2 = 0; n2 < nr2(); n2++ )
-                for( size_t iter = 0; iter < nb2(n2).size(); ) {
-                    if( nb2(n2, iter).node == n1 ) {
-                        // delete this entry, because it points to the deleted node
-                        nb2(n2).erase( nb2(n2).begin() + iter );
-                        // adjust all subsequent entries:
-                        // update their iter and the corresponding dual of the neighboring node of type 1
-                        for( size_t newiter = iter; newiter < nb2(n2).size(); newiter++ ) {
-                            nb2( n2, newiter ).iter = newiter;
-                            nb1( nb2(n2, newiter).node, nb2(n2, newiter).dual ).dual = newiter;
-                        }
-                    } else if( nb2(n2, iter).node > n1 ) {
-                        nb2(n2, iter).node--;
-                        iter++;
-                    } else
-                        iter++;
-                }
+        /// Adds an edge between node \a n1 of type 1 and node \a n2 of type 2.
+        /** If \a check == \c true, only adds the edge if it does not exist already.
+         */
+        BipartiteGraph& addEdge( size_t n1, size_t n2, bool check = true );
+    //@}
+
+    /// \name Erasing nodes and edges
+    //@{
+        /// Removes node \a n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.
+        void eraseNode1( size_t n1 );
+
+        /// Removes node \a n2 of type 2 and all incident edges; indices of other nodes are changed accordingly.
+        void eraseNode2( size_t n2 );
+
+        /// Removes edge between node \a n1 of type 1 and node \a n2 of type 2.
+        void eraseEdge( size_t n1, size_t n2 );
+    //@}
+
+    /// \name Queries
+    //@{
+        /// Returns number of nodes of type 1
+        size_t nrNodes1() const { return _nb1.size(); }
+        /// Returns number of nodes of type 2
+        size_t nrNodes2() const { return _nb2.size(); }
+
+        /// Calculates the number of edges, time complexity: O(nrNodes1())
+        size_t nrEdges() const {
+            size_t sum = 0;
+            for( size_t i1 = 0; i1 < nrNodes1(); i1++ )
+                sum += nb1(i1).size();
+            return sum;
         }
 
-        /// Remove node of type 2 and all incident edges.
-        void erase2( size_t n2 ) {
-            assert( n2 < nr2() );
-            // Erase neighbor entry of node n2
-            _nb2.erase( _nb2.begin() + n2 );
-            // Adjust neighbor entries of nodes of type 1
-            for( size_t n1 = 0; n1 < nr1(); n1++ )
-                for( size_t iter = 0; iter < nb1(n1).size(); ) {
-                    if( nb1(n1, iter).node == n2 ) {
-                        // delete this entry, because it points to the deleted node
-                        nb1(n1).erase( nb1(n1).begin() + iter );
-                        // adjust all subsequent entries:
-                        // update their iter and the corresponding dual of the neighboring node of type 2
-                        for( size_t newiter = iter; newiter < nb1(n1).size(); newiter++ ) {
-                            nb1( n1, newiter ).iter = newiter;
-                            nb2( nb1(n1, newiter).node, nb1(n1, newiter).dual ).dual = newiter;
-                        }
-                    } else if( nb1(n1, iter).node > n2 ) {
-                        nb1(n1, iter).node--;
-                        iter++;
-                    } else
-                        iter++;
-                }
+        /// Returns true if the graph contains an edge between node \a n1 of type 1 and node \a n2 of type 2.
+        /** \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 ) const {
+            if( nb1(n1).size() < nb2(n2).size() ) {
+                for( size_t _n2 = 0; _n2 < nb1(n1).size(); _n2++ )
+                    if( nb1( n1, _n2 ) == n2 )
+                        return true;
+            } else {
+                for( size_t _n1 = 0; _n1 < nb2(n2).size(); _n1++ )
+                    if( nb2( n2, _n1 ) == n1 )
+                        return true;
+            }
+            return false;
         }
 
-        /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
-        /** If include == true, include n1 itself, otherwise exclude n1.
+        /// Returns the index of a given node \a n2 of type 2 amongst the neighbors of node \a n1 of type 1
+        /** \note The time complexity is linear in the number of neighbors of \a n1
+         *  \throw OBJECT_NOT_FOUND if \a n2 is not a neighbor of \a n1
          */
-        std::vector<size_t> delta1( size_t n1, bool include = false ) const {
-            std::vector<size_t> result;
-            foreach( const Neighbor &n2, nb1(n1) )
-                foreach( const Neighbor &m1, nb2(n2) )
-                    if( include || (m1 != n1) )
-                        result.push_back( m1 );
-            // remove duplicates
-            std::vector<size_t>::iterator it = std::unique( result.begin(), result.end() );
-            result.erase( it, result.end() );
-            return result;
+        size_t findNb1( size_t n1, size_t n2 ) {
+            for( size_t _n2 = 0; _n2 < nb1(n1).size(); _n2++ )
+                if( nb1( n1, _n2 ) == n2 )
+                    return _n2;
+            DAI_THROW(OBJECT_NOT_FOUND);
+            return nb1(n1).size();
         }
 
-        /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
-        /** If include == true, include n2 itself, otherwise exclude n2.
+        /// Returns the index of a given node \a n1 of type 1 amongst the neighbors of node \a n2 of type 2
+        /** \note The time complexity is linear in the number of neighbors of \a n2
+         *  \throw OBJECT_NOT_FOUND if \a n1 is not a neighbor of \a n2
          */
-        std::vector<size_t> delta2( size_t n2, bool include = false ) const {
-            std::vector<size_t> result;
-            foreach( const Neighbor &n1, nb2(n2) )
-                foreach( const Neighbor &m2, nb1(n1) )
-                    if( include || (m2 != n2) )
-                        result.push_back( m2 );
-            // remove duplicates
-            std::vector<size_t>::iterator it = std::unique( result.begin(), result.end() );
-            result.erase( it, result.end() );
-            return result;
+        size_t findNb2( size_t n1, size_t n2 ) {
+            for( size_t _n1 = 0; _n1 < nb2(n2).size(); _n1++ )
+                if( nb2( n2, _n1 ) == n1 )
+                    return _n1;
+            DAI_THROW(OBJECT_NOT_FOUND);
+            return nb2(n2).size();
         }
 
+        /// Returns neighbors of node \a n1 of type 1 as a SmallSet<size_t>.
+        SmallSet<size_t> nb1Set( size_t n1 ) const;
+
+        /// Returns neighbors of node \a n2 of type 2 as a SmallSet<size_t>.
+        SmallSet<size_t> nb2Set( size_t n2 ) const;
+
+        /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n1 of type 1.
+        /** If \a include == \c true, includes \a n1 itself, otherwise excludes \a n1.
+         *  \note In libDAI versions 0.2.4 and earlier, this function used to return a std::vector<size_t>
+         */
+        SmallSet<size_t> delta1( size_t n1, bool include = false ) const;
+
+        /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n2 of type 2.
+        /** If \a include == \c true, includes \a n2 itself, otherwise excludes \a n2.
+         *  \note In libDAI versions 0.2.4 and earlier, this function used to return a std::vector<size_t>
+         */
+        SmallSet<size_t> delta2( size_t n2, bool include = false ) const;
+
         /// Returns true if the graph is connected
-        bool isConnected() const {
-            if( nr1() == 0 ) {
-                return true;
-            } else {
-                std::vector<bool> incomponent1( nr1(), false );
-                std::vector<bool> incomponent2( nr2(), false );
-
-                incomponent1[0] = true;
-                bool found_new_nodes;
-                do {
-                    found_new_nodes = false;
-
-                    // For all nodes of type 2, check if they are connected with the (growing) component
-                    for( size_t n2 = 0; n2 < nr2(); n2++ )
-                        if( !incomponent2[n2] ) {
-                            foreach( const Neighbor &n1, nb2(n2) ) {
-                                if( incomponent1[n1] ) {
-                                    found_new_nodes = true;
-                                    incomponent2[n2] = true;
-                                    break;
-                                }
-                            }
-                        }
-
-                    // For all nodes of type 1, check if they are connected with the (growing) component
-                    for( size_t n1 = 0; n1 < nr1(); n1++ )
-                        if( !incomponent1[n1] ) {
-                            foreach( const Neighbor &n2, nb1(n1) ) {
-                                if( incomponent2[n2] ) {
-                                    found_new_nodes = true;
-                                    incomponent1[n1] = true;
-                                    break;
-                                }
-                            }
-                        }
-                } while( found_new_nodes );
-
-                // Check if there are remaining nodes (not in the component)
-                bool all_connected = true;
-                for( size_t n1 = 0; (n1 < nr1()) && all_connected; n1++ )
-                    if( !incomponent1[n1] )
-                        all_connected = false;
-                for( size_t n2 = 0; (n2 < nr2()) && all_connected; n2++ )
-                    if( !incomponent2[n2] )
-                        all_connected = false;
-
-                return all_connected;
-            }
-        }
+        bool isConnected() const;
 
         /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
-        /** This is equivalent to whether for each pair of vertices in the graph, there exists
-         *  a unique path in the graph that starts at the first and ends at the second vertex.
+        bool isTree() 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
+         *  of both types 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 isTree() const {
-            using namespace std;
-            vector<levelType> levels;
-
-            bool foundCycle = false;
-            size_t nr_1 = 0;
-            size_t nr_2 = 0;
-
-            if( nr1() == 0 || nr2() == 0 )
-                return true;
-            else {
-                levelType newLevel;
-                do {
-                    newLevel.ind1.clear();
-                    newLevel.ind2.clear();
-                    if( levels.size() == 0 ) {
-                        size_t n1 = 0;
-                        // add n1 to ind1
-                        newLevel.ind1 = vector<size_t>( 1, n1 );
-                        // add all neighbors of n1 to ind2
-                        newLevel.ind2.reserve( nb1(n1).size() );
-                        foreach( const Neighbor &n2, nb1(n1) )
-                            newLevel.ind2.push_back( n2 );
-                    } else {
-                        const levelType &prevLevel = levels.back();
-                        // build newLevel.ind1
-                        foreach( size_t n2, prevLevel.ind2 ) { // for all n2 in the previous level
-                            foreach( const Neighbor &n1, nb2(n2) ) { // for all neighbors n1 of n2
-                                if( find( prevLevel.ind1.begin(), prevLevel.ind1.end(), n1 ) == prevLevel.ind1.end() ) { // n1 not in previous level
-                                    if( find( newLevel.ind1.begin(), newLevel.ind1.end(), n1 ) != newLevel.ind1.end() )
-                                        foundCycle = true; // n1 already in new level: we found a cycle
-                                    else
-                                        newLevel.ind1.push_back( n1 ); // add n1 to new level
-                                }
-                                if( foundCycle )
-                                    break;
-                            }
-                            if( foundCycle )
-                                break;
-                        }
-                        // build newLevel.ind2
-                        foreach( size_t n1, newLevel.ind1 ) { // for all n1 in this level
-                            foreach( const Neighbor &n2, nb1(n1) ) { // for all neighbors n2 of n1
-                                if( find( prevLevel.ind2.begin(), prevLevel.ind2.end(), n2 ) == prevLevel.ind2.end() ) { // n2 not in previous level
-                                    if( find( newLevel.ind2.begin(), newLevel.ind2.end(), n2 ) != newLevel.ind2.end() )
-                                        foundCycle = true; // n2 already in new level: we found a cycle
-                                    else
-                                        newLevel.ind2.push_back( n2 ); // add n2 to new level
-                                }
-                                if( foundCycle )
-                                    break;
-                            }
-                            if( foundCycle )
-                                break;
-                        } 
-                    }
-                    levels.push_back( newLevel );
-                    nr_1 += newLevel.ind1.size();
-                    nr_2 += newLevel.ind2.size();
-                } while( ((newLevel.ind1.size() != 0) || (newLevel.ind2.size() != 0)) && !foundCycle );
-                if( nr_1 == nr1() && nr_2 == nr2() && !foundCycle )
-                    return true;
-                else
+        bool operator==( const BipartiteGraph& x ) const {
+            if( nrNodes1() != x.nrNodes1() )
+                return false;
+            if( nrNodes2() != x.nrNodes2() )
+                return false;
+            for( size_t n1 = 0; n1 < nrNodes1(); n1++ ) {
+                if( nb1(n1).size() != x.nb1(n1).size() )
                     return false;
+                foreach( const Neighbor &n2, nb1(n1) )
+                    if( !x.hasEdge( n1, n2 ) )
+                        return false;
+                foreach( const Neighbor &n2, x.nb1(n1) )
+                    if( !hasEdge( n1, n2 ) )
+                        return false;
             }
+            return true;
         }
 
-        /// Stream to output stream os in graphviz .dot syntax
-        void display( std::ostream& os ) const {
-            using namespace std;
-            os << "graph G {" << endl;
-            os << "node[shape=circle,width=0.4,fixedsize=true];" << endl;
-            for( size_t n1 = 0; n1 < nr1(); n1++ )
-                os << "\tx" << n1 << ";" << endl;
-            os << "node[shape=box,width=0.3,height=0.3,fixedsize=true];" << endl;
-            for( size_t n2 = 0; n2 < nr2(); n2++ )
-                os << "\ty" << n2 << ";" << endl;
-            for( size_t n1 = 0; n1 < nr1(); n1++ )
-                foreach( const Neighbor &n2, nb1(n1) )
-                    os << "\tx" << n1 << " -- y" << n2 << ";" << endl;
-            os << "}" << endl;
+        /// Asserts internal consistency
+        void checkConsistency() const;
+    //@}
+
+    /// \name Input and output
+    //@{
+        /// Writes this BipartiteGraph to an output stream in GraphViz .dot syntax
+        void printDot( std::ostream& os ) const;
+
+        /// Writes this BipartiteGraph to an output stream
+        friend std::ostream& operator<<( std::ostream& os, const BipartiteGraph& g ) {
+            g.printDot( os );
+            return os;
         }
+    //@}
 };
 
 
 template<typename EdgeInputIterator>
-void BipartiteGraph::create( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) {
+void BipartiteGraph::construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check ) {
     _nb1.clear();
-    _nb1.resize( nr1 );
+    _nb1.resize( nrNodes1 );
     _nb2.clear();
-    _nb2.resize( nr2 );
-
-    for( EdgeInputIterator e = begin; e != end; e++ ) {
-        // Each edge yields a neighbor pair
-        Neighbor nb_1( _nb1[e->first].size(), e->second, _nb2[e->second].size() );
-        Neighbor nb_2( nb_1.dual, e->first, nb_1.iter );
-        _nb1[e->first].push_back( nb_1 );
-        _nb2[e->second].push_back( nb_2 );
-    }
+    _nb2.resize( nrNodes2 );
+
+    for( EdgeInputIterator e = begin; e != end; e++ )
+        addEdge( e->first, e->second, check );
 }
 
 
 } // end of namespace dai
 
 
+/** \example example_bipgraph.cpp
+ *  This example deals with the following bipartite graph:
+ *  \dot
+ *  graph example {
+ *    ordering=out;
+ *    subgraph cluster_type1 {
+ *      node[shape=circle,width=0.4,fixedsize=true,style=filled];
+ *      12 [label="2"];
+ *      11 [label="1"];
+ *      10 [label="0"];
+ *    }
+ *    subgraph cluster_type2 {
+ *      node[shape=polygon,regular=true,sides=4,width=0.4,fixedsize=true,style=filled];
+ *      21 [label="1"];
+ *      20 [label="0"];
+ *    }
+ *    10 -- 20;
+ *    11 -- 20;
+ *    12 -- 20;
+ *    11 -- 21;
+ *    12 -- 21;
+ *  }
+ *  \enddot
+ *  It has three nodes of type 1 (drawn as circles) and two nodes of type 2 (drawn as rectangles).
+ *  Node 0 of type 1 has only one neighbor (node 0 of type 2), but node 0 of type 2 has three neighbors (nodes 0,1,2 of type 1).
+ *  The example code shows how to construct a BipartiteGraph object representing this bipartite graph and
+ *  how to iterate over nodes and their neighbors.
+ *
+ *  \section Output
+ *  \verbinclude examples/example_bipgraph.out
+ *
+ *  \section Source
+ */
+
+
 #endif