Renamed some functions of BipartiteGraph

diff --git a/ChangeLog b/ChangeLog
index 90076a8..e678e04 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+* Renamed some functions of BipartiteGraph:
+    add1() -> addNode1()
+    erase1() -> eraseNode1()
+    nr1() -> nrNodes1()
+    add2() -> addNode2()
+    erase2() -> eraseNode2()
+    nr2() -> nrNodes2()
 * Added examples example_sprinkler_gibbs and example_sprinkler_em
 * Optimized BipartiteGraph::isConnected() by using Boost Graph Library implementation
 * Strengthened convergence criteria of various algorithms

diff --git a/examples/example_bipgraph.cpp b/examples/example_bipgraph.cpp
index 53c43be..ff5ebae 100644 (file)
--- a/examples/example_bipgraph.cpp
+++ b/examples/example_bipgraph.cpp
@@ -28,10 +28,10 @@ int main() {
     BipartiteGraph G( 3, 2, edges.begin(), edges.end() );
 
     // Display some information about G
-    cout << "G has " << G.nr1() << " nodes of type 1, " << G.nr2() << " nodes of type 2 and " << G.nrEdges() << " edges." << endl << endl;
+    cout << "G has " << G.nrNodes1() << " nodes of type 1, " << G.nrNodes2() << " nodes of type 2 and " << G.nrEdges() << " edges." << endl << endl;
 
     // Iterate over all nodes n1 of type 1
-    for( size_t n1 = 0; n1 < G.nr1(); n1++ ) {
+    for( size_t n1 = 0; n1 < G.nrNodes1(); n1++ ) {
         cout << "Node " << n1 << " of type 1 has " << G.nb1(n1).size() << " neighbors:" << endl;
         // Iterate over all neighbors n2 of n1
         foreach( const BipartiteGraph::Neighbor &n2, G.nb1(n1) ) {

diff --git a/include/dai/bipgraph.h b/include/dai/bipgraph.h
index 4128339..62f1f57 100644 (file)
--- a/include/dai/bipgraph.h
+++ b/include/dai/bipgraph.h
@@ -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(), _nb2() {
-            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;
         }
@@ -335,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

diff --git a/include/dai/clustergraph.h b/include/dai/clustergraph.h
index cfa5dbe..bb77ba4 100644 (file)
--- a/include/dai/clustergraph.h
+++ b/include/dai/clustergraph.h
@@ -63,7 +63,7 @@ namespace dai {
 
             /// Returns number of clusters
             size_t size() const {
-                return G.nr2();
+                return G.nrNodes2();
             }
 
             /// Returns the index of variable \a n
@@ -97,7 +97,7 @@ namespace dai {
 
             /// Returns \c true if cluster \a I is not contained in a larger cluster
             bool isMaximal( size_t I ) const {
-                DAI_DEBASSERT( I < G.nr2() );
+                DAI_DEBASSERT( I < G.nrNodes2() );
                 const VarSet & clI = clusters[I];
                 bool maximal = true;
                 // The following may not be optimal, since it may repeatedly test the same cluster *J
@@ -126,20 +126,20 @@ namespace dai {
                         size_t iter = find( vars.begin(), vars.end(), *n ) - vars.begin();
                         nbs.push_back( iter );
                         if( iter == vars.size() ) {
-                            G.add1();
+                            G.addNode1();
                             vars.push_back( *n );
                         }
                     }
-                    G.add2( nbs.begin(), nbs.end(), nbs.size() );
+                    G.addNode2( nbs.begin(), nbs.end(), nbs.size() );
                 }
             }
 
             /// Erases all clusters that are not maximal
             ClusterGraph& eraseNonMaximal() {
-                for( size_t I = 0; I < G.nr2(); ) {
+                for( size_t I = 0; I < G.nrNodes2(); ) {
                     if( !isMaximal(I) ) {
                         clusters.erase( clusters.begin() + I );
-                        G.erase2(I);
+                        G.eraseNode2(I);
                     } else
                         I++;
                 }
@@ -150,7 +150,7 @@ namespace dai {
             ClusterGraph& eraseSubsuming( size_t i ) {
                 while( G.nb1(i).size() ) {
                     clusters.erase( clusters.begin() + G.nb1(i)[0] );
-                    G.erase2( G.nb1(i)[0] );
+                    G.eraseNode2( G.nb1(i)[0] );
                 }
                 return *this;
             }

diff --git a/src/bipgraph.cpp b/src/bipgraph.cpp
index f7aaa97..30b8927 100644 (file)
--- a/src/bipgraph.cpp
+++ b/src/bipgraph.cpp
@@ -21,8 +21,8 @@ using namespace std;
 
 
 void BipartiteGraph::addEdge( size_t n1, size_t n2, bool check ) {
-    DAI_ASSERT( n1 < nr1() );
-    DAI_ASSERT( n2 < nr2() );
+    DAI_ASSERT( n1 < nrNodes1() );
+    DAI_ASSERT( n2 < nrNodes2() );
     bool exists = false;
     if( check ) {
         // Check whether the edge already exists
@@ -41,12 +41,12 @@ void BipartiteGraph::addEdge( size_t n1, size_t n2, bool check ) {
 }
 
 
-void BipartiteGraph::erase1( size_t n1 ) {
-    DAI_ASSERT( n1 < nr1() );
+void BipartiteGraph::eraseNode1( size_t n1 ) {
+    DAI_ASSERT( n1 < nrNodes1() );
     // 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 n2 = 0; n2 < nrNodes2(); n2++ ) {
         for( size_t iter = 0; iter < nb2(n2).size(); ) {
             Neighbor &m1 = nb2(n2, iter);
             if( m1.node == n1 ) {
@@ -67,12 +67,12 @@ void BipartiteGraph::erase1( size_t n1 ) {
 }
 
 
-void BipartiteGraph::erase2( size_t n2 ) {
-    DAI_ASSERT( n2 < nr2() );
+void BipartiteGraph::eraseNode2( size_t n2 ) {
+    DAI_ASSERT( n2 < nrNodes2() );
     // 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 n1 = 0; n1 < nrNodes1(); n1++ ) {
         for( size_t iter = 0; iter < nb1(n1).size(); ) {
             Neighbor &m2 = nb1(n1, iter);
             if( m2.node == n2 ) {
@@ -94,8 +94,8 @@ void BipartiteGraph::erase2( size_t n2 ) {
 
 
 void BipartiteGraph::eraseEdge( size_t n1, size_t n2 ) {
-    DAI_ASSERT( n1 < nr1() );
-    DAI_ASSERT( n2 < nr2() );
+    DAI_ASSERT( n1 < nrNodes1() );
+    DAI_ASSERT( n2 < nrNodes2() );
     size_t iter;
     // Search for edge among neighbors of n1
     for( iter = 0; iter < nb1(n1).size(); iter++ )
@@ -155,7 +155,7 @@ std::vector<size_t> BipartiteGraph::delta2( size_t n2, bool include ) const {
 
 
 bool BipartiteGraph::isConnected() const {
-    if( nr1() == 0 ) {
+    if( nrNodes1() == 0 ) {
         return true;
     } else {
         using namespace boost;
@@ -163,13 +163,13 @@ bool BipartiteGraph::isConnected() const {
         typedef pair<size_t, size_t> E;
 
         // Copy graph structure into boostGraph object
-        size_t N = nr1();
+        size_t N = nrNodes1();
         vector<E> edges;
         edges.reserve( nrEdges() );
-        for( size_t n1 = 0; n1 < nr1(); n1++ )
+        for( size_t n1 = 0; n1 < nrNodes1(); n1++ )
             foreach( const Neighbor &n2, nb1(n1) )
                 edges.push_back( E( n1, n2.node + N ) );
-        boostGraph g( edges.begin(), edges.end(), nr1() + nr2() );
+        boostGraph g( edges.begin(), edges.end(), nrNodes1() + nrNodes2() );
 
         // Construct connected components using Boost Graph Library
         std::vector<int> component( num_vertices( g ) );
@@ -177,8 +177,8 @@ bool BipartiteGraph::isConnected() const {
 
         return (num_comp == 1);
         /*
-        std::vector<bool> incomponent1( nr1(), false );
-        std::vector<bool> incomponent2( nr2(), false );
+        std::vector<bool> incomponent1( nrNodes1(), false );
+        std::vector<bool> incomponent2( nrNodes2(), false );
 
         incomponent1[0] = true;
         bool found_new_nodes;
@@ -186,7 +186,7 @@ bool BipartiteGraph::isConnected() const {
             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++ )
+            for( size_t n2 = 0; n2 < nrNodes2(); n2++ )
                 if( !incomponent2[n2] ) {
                     foreach( const Neighbor &n1, nb2(n2) ) {
                         if( incomponent1[n1] ) {
@@ -198,7 +198,7 @@ bool BipartiteGraph::isConnected() const {
                 }
 
             // For all nodes of type 1, check if they are connected with the (growing) component
-            for( size_t n1 = 0; n1 < nr1(); n1++ )
+            for( size_t n1 = 0; n1 < nrNodes1(); n1++ )
                 if( !incomponent1[n1] ) {
                     foreach( const Neighbor &n2, nb1(n1) ) {
                         if( incomponent2[n2] ) {
@@ -212,10 +212,10 @@ bool BipartiteGraph::isConnected() const {
 
         // Check if there are remaining nodes (not in the component)
         bool all_connected = true;
-        for( size_t n1 = 0; (n1 < nr1()) && all_connected; n1++ )
+        for( size_t n1 = 0; (n1 < nrNodes1()) && all_connected; n1++ )
             if( !incomponent1[n1] )
                 all_connected = false;
-        for( size_t n2 = 0; (n2 < nr2()) && all_connected; n2++ )
+        for( size_t n2 = 0; (n2 < nrNodes2()) && all_connected; n2++ )
             if( !incomponent2[n2] )
                 all_connected = false;
 
@@ -232,7 +232,7 @@ bool BipartiteGraph::isTree() const {
     size_t nr_1 = 0;
     size_t nr_2 = 0;
 
-    if( nr1() == 0 || nr2() == 0 )
+    if( nrNodes1() == 0 || nrNodes2() == 0 )
         return true;
     else {
         levelType newLevel;
@@ -284,7 +284,7 @@ bool BipartiteGraph::isTree() const {
             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 )
+        if( nr_1 == nrNodes1() && nr_2 == nrNodes2() && !foundCycle )
             return true;
         else
             return false;
@@ -296,12 +296,12 @@ void BipartiteGraph::printDot( 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++ )
+    for( size_t n1 = 0; n1 < nrNodes1(); 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++ )
+    for( size_t n2 = 0; n2 < nrNodes2(); n2++ )
         os << "\ty" << n2 << ";" << endl;
-    for( size_t n1 = 0; n1 < nr1(); n1++ )
+    for( size_t n1 = 0; n1 < nrNodes1(); n1++ )
         foreach( const Neighbor &n2, nb1(n1) )
             os << "\tx" << n1 << " -- y" << n2 << ";" << endl;
     os << "}" << endl;
@@ -309,8 +309,8 @@ void BipartiteGraph::printDot( std::ostream& os ) const {
 
 
 void BipartiteGraph::checkConsistency() const {
-    size_t N1 = nr1();
-    size_t N2 = nr2();
+    size_t N1 = nrNodes1();
+    size_t N2 = nrNodes2();
     for( size_t n1 = 0; n1 < N1; n1++ ) {
         size_t iter = 0;
         foreach( const Neighbor &n2, nb1(n1) ) {