New git HEAD version
[libdai.git] / src / graph.cpp
index 034f269..ca7fd3a 100644 (file)
@@ -1,18 +1,12 @@
 /*  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-2011, The libDAI authors. All rights reserved.
  *
- *  Copyright (C) 2006-2010  Joris Mooij  [joris dot mooij at libdai dot org]
- *  Copyright (C) 2006-2007  Radboud University Nijmegen, The Netherlands
+ *  Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
  */
 
 
 #include <dai/graph.h>
-#include <dai/weightedgraph.h>
-#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/connected_components.hpp>
 
 
 namespace dai {
@@ -21,13 +15,13 @@ 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;
     if( check ) {
         // Check whether the edge already exists
-        foreach( const Neighbor &n, nb(n1) )
+        bforeach( const Neighbor &n, nb(n1) )
             if( n == n2 ) {
                 exists = true;
                 break;
@@ -39,6 +33,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,15 +48,12 @@ 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 ) {
+            } else {
                 // update this entry and the corresponding dual of the neighboring node
-                m.iter = iter;
-                m.node--;
+                if( m.node > n ) 
+                    m.node--;
                 nb( m.node, m.dual ).dual = iter;
-                iter++;
-            } else {
-                // skip
-                iter++;
+                m.iter = iter++;
             }
         }
     }
@@ -101,6 +93,14 @@ void GraphAL::eraseEdge( size_t n1, size_t n2 ) {
 }
 
 
+SmallSet<size_t> GraphAL::nbSet( size_t n ) const {
+    SmallSet<size_t> result;
+    bforeach( const Neighbor &m, nb(n) )
+        result |= m;
+    return result;
+}
+
+
 bool GraphAL::isConnected() const {
     if( nrNodes() == 0 ) {
         return true;
@@ -115,7 +115,7 @@ bool GraphAL::isConnected() const {
             // For all nodes, check if they are connected with the (growing) component
             for( size_t n1 = 0; n1 < nrNodes(); n1++ )
                 if( !incomponent[n1] ) {
-                    foreach( const Neighbor &n2, nb(n1) ) {
+                    bforeach( const Neighbor &n2, nb(n1) ) {
                         if( incomponent[n2] ) {
                             found_new_nodes = true;
                             incomponent[n1] = true;
@@ -142,7 +142,7 @@ bool GraphAL::isConnected() const {
         vector<E> edges;
         edges.reserve( nrEdges() );
         for( size_t n1 = 0; n1 < nrNodes(); n1++ )
-            foreach( const Neighbor &n2, nb(n1) )
+            bforeach( const Neighbor &n2, nb(n1) )
                 if( n1 < n2 )
                     edges.push_back( E( n1, n2 ) );
         boostGraphAL g( edges.begin(), edges.end(), nrNodes() );
@@ -175,7 +175,7 @@ bool GraphAL::isTree() const {
             // (without backtracking), aborting if a cycle is detected
             for( size_t e = 0; e < prevLevel.size(); e++ ) {
                 size_t n2 = prevLevel[e].first; // for all nodes n2 in the previous level
-                foreach( const Neighbor &n1, nb(n2) ) { // for all neighbors n1 of n2
+                bforeach( const Neighbor &n1, nb(n2) ) { // for all neighbors n1 of n2
                     if( n1 != prevLevel[e].second ) { // no backtracking allowed
                         for( size_t l = 0; l < levels.size() && !foundCycle; l++ )
                             for( size_t f = 0; f < levels[l].size() && !foundCycle; f++ )
@@ -203,12 +203,12 @@ bool GraphAL::isTree() const {
 
 
 void GraphAL::printDot( std::ostream& os ) const {
-    os << "graph G {" << endl;
+    os << "graph GraphAL {" << endl;
     os << "node[shape=circle,width=0.4,fixedsize=true];" << endl;
     for( size_t n = 0; n < nrNodes(); n++ )
         os << "\tx" << n << ";" << endl;
     for( size_t n1 = 0; n1 < nrNodes(); n1++ )
-        foreach( const Neighbor &n2, nb(n1) )
+        bforeach( const Neighbor &n2, nb(n1) )
             if( n1 < n2 )
                 os << "\tx" << n1 << " -- x" << n2 << ";" << endl;
     os << "}" << endl;
@@ -219,7 +219,7 @@ void GraphAL::checkConsistency() const {
     size_t N = nrNodes();
     for( size_t n1 = 0; n1 < N; n1++ ) {
         size_t iter = 0;
-        foreach( const Neighbor &n2, nb(n1) ) {
+        bforeach( const Neighbor &n2, nb(n1) ) {
             DAI_ASSERT( n2.iter == iter );
             DAI_ASSERT( n2.node < N );
             DAI_ASSERT( n2.dual < nb(n2).size() );
@@ -227,16 +227,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++;
-        }
-    }
 }
 
 
@@ -322,7 +312,7 @@ GraphAL createGraphRegular( size_t N, size_t d ) {
             G = GraphAL( N );
             bool finished = false;
             while( !finished ) {
-                random_shuffle( U.begin(), U.end() );
+                random_shuffle( U.begin(), U.end(), rnd );
                 size_t i1, i2;
                 bool suit_pair_found = false;
                 for( i1 = 0; i1 < U.size()-1 && !suit_pair_found; i1++ )