Cleaned up variable elimination code in ClusterGraph
[libdai.git] / include / dai / bipgraph.h
index dfb0c50..62f1f57 100644 (file)
@@ -29,9 +29,9 @@ namespace dai {
 
 /// 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. If there are nr1()
- *  nodes of type 1 and nr2() nodes of type 2, the nodes of type 1 are numbered
- *  0,1,2,...,nr1()-1 and the nodes of type 2 are numbered 0,1,2,...,nr2()-1. An edge
+ *  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
@@ -147,14 +147,14 @@ class BipartiteGraph {
 
         /// Constructs BipartiteGraph from a range of edges.
         /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
-         *  \param nr1 The number of nodes of type 1.
-         *  \param nr2 The number of nodes of type 2.
+         *  \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.
          */
         template<typename EdgeInputIterator>
-        BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ) {
-            construct( nr1, nr2, begin, end );
+        BipartiteGraph( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1(), _nb2() {
+            construct( nrNodes1, nrNodes2, begin, end );
         }
     //@}
 
@@ -213,19 +213,30 @@ class BipartiteGraph {
     //@{
         /// (Re)constructs BipartiteGraph from a range of edges.
         /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
-         *  \param nr1 The number of nodes of type 1.
-         *  \param nr2 The number of nodes of type 2.
+         *  \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.
          */
         template<typename EdgeInputIterator>
-        void construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
+        void construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end );
 
         /// Adds a node of type 1 without neighbors and returns the index of the added node.
-        size_t add1() { _nb1.push_back( Neighbors() ); return _nb1.size() - 1; }
+        size_t addNode1() { _nb1.push_back( Neighbors() ); return _nb1.size() - 1; }
 
         /// Adds a node of type 2 without neighbors and returns the index of the added node.
-        size_t add2() { _nb2.push_back( Neighbors() ); return _nb2.size() - 1; }
+        size_t addNode2() { _nb2.push_back( Neighbors() ); return _nb2.size() - 1; }
+
+
+        /// Adds a node of type 1 without neighbors and returns the index of the added node.
+        /** \deprecated Please use dai::BipartiteGraph::addNode1() instead.
+         */
+        size_t add1() { return addNode1(); }
+
+        /// Adds a node of type 2 without neighbors and returns the index of the added node.
+        /** \deprecated Please use dai::BipartiteGraph::addNode2() instead.
+         */
+        size_t add2() { return addNode2(); }
 
         /// 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.
@@ -235,14 +246,14 @@ class BipartiteGraph {
          *  \returns Index of the added node.
          */
         template <typename NodeInputIterator>
-        size_t 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 ) {
-                DAI_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 );
             }
@@ -258,14 +269,14 @@ class BipartiteGraph {
          *  \returns Index of the added node.
          */
         template <typename NodeInputIterator>
-        size_t 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 ) {
-                DAI_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 );
             }
@@ -273,6 +284,22 @@ class BipartiteGraph {
             return _nb2.size() - 1;
         }
 
+        /// Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
+        /** \deprecated Please use dai::BipartiteGraph::addNode1( NodeInputIterator, NodeInputIterator, size_t) instead.
+         */
+        template <typename NodeInputIterator>
+        size_t add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
+            return addNode1( begin, end, sizeHint );
+        }
+
+        /// Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
+        /** \deprecated Please use dai::BipartiteGraph::addNode2( NodeInputIterator, NodeInputIterator, size_t) instead.
+         */
+        template <typename NodeInputIterator>
+        size_t add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
+            return addNode2( begin, end, sizeHint );
+        }
+        
         /// 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.
          */
@@ -282,10 +309,20 @@ class BipartiteGraph {
     /// \name Erasing nodes and edges
     //@{
         /// Removes node \a n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.
-        void erase1( size_t n1 );
+        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 node \a n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.
+        /** \deprecated Please use dai::BipartiteGraph::eraseNode1(size_t) instead.
+         */
+        void erase1( size_t n1 ) { eraseNode1( n1 ); }
 
         /// Removes node \a n2 of type 2 and all incident edges; indices of other nodes are changed accordingly.
-        void erase2( size_t n2 );
+        /** \deprecated Please use dai::BipartiteGraph::eraseNode2(size_t) instead.
+         */
+        void erase2( size_t n2 ) { eraseNode2( 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 );
@@ -294,14 +331,24 @@ class BipartiteGraph {
     /// \name Queries
     //@{
         /// Returns number of nodes of type 1
-        size_t nr1() const { return _nb1.size(); }
+        size_t nrNodes1() const { return _nb1.size(); }
+        /// Returns number of nodes of type 2
+        size_t nrNodes2() const { return _nb2.size(); }
+
+        /// Returns number of nodes of type 1
+        /** \deprecated Please use dai::BipartiteGraph::nrNodes1() instead.
+         */
+        size_t nr1() const { return nrNodes1(); }
+
         /// Returns number of nodes of type 2
-        size_t nr2() const { return _nb2.size(); }
+        /** \deprecated Please use dai::BipartiteGraph::nrNodes2() instead.
+         */
+        size_t nr2() const { return nrNodes2(); }
 
-        /// Calculates the number of edges, time complexity: O(nr1())
+        /// Calculates the number of edges, time complexity: O(nrNodes1())
         size_t nrEdges() const {
             size_t sum = 0;
-            for( size_t i1 = 0; i1 < nr1(); i1++ )
+            for( size_t i1 = 0; i1 < nrNodes1(); i1++ )
                 sum += nb1(i1).size();
             return sum;
         }
@@ -317,8 +364,6 @@ class BipartiteGraph {
         std::vector<size_t> delta2( size_t n2, bool include = false ) const;
 
         /// Returns true if the graph is connected
-        /** \todo Should be optimized by invoking boost::graph library
-         */
         bool isConnected() const;
 
         /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
@@ -337,11 +382,11 @@ class BipartiteGraph {
 
 
 template<typename EdgeInputIterator>
-void BipartiteGraph::construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) {
+void BipartiteGraph::construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end ) {
     _nb1.clear();
-    _nb1.resize( nr1 );
+    _nb1.resize( nrNodes1 );
     _nb2.clear();
-    _nb2.resize( nr2 );
+    _nb2.resize( nrNodes2 );
 
     for( EdgeInputIterator e = begin; e != end; e++ ) {
 #ifdef DAI_DEBUG