- Solved the proliferation of type checks for different DAI_ENUM's in properties.cpp
[libdai.git] / include / dai / bipgraph.h
index c9701ef..b385476 100644 (file)
@@ -36,12 +36,13 @@ namespace dai {
 /// A BipartiteGraph represents the neighborhood structure of nodes in a 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.
+ *  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:
+ *  each node has a vector of Neighbor entries, which is also known as a Neighbors type.
  */
 class BipartiteGraph {
     public:
-        /// A Neighbor describes a neighboring node of some other node.
+        /// A Neighbor describes a neighboring node of some other node in a BipartiteGraph.
         /** Iterating over all neighbors of node n1 of type 1 can be done in the following way:
          *  \code
          *      foreach( const BipartiteGraph::Neighbor &n2, nb1(n1) ) {
@@ -60,7 +61,7 @@ class BipartiteGraph {
             unsigned node;
             /// Contains the "dual" iter
             unsigned dual;
-            /// Cast to unsigned returns node
+            /// Cast to unsigned returns node member
             operator unsigned () const { return node; }
             /// Default constructor
             Neighbor() {}
@@ -71,7 +72,7 @@ class BipartiteGraph {
         /// Neighbors is a vector of Neighbor entries; each node has an associated Neighbors variable, which describes its neighbors.
         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.
+        /// 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. It depends on the context whether the first node (with index a) is of type 1 or of type 2.
         typedef std::pair<size_t,size_t> Edge;
 
     private:
@@ -187,7 +188,7 @@ class BipartiteGraph {
         /// Returns number of nodes of type 2
         size_t nr2() const { return _nb2.size(); }
         
-        /// Calculates the number of edges
+        /// Calculates the number of edges, using O(nr1()) time
         size_t nrEdges() const {
             size_t sum = 0;
             for( size_t i1 = 0; i1 < nr1(); i1++ )
@@ -241,12 +242,35 @@ class BipartiteGraph {
             _nb2.push_back( nbs2new );
         }
 
-        /// Remove node of type 1 and all incident edges.
+        /// Remove node n1 of type 1 and all incident edges.
         void erase1( size_t n1 );
 
-        /// Remove node of type 2 and all incident edges.
+        /// Remove node n2 of type 2 and all incident edges.
         void erase2( size_t n2 );
 
+        /// Add edge between node n1 of type 1 and node n2 of type 2.
+        /** If check == true, only adds the edge if it does not exist already.
+         */
+        void addEdge( size_t n1, size_t n2, bool check = true ) {
+            assert( n1 < nr1() );
+            assert( n2 < nr2() );
+            bool exists = false;
+            if( check ) {
+                // Check whether the edge already exists
+                foreach( const Neighbor &nb2, nb1(n1) )
+                    if( nb2 == n2 ) {
+                        exists = true;
+                        break;
+                    }
+            }
+            if( !exists ) { // Add edge
+                Neighbor nb_1( _nb1[n1].size(), n2, _nb2[n2].size() );
+                Neighbor nb_2( nb_1.dual, n1, nb_1.iter );
+                _nb1[n1].push_back( nb_1 );
+                _nb2[n2].push_back( nb_2 );
+            }
+        }
+
         /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
         /** If include == true, include n1 itself, otherwise exclude n1.
          */
@@ -282,11 +306,11 @@ void BipartiteGraph::create( size_t nr1, size_t nr2, EdgeInputIterator begin, Ed
     _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 );
+#ifdef DAI_DEBUG
+        addEdge( e->first, e->second, true );
+#else
+        addEdge( e->first, e->second, false );
+#endif
     }
 }