Optimized BipartiteGraph::isConnected() by using Boost Graph Library implementation
authorJoris Mooij <joris.mooij@tuebingen.mpg.de>
Tue, 12 Jan 2010 12:45:41 +0000 (13:45 +0100)
committerJoris Mooij <joris.mooij@tuebingen.mpg.de>
Tue, 12 Jan 2010 12:45:41 +0000 (13:45 +0100)
ChangeLog
include/dai/bipgraph.h
src/bipgraph.cpp

index 80e60ee..38505d7 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,4 @@
+* Optimized BipartiteGraph::isConnected() by using Boost Graph Library implementation
 * Strengthened convergence criteria of various algorithms
 * Implemented FBP::logZ()
 * Fixed bug in HAK for trivial region graphs (with only one outer region
index dfb0c50..4128339 100644 (file)
@@ -153,7 +153,7 @@ class BipartiteGraph {
          *  \param end Points just beyond the last edge.
          */
         template<typename EdgeInputIterator>
-        BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ) {
+        BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1(), _nb2() {
             construct( nr1, nr2, begin, end );
         }
     //@}
@@ -317,8 +317,6 @@ class BipartiteGraph {
         std::vector<size_t> delta2( size_t n2, bool include = false ) const;
 
         /// Returns true if the graph is connected
-        /** \todo Should be optimized by invoking boost::graph library
-         */
         bool isConnected() const;
 
         /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
index 0288fe8..f7aaa97 100644 (file)
@@ -10,6 +10,8 @@
 
 
 #include <dai/bipgraph.h>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/connected_components.hpp>
 
 
 namespace dai {
@@ -153,12 +155,28 @@ 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 {
+        using namespace boost;
+        typedef adjacency_list< vecS, vecS, undirectedS, property<vertex_distance_t, int> > boostGraph;
+        typedef pair<size_t, size_t> E;
+
+        // Copy graph structure into boostGraph object
+        size_t N = nr1();
+        vector<E> edges;
+        edges.reserve( nrEdges() );
+        for( size_t n1 = 0; n1 < nr1(); n1++ )
+            foreach( const Neighbor &n2, nb1(n1) )
+                edges.push_back( E( n1, n2.node + N ) );
+        boostGraph g( edges.begin(), edges.end(), nr1() + nr2() );
+
+        // Construct connected components using Boost Graph Library
+        std::vector<int> component( num_vertices( g ) );
+        int num_comp = connected_components( g, make_iterator_property_map(component.begin(), get(vertex_index, g)) );
+
+        return (num_comp == 1);
+        /*
         std::vector<bool> incomponent1( nr1(), false );
         std::vector<bool> incomponent2( nr2(), false );
 
@@ -201,7 +219,7 @@ bool BipartiteGraph::isConnected() const {
             if( !incomponent2[n2] )
                 all_connected = false;
 
-        return all_connected;
+        return all_connected;*/
     }
 }