Added DAG class and various minor improvements
[libdai.git] / src / graph.cpp
index 501fa75..3667f09 100644 (file)
@@ -10,9 +10,6 @@
 
 
 #include <dai/graph.h>
-#include <dai/weightedgraph.h>
-#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/connected_components.hpp>
 
 
 namespace dai {
@@ -21,7 +18,7 @@ namespace dai {
 using namespace std;
 
 
-void GraphAL::addEdge( size_t n1, size_t n2, bool check ) {
+GraphAL& GraphAL::addEdge( size_t n1, size_t n2, bool check ) {
     DAI_ASSERT( n1 < nrNodes() );
     DAI_ASSERT( n2 < nrNodes() );
     bool exists = false;
@@ -39,6 +36,7 @@ void GraphAL::addEdge( size_t n1, size_t n2, bool check ) {
         nb(n1).push_back( nb_1 );
         nb(n2).push_back( nb_2 );
     }
+    return *this;
 }
 
 
@@ -53,13 +51,10 @@ void GraphAL::eraseNode( size_t n ) {
             if( m.node == n ) {
                 // delete this entry, because it points to the deleted node
                 nb(n2).erase( nb(n2).begin() + iter );
-            } else if( m.node > n ) {
-                // update this entry and the corresponding dual of the neighboring node
-                m.node--;
-                nb( m.node, m.dual ).dual = iter;
-                m.iter = iter++;
             } else {
                 // update this entry and the corresponding dual of the neighboring node
+                if( m.node > n ) 
+                    m.node--;
                 nb( m.node, m.dual ).dual = iter;
                 m.iter = iter++;
             }
@@ -101,6 +96,14 @@ void GraphAL::eraseEdge( size_t n1, size_t n2 ) {
 }
 
 
+SmallSet<size_t> GraphAL::nbSet( size_t n ) const {
+    SmallSet<size_t> result;
+    foreach( const Neighbor &m, nb(n) )
+        result |= m;
+    return result;
+}
+
+
 bool GraphAL::isConnected() const {
     if( nrNodes() == 0 ) {
         return true;
@@ -227,16 +230,6 @@ void GraphAL::checkConsistency() const {
             iter++;
         }
     }
-    for( size_t n2 = 0; n2 < N; n2++ ) {
-        size_t iter = 0;
-        foreach( const Neighbor &n1, nb(n2) ) {
-            DAI_ASSERT( n1.iter == iter );
-            DAI_ASSERT( n1.node < N );
-            DAI_ASSERT( n1.dual < nb(n1).size() );
-            DAI_ASSERT( nb(n1, n1.dual) == n2 );
-            iter++;
-        }
-    }
 }