Forgot to update version and date in last commit
[libdai.git] / src / bipgraph.cpp
index d27b8c0..0288fe8 100644 (file)
@@ -1,22 +1,12 @@
-/*  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.
-
-    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
-*/
+/*  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-2009  Joris Mooij  [joris dot mooij at libdai dot org]
+ *  Copyright (C) 2006-2007  Radboud University Nijmegen, The Netherlands
+ */
 
 
 #include <dai/bipgraph.h>
@@ -28,8 +18,29 @@ namespace dai {
 using namespace std;
 
 
+void BipartiteGraph::addEdge( size_t n1, size_t n2, bool check ) {
+    DAI_ASSERT( n1 < nr1() );
+    DAI_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 );
+    }
+}
+
+
 void BipartiteGraph::erase1( size_t n1 ) {
-    assert( n1 < nr1() );
+    DAI_ASSERT( n1 < nr1() );
     // Erase neighbor entry of node n1
     _nb1.erase( _nb1.begin() + n1 );
     // Adjust neighbor entries of nodes of type 2
@@ -55,7 +66,7 @@ void BipartiteGraph::erase1( size_t n1 ) {
 
 
 void BipartiteGraph::erase2( size_t n2 ) {
-    assert( n2 < nr2() );
+    DAI_ASSERT( n2 < nr2() );
     // Erase neighbor entry of node n2
     _nb2.erase( _nb2.begin() + n2 );
     // Adjust neighbor entries of nodes of type 1
@@ -80,6 +91,39 @@ void BipartiteGraph::erase2( size_t n2 ) {
 }
 
 
+void BipartiteGraph::eraseEdge( size_t n1, size_t n2 ) {
+    DAI_ASSERT( n1 < nr1() );
+    DAI_ASSERT( n2 < nr2() );
+    size_t iter;
+    // Search for edge among neighbors of n1
+    for( iter = 0; iter < nb1(n1).size(); iter++ )
+        if( nb1(n1, iter).node == n2 ) {
+            // Remove it
+            nb1(n1).erase( nb1(n1).begin() + iter );
+            break;
+        }
+    // Change the iter and dual values of the subsequent neighbors
+    for( ; iter < nb1(n1).size(); iter++ ) {
+        Neighbor &m2 = nb1( n1, iter );
+        m2.iter = iter;
+        nb2( m2.node, m2.dual ).dual = iter;
+    }
+    // Search for edge among neighbors of n2
+    for( iter = 0; iter < nb2(n2).size(); iter++ )
+        if( nb2(n2, iter).node == n1 ) {
+            // Remove it
+            nb2(n2).erase( nb2(n2).begin() + iter );
+            break;
+        }
+    // Change the iter and node values of the subsequent neighbors
+    for( ; iter < nb2(n2).size(); iter++ ) {
+        Neighbor &m1 = nb2( n2, iter );
+        m1.iter = iter;
+        nb1( m1.node, m1.dual ).dual = iter;
+    }
+}
+
+
 std::vector<size_t> BipartiteGraph::delta1( size_t n1, bool include ) const {
     // get all second-order neighbors
     std::vector<size_t> result;
@@ -109,6 +153,9 @@ std::vector<size_t> BipartiteGraph::delta2( size_t n2, bool include ) const {
 
 
 bool BipartiteGraph::isConnected() const {
+    // TODO: use BGL, like:
+    // std::vector<int> component( num_vertices( g ) );
+    // int num_comp = connected_components( g, make_iterator_property_map(component.begin(), get(vertex_index, g)) );
     if( nr1() == 0 ) {
         return true;
     } else {
@@ -213,7 +260,7 @@ bool BipartiteGraph::isTree() const {
                     }
                     if( foundCycle )
                         break;
-                } 
+                }
             }
             levels.push_back( newLevel );
             nr_1 += newLevel.ind1.size();
@@ -243,26 +290,26 @@ void BipartiteGraph::printDot( std::ostream& os ) const {
 }
 
 
-void BipartiteGraph::check() const {
+void BipartiteGraph::checkConsistency() const {
     size_t N1 = nr1();
     size_t N2 = nr2();
     for( size_t n1 = 0; n1 < N1; n1++ ) {
         size_t iter = 0;
         foreach( const Neighbor &n2, nb1(n1) ) {
-            assert( n2.iter == iter );
-            assert( n2.node < N2 );
-            assert( n2.dual < nb2(n2).size() );
-            assert( nb2(n2, n2.dual) == n1 );
+            DAI_ASSERT( n2.iter == iter );
+            DAI_ASSERT( n2.node < N2 );
+            DAI_ASSERT( n2.dual < nb2(n2).size() );
+            DAI_ASSERT( nb2(n2, n2.dual) == n1 );
             iter++;
         }
     }
     for( size_t n2 = 0; n2 < N2; n2++ ) {
         size_t iter = 0;
         foreach( const Neighbor &n1, nb2(n2) ) {
-            assert( n1.iter == iter );
-            assert( n1.node < N1 );
-            assert( n1.dual < nb1(n1).size() );
-            assert( nb1(n1, n1.dual) == n2 );
+            DAI_ASSERT( n1.iter == iter );
+            DAI_ASSERT( n1.node < N1 );
+            DAI_ASSERT( n1.dual < nb1(n1).size() );
+            DAI_ASSERT( nb1(n1, n1.dual) == n2 );
             iter++;
         }
     }