Improved BipartiteGraph code, BipartiteGraph and Graph unit tests
authorJoris Mooij <joris.mooij@tuebingen.mpg.de>
Tue, 23 Mar 2010 08:53:41 +0000 (09:53 +0100)
committerJoris Mooij <joris.mooij@tuebingen.mpg.de>
Tue, 23 Mar 2010 08:53:41 +0000 (09:53 +0100)
- Added BipartiteGraph::hasEdge()
- Added BipartiteGraph::findNb1()
- Added BipartiteGraph::findNb2()
- BipartiteGraph::delta1() and BipartiteGraph::delta2() now
  return a SmallSet<size_t> instead of a vector<size_t>
- The sizeHint argument of the iterator constructor
    SmallSet::SmallSet( TIterator begin, TIterator end, size_t sizeHint=0 )
  no longer has a default value in order to avoid confusion with the
    SmallSet::SmallSet( const T &t1, const T &t2 )
  constructor.
- Improved BipartiteGraph unit test cases
- Improved Graph unit test cases

ChangeLog
include/dai/bipgraph.h
include/dai/graph.h
include/dai/smallset.h
src/bipgraph.cpp
src/clustergraph.cpp
tests/unit/bipgraph.cpp
tests/unit/graph.cpp
tests/unit/smallset.cpp

index 11b2ceb..5e2fe2d 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -5,6 +5,11 @@ git HEAD
   - Fixed bug in BipartiteGraph::eraseNode1()
   - Fixed bug in BipartiteGraph::eraseNode2()
   - Fixed bug in BipartiteGraph::isTree()
+  - Added BipartiteGraph::hasEdge()
+  - Added BipartiteGraph::findNb1()
+  - Added BipartiteGraph::findNb2()
+  - BipartiteGraph::delta1() and BipartiteGraph::delta2() now 
+    return a SmallSet<size_t> instead of a vector<size_t>
 * Improved GraphAL code:
   - Fixed bug in GraphAL::nrEdges()
   - Fixed bug in GraphAL::addEdge()
@@ -14,6 +19,12 @@ git HEAD
   - Fixed bug in createGraphGrid3D()
   - Fixed bug in createGraphRegular()
   - Added GraphAL::hasEdge(size_t,size_t)
+* Improved SmallSet code:
+  - The sizeHint argument of the iterator constructor
+     SmallSet::SmallSet( TIterator begin, TIterator end, size_t sizeHint=0 )
+    no longer has a default value in order to avoid confusion with the
+     SmallSet::SmallSet( const T &t1, const T &t2 )
+    constructor.
 * Removed RandomDRegularGraph()
 * Compressed Makefile
 * Added unit tests for Var, SmallSet, VarSet, Graph, BipartiteGraph
index 29c8a1a..f51c0fd 100644 (file)
@@ -21,6 +21,7 @@
 #include <vector>
 #include <algorithm>
 #include <dai/util.h>
+#include <dai/smallset.h>
 #include <dai/exceptions.h>
 
 
@@ -307,15 +308,55 @@ class BipartiteGraph {
             return sum;
         }
 
+        /// Returns true if the graph contains an edge between node \a n1 of type 1 and node \a n2 of type 2.
+        /** \note The time complexity is linear in the number of neighbors of \a n1 or \a n2
+         */
+        bool hasEdge( size_t n1, size_t n2 ) {
+            if( nb1(n1).size() < nb2(n2).size() ) {
+                for( size_t _n2 = 0; _n2 < nb1(n1).size(); _n2++ )
+                    if( nb1( n1, _n2 ) == n2 )
+                        return true;
+            } else {
+                for( size_t _n1 = 0; _n1 < nb2(n2).size(); _n1++ )
+                    if( nb2( n2, _n1 ) == n1 )
+                        return true;
+            }
+            return false;
+        }
+
+        /// Returns the index of a given node \a n2 of type 2 amongst the neighbors of node \a n1 of type 1
+        /** \note The time complexity is linear in the number of neighbors of \a n1
+         *  \throw OBJECT_NOT_FOUND if \a n2 is not a neighbor of \a n1
+         */
+        size_t findNb1( size_t n1, size_t n2 ) {
+            for( size_t _n2 = 0; _n2 < nb1(n1).size(); _n2++ )
+                if( nb1( n1, _n2 ) == n2 )
+                    return _n2;
+            DAI_THROW(OBJECT_NOT_FOUND);
+            return nb1(n1).size();
+        }
+
+        /// Returns the index of a given node \a n1 of type 1 amongst the neighbors of node \a n2 of type 2
+        /** \note The time complexity is linear in the number of neighbors of \a n2
+         *  \throw OBJECT_NOT_FOUND if \a n1 is not a neighbor of \a n2
+         */
+        size_t findNb2( size_t n1, size_t n2 ) {
+            for( size_t _n1 = 0; _n1 < nb2(n2).size(); _n1++ )
+                if( nb2( n2, _n1 ) == n1 )
+                    return _n1;
+            DAI_THROW(OBJECT_NOT_FOUND);
+            return nb2(n2).size();
+        }
+
         /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n1 of type 1.
         /** If \a include == \c true, includes \a n1 itself, otherwise excludes \a n1.
          */
-        std::vector<size_t> delta1( size_t n1, bool include = false ) const;
+        SmallSet<size_t> delta1( size_t n1, bool include = false ) const;
 
         /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n2 of type 2.
         /** If \a include == \c true, includes \a n2 itself, otherwise excludes \a n2.
          */
-        std::vector<size_t> delta2( size_t n2, bool include = false ) const;
+        SmallSet<size_t> delta2( size_t n2, bool include = false ) const;
 
         /// Returns true if the graph is connected
         bool isConnected() const;
index 3526ef6..02da765 100644 (file)
@@ -233,12 +233,18 @@ class GraphAL {
         }
 
         /// Returns true if the graph contains an edge between nodes \a n1 and \a n2
-        /** \note The time complexity is linear in the number of neighbors of \a n1
+        /** \note The time complexity is linear in the number of neighbors of \a n1 or \a n2
          */
         bool hasEdge( size_t n1, size_t n2 ) {
-            for( size_t _n2 = 0; _n2 < nb(n1).size(); _n2++ )
-                if( nb( n1, _n2 ) == n2 )
-                    return true;
+            if( nb(n1).size() < nb(n2).size() ) {
+                for( size_t _n2 = 0; _n2 < nb(n1).size(); _n2++ )
+                    if( nb( n1, _n2 ) == n2 )
+                        return true;
+            } else {
+                for( size_t _n1 = 0; _n1 < nb(n2).size(); _n1++ )
+                    if( nb( n2, _n1 ) == n1 )
+                        return true;
+            }
             return false;
         }
 
index ae8cdd0..dc49a90 100644 (file)
@@ -67,7 +67,7 @@ class SmallSet {
          *  \param sizeHint For efficiency, the number of elements can be speficied by \a sizeHint.
          */
         template <typename TIterator>
-        SmallSet( TIterator begin, TIterator end, size_t sizeHint=0 ) {
+        SmallSet( TIterator begin, TIterator end, size_t sizeHint ) {
             _elements.reserve( sizeHint );
             _elements.insert( _elements.begin(), begin, end );
             std::sort( _elements.begin(), _elements.end() );
index d8fdab5..4389b45 100644 (file)
@@ -124,30 +124,24 @@ void BipartiteGraph::eraseEdge( size_t n1, size_t n2 ) {
 }
 
 
-std::vector<size_t> BipartiteGraph::delta1( size_t n1, bool include ) const {
+SmallSet<size_t> BipartiteGraph::delta1( size_t n1, bool include ) const {
     // get all second-order neighbors
-    std::vector<size_t> result;
+    SmallSet<size_t> result;
     foreach( const Neighbor &n2, nb1(n1) )
         foreach( const Neighbor &m1, nb2(n2) )
             if( include || (m1 != n1) )
-                result.push_back( m1 );
-    // remove duplicates
-    std::vector<size_t>::iterator it = std::unique( result.begin(), result.end() );
-    result.erase( it, result.end() );
+                result |= m1;
     return result;
 }
 
 
-std::vector<size_t> BipartiteGraph::delta2( size_t n2, bool include ) const {
+SmallSet<size_t> BipartiteGraph::delta2( size_t n2, bool include ) const {
     // store all second-order neighbors
-    std::vector<size_t> result;
+    SmallSet<size_t> result;
     foreach( const Neighbor &n1, nb2(n2) )
         foreach( const Neighbor &m2, nb1(n1) )
             if( include || (m2 != n2) )
-                result.push_back( m2 );
-    // remove duplicates
-    std::vector<size_t>::iterator it = std::unique( result.begin(), result.end() );
-    result.erase( it, result.end() );
+                result |= m2;
     return result;
 }
 
index 1b6a06d..0953918 100644 (file)
@@ -65,49 +65,50 @@ size_t greedyVariableElimination::operator()( const ClusterGraph &cl, const std:
 
 
 size_t eliminationCost_MinNeighbors( const ClusterGraph &cl, size_t i ) {
-    std::vector<size_t> id_n = cl.G.delta1( i );
-    return id_n.size();
+    return cl.G.delta1( i ).size();
 }
 
 
 size_t eliminationCost_MinWeight( const ClusterGraph &cl, size_t i ) {
-    std::vector<size_t> id_n = cl.G.delta1( i );
+    SmallSet<size_t> id_n = cl.G.delta1( i );
     
     size_t cost = 1;
-    for( size_t _i = 0; _i < id_n.size(); _i++ )
-        cost *= cl.vars[id_n[_i]].states();
+    for( SmallSet<size_t>::const_iterator it = id_n.begin(); it != id_n.end(); it++ )
+        cost *= cl.vars[*it].states();
 
     return cost;
 }
 
 
 size_t eliminationCost_MinFill( const ClusterGraph &cl, size_t i ) {
-    std::vector<size_t> id_n = cl.G.delta1( i );
+    SmallSet<size_t> id_n = cl.G.delta1( i );
 
     size_t cost = 0;
     // for each unordered pair {i1,i2} adjacent to n
-    for( size_t _i1 = 0; _i1 < id_n.size(); _i1++ )
-        for( size_t _i2 = _i1 + 1; _i2 < id_n.size(); _i2++ ) {
-            // if i1 and i2 are not adjacent, eliminating n would make them adjacent
-            if( !cl.adj(id_n[_i1], id_n[_i2]) )
-                cost++;
-        }
+    for( SmallSet<size_t>::const_iterator it1 = id_n.begin(); it1 != id_n.end(); it1++ )
+        for( SmallSet<size_t>::const_iterator it2 = it1; it2 != id_n.end(); it2++ )
+            if( it1 != it2 ) {
+                // if i1 and i2 are not adjacent, eliminating n would make them adjacent
+                if( !cl.adj(*it1, *it2) )
+                    cost++;
+            }
 
     return cost;
 }
 
 
 size_t eliminationCost_WeightedMinFill( const ClusterGraph &cl, size_t i ) {
-    std::vector<size_t> id_n = cl.G.delta1( i );
+    SmallSet<size_t> id_n = cl.G.delta1( i );
 
     size_t cost = 0;
     // for each unordered pair {i1,i2} adjacent to n
-    for( size_t _i1 = 0; _i1 < id_n.size(); _i1++ )
-        for( size_t _i2 = _i1 + 1; _i2 < id_n.size(); _i2++ ) {
-            // if i1 and i2 are not adjacent, eliminating n would make them adjacent
-            if( !cl.adj(id_n[_i1], id_n[_i2]) )
-                cost += cl.vars[id_n[_i1]].states() * cl.vars[id_n[_i2]].states();
-        }
+    for( SmallSet<size_t>::const_iterator it1 = id_n.begin(); it1 != id_n.end(); it1++ )
+        for( SmallSet<size_t>::const_iterator it2 = it1; it2 != id_n.end(); it2++ )
+            if( it1 != it2 ) {
+                // if i1 and i2 are not adjacent, eliminating n would make them adjacent
+                if( !cl.adj(*it1, *it2) )
+                    cost += cl.vars[*it1].states() * cl.vars[*it2].states();
+            }
 
     return cost;
 }
index 1c5d9f3..2456ad4 100644 (file)
@@ -227,29 +227,124 @@ BOOST_AUTO_TEST_CASE( AddEraseTest ) {
 }
 
 
+BOOST_AUTO_TEST_CASE( RandomAddEraseTest ) {
+    // check adding and erasing nodes and edges randomly
+    BipartiteGraph G;
+    for( size_t maxN1 = 2; maxN1 < 10; maxN1++ )
+        for( size_t maxN2 = 2; maxN2 < 10; maxN2++ )
+            for( size_t repeats = 0; repeats < 100000; repeats++ ) {
+                size_t action = rnd( 5 );
+                size_t N1 = G.nrNodes1();
+                size_t N2 = G.nrNodes2();
+                size_t M = G.nrEdges();
+                size_t maxM = N1 * N2;
+                if( action == 0 ) {
+                    // add node
+                    if( rnd( 2 ) == 0 ) {
+                        // add node of type 1
+                        if( N1 < maxN1 )
+                            G.addNode1();
+                    } else {
+                        // add node of type 2
+                        if( N2 < maxN2 )
+                            G.addNode2();
+                    }
+                } else if( action == 1 ) {
+                    // erase node
+                    if( rnd( 2 ) == 0 ) {
+                        // erase node of type 1
+                        if( N1 > 0 )
+                            G.eraseNode1( rnd( N1 ) );
+                    } else {
+                        // erase node of type 2
+                        if( N2 > 0 )
+                            G.eraseNode2( rnd( N2 ) );
+                    }
+                } else if( action == 2 || action == 3 ) {
+                    // add edge
+                    if( N1 >= 1 && N2 >= 1 && M < maxM ) {
+                        size_t n1 = 0;
+                        size_t n2 = 0;
+                        if( rnd( 2 ) == 0 ) {
+                            do {
+                                n1 = rnd( N1 );
+                            } while( G.nb1(n1).size() >= N2 );
+                            do {
+                                n2 = rnd( N2 );
+                            } while( G.hasEdge( n1, n2 ) );
+                        } else {
+                            do {
+                                n2 = rnd( N2 );
+                            } while( G.nb2(n2).size() >= N1 );
+                            do {
+                                n1 = rnd( N1 );
+                            } while( G.hasEdge( n1, n2 ) );
+                        }
+                        G.addEdge( n1, n2 );
+                    }
+                } else if( action == 4 ) {
+                    // erase edge
+                    if( M > 0 ) {
+                        size_t n1 = 0;
+                        size_t n2 = 0;
+                        if( rnd( 2 ) == 0 ) {
+                            do {
+                                n1 = rnd( N1 );
+                            } while( G.nb1(n1).size() == 0 );
+                            do {
+                                n2 = rnd( N2 );
+                            } while( !G.hasEdge( n1, n2 ) );
+                        } else {
+                            do {
+                                n2 = rnd( N2 );
+                            } while( G.nb2(n2).size() == 0 );
+                            do {
+                                n1 = rnd( N1 );
+                            } while( !G.hasEdge( n1, n2 ) );
+                        }
+                        G.eraseEdge( n1, n2 );
+                    }
+                }
+                G.checkConsistency();
+            }
+}
+
+
 BOOST_AUTO_TEST_CASE( QueriesTest ) {
     // check queries which have not been tested in another test case
     typedef BipartiteGraph::Edge Edge;
     std::vector<Edge> edges;
-    edges.push_back( Edge( 0, 0 ) );
     edges.push_back( Edge( 0, 1 ) );
     edges.push_back( Edge( 1, 1 ) );
+    edges.push_back( Edge( 0, 0 ) );
     BipartiteGraph G( 3, 2, edges.begin(), edges.end() );
     G.checkConsistency();
-    std::vector<size_t> v;
-    std::vector<size_t> v0; v0.push_back(0);
-    std::vector<size_t> v1; v1.push_back(1);
-    std::vector<size_t> v01; v01.push_back(0); v01.push_back(1);
-    BOOST_CHECK( G.delta1( 0, true ) == v01 );
-    BOOST_CHECK( G.delta1( 1, true ) == v01 );
-    BOOST_CHECK( G.delta1( 2, true ) == v );
-    BOOST_CHECK( G.delta2( 0, true ) == v01 );
-    BOOST_CHECK( G.delta2( 1, true ) == v01 );
-    BOOST_CHECK( G.delta1( 0, false ) == v1 );
-    BOOST_CHECK( G.delta1( 1, false ) == v0 );
-    BOOST_CHECK( G.delta1( 2, false ) == v );
-    BOOST_CHECK( G.delta2( 0, false ) == v1 );
-    BOOST_CHECK( G.delta2( 1, false ) == v0 );
+    SmallSet<size_t> v;
+    SmallSet<size_t> v0( 0 );
+    SmallSet<size_t> v1( 1 );
+    SmallSet<size_t> v01( 0, 1 );
+    BOOST_CHECK_EQUAL( G.delta1( 0, true ), v01 );
+    BOOST_CHECK_EQUAL( G.delta1( 1, true ), v01 );
+    BOOST_CHECK_EQUAL( G.delta1( 2, true ), v );
+    BOOST_CHECK_EQUAL( G.delta2( 0, true ), v01 );
+    BOOST_CHECK_EQUAL( G.delta2( 1, true ), v01 );
+    BOOST_CHECK_EQUAL( G.delta1( 0, false ), v1 );
+    BOOST_CHECK_EQUAL( G.delta1( 1, false ), v0 );
+    BOOST_CHECK_EQUAL( G.delta1( 2, false ), v );
+    BOOST_CHECK_EQUAL( G.delta2( 0, false ), v1 );
+    BOOST_CHECK_EQUAL( G.delta2( 1, false ), v0 );
+    BOOST_CHECK( G.hasEdge( 0, 0 ) );
+    BOOST_CHECK( G.hasEdge( 0, 1 ) );
+    BOOST_CHECK( G.hasEdge( 1, 1 ) );
+    BOOST_CHECK( !G.hasEdge( 1, 0 ) );
+    BOOST_CHECK( !G.hasEdge( 2, 0 ) );
+    BOOST_CHECK( !G.hasEdge( 2, 1 ) );
+    BOOST_CHECK_EQUAL( G.findNb1( 0, 0 ), 1 );
+    BOOST_CHECK_EQUAL( G.findNb1( 0, 1 ), 0 );
+    BOOST_CHECK_EQUAL( G.findNb1( 1, 1 ), 0 );
+    BOOST_CHECK_EQUAL( G.findNb2( 0, 0 ), 0 );
+    BOOST_CHECK_EQUAL( G.findNb2( 0, 1 ), 0 );
+    BOOST_CHECK_EQUAL( G.findNb2( 1, 1 ), 1 );
 }
 
 
index 5c907e6..a7bc4b3 100644 (file)
@@ -159,6 +159,55 @@ BOOST_AUTO_TEST_CASE( AddEraseTest ) {
 }
 
 
+BOOST_AUTO_TEST_CASE( RandomAddEraseTest ) {
+    // check adding and erasing nodes and edges randomly
+    GraphAL G;
+    for( size_t maxN = 2; maxN < 50; maxN++ )
+        for( size_t repeats = 0; repeats < 10000; repeats++ ) {
+            size_t action = rnd( 5 );
+            size_t N = G.nrNodes();
+            size_t M = G.nrEdges();
+            size_t maxM = N * (N - 1) / 2;
+            if( action == 0 ) {
+                // add node
+                if( N < maxN )
+                    G.addNode();
+            } else if( action == 1 ) {
+                // erase node
+                if( N > 0 )
+                    G.eraseNode( rnd( N ) );
+            } else if( action == 2 || action == 3 ) {
+                // add edge
+                if( N >= 2 && M < maxM ) {
+                    size_t n1 = 0;
+                    do {
+                        n1 = rnd( N );
+                    } while( G.nb(n1).size() >= N - 1 );
+                    size_t n2 = 0;
+                    do {
+                        n2 = rnd( N );
+                    } while( G.hasEdge( n1, n2 ) );
+                    G.addEdge( n1, n2 );
+                }
+            } else if( action == 4 ) {
+                // erase edge
+                if( M > 0 ) {
+                    size_t n1 = 0;
+                    do {
+                        n1 = rnd( N );
+                    } while( G.nb(n1).size() == 0 );
+                    size_t n2 = 0;
+                    do {
+                        n2 = rnd( N );
+                    } while( !G.hasEdge( n1, n2 ) );
+                    G.eraseEdge( n1, n2 );
+                }
+            }
+            G.checkConsistency();
+        }
+}
+
+
 BOOST_AUTO_TEST_CASE( QueriesAndCreationTest ) {
     // check queries and createGraph* functions
 
index d863480..87d20f4 100644 (file)
@@ -37,6 +37,13 @@ BOOST_AUTO_TEST_CASE( ConstructorsTest ) {
     BOOST_CHECK( !y.contains( 5 ) );
     BOOST_CHECK( y.contains( 1 ) );
 
+    SmallSet<size_t> u( 0, 1 );
+    BOOST_CHECK( !u.empty() );
+    BOOST_CHECK_EQUAL( u.size(), 2 );
+    BOOST_CHECK( !u.contains( 2 ) );
+    BOOST_CHECK( u.contains( 1 ) );
+    BOOST_CHECK( u.contains( 0 ) );
+
     SmallSet<double> z( 1.0, 2.0 );
     BOOST_CHECK_EQUAL( z.size(), 2 );
     BOOST_CHECK( !z.contains( 5.0 ) );
@@ -54,7 +61,7 @@ BOOST_AUTO_TEST_CASE( ConstructorsTest ) {
     a.push_back( 4 );
     a.push_back( 3 );
     a.push_back( 2 );
-    SmallSet<double> w( a.begin(), a.end() );
+    SmallSet<double> w( a.begin(), a.end(), a.size() );
     BOOST_CHECK_EQUAL( w.size(), 4 );
     BOOST_CHECK( w.contains( 1 ) );
     BOOST_CHECK( w.contains( 2 ) );