Added BipartiteGraph unit tests and fixed some bugs
authorJoris Mooij <joris.mooij@tuebingen.mpg.de>
Mon, 22 Mar 2010 20:50:04 +0000 (21:50 +0100)
committerJoris Mooij <joris.mooij@tuebingen.mpg.de>
Mon, 22 Mar 2010 20:50:04 +0000 (21:50 +0100)
  - Fixed bug in BipartiteGraph::eraseNode1()
  - Fixed bug in BipartiteGraph::eraseNode2()
  - Fixed bug in BipartiteGraph::isTree()
  - Fixed bug in GraphAL::eraseNode()

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

index 218ba56..11b2ceb 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,17 +1,22 @@
 git HEAD
 --------
 
+* Improved BipartiteGraph code:
+  - Fixed bug in BipartiteGraph::eraseNode1()
+  - Fixed bug in BipartiteGraph::eraseNode2()
+  - Fixed bug in BipartiteGraph::isTree()
 * Improved GraphAL code:
   - Fixed bug in GraphAL::nrEdges()
   - Fixed bug in GraphAL::addEdge()
   - Fixed bug in GraphAL::isTree()
+  - Fixed bug in GraphAL::eraseNode()
   - Fixed bug in GraphAL::printDot()
   - Fixed bug in createGraphGrid3D()
   - Fixed bug in createGraphRegular()
   - Added GraphAL::hasEdge(size_t,size_t)
 * Removed RandomDRegularGraph()
 * Compressed Makefile
-* Added unit tests for Var, SmallSet, VarSet, Graph
+* Added unit tests for Var, SmallSet, VarSet, Graph, BipartiteGraph
 * Added unit testing framework
 * Added initialization of TRWBP weights by sampling spanning trees
 * Cleaned up MR code:
index 247b1d6..29c8a1a 100644 (file)
@@ -4,7 +4,7 @@
  *  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-2010  Joris Mooij  [joris dot mooij at libdai dot org]
  *  Copyright (C) 2006-2007  Radboud University Nijmegen, The Netherlands
  */
 
@@ -323,7 +323,7 @@ class BipartiteGraph {
         /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
         bool isTree() const;
 
-        /// Checks internal consistency
+        /// Asserts internal consistency
         void checkConsistency() const;
     //@}
 
index d728d31..d8fdab5 100644 (file)
@@ -52,13 +52,13 @@ void BipartiteGraph::eraseNode1( size_t n1 ) {
                 nb2(n2).erase( nb2(n2).begin() + iter );
             } else if( m1.node > n1 ) {
                 // update this entry and the corresponding dual of the neighboring node of type 1
-                m1.iter = iter;
                 m1.node--;
                 nb1( m1.node, m1.dual ).dual = iter;
-                iter++;
+                m1.iter = iter++;
             } else {
-                // skip
-                iter++;
+                // update this entry and the corresponding dual of the neighboring node of type 1
+                nb1( m1.node, m1.dual ).dual = iter;
+                m1.iter = iter++;
             }
         }
     }
@@ -78,13 +78,13 @@ void BipartiteGraph::eraseNode2( size_t n2 ) {
                 nb1(n1).erase( nb1(n1).begin() + iter );
             } else if( m2.node > n2 ) {
                 // update this entry and the corresponding dual of the neighboring node of type 2
-                m2.iter = iter;
                 m2.node--;
                 nb2( m2.node, m2.dual ).dual = iter;
-                iter++;
+                m2.iter = iter++;
             } else {
-                // skip
-                iter++;
+                // update this entry and the corresponding dual of the neighboring node of type 2
+                nb2( m2.node, m2.dual ).dual = iter;
+                m2.iter = iter++;
             }
         }
     }
@@ -232,8 +232,10 @@ bool BipartiteGraph::isTree() const {
     size_t nr_1 = 0;
     size_t nr_2 = 0;
 
-    if( nrNodes1() == 0 || nrNodes2() == 0 )
-        return true;
+    if( nrNodes1() == 0 )
+        return (nrNodes2() < 2 );
+    else if( nrNodes2() == 0 )
+        return (nrNodes1() < 2 );
     else {
         levelType newLevel;
         do {
index 034f269..b3d46d9 100644 (file)
@@ -55,13 +55,13 @@ void GraphAL::eraseNode( size_t n ) {
                 nb(n2).erase( nb(n2).begin() + iter );
             } else if( m.node > n ) {
                 // update this entry and the corresponding dual of the neighboring node
-                m.iter = iter;
                 m.node--;
                 nb( m.node, m.dual ).dual = iter;
-                iter++;
+                m.iter = iter++;
             } else {
-                // skip
-                iter++;
+                // update this entry and the corresponding dual of the neighboring node
+                nb( m.node, m.dual ).dual = iter;
+                m.iter = iter++;
             }
         }
     }
index 8058915..1c5d9f3 100644 (file)
@@ -79,17 +79,177 @@ BOOST_AUTO_TEST_CASE( ConstructorsTest ) {
 
 
 BOOST_AUTO_TEST_CASE( NeighborTest ) {
-    // TODO   
+    // check nb() accessor / mutator
+    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(1, 2) );
+    BipartiteGraph G( 2, 3, edges.begin(), edges.end() );
+    BOOST_CHECK_EQUAL( G.nb1(0).size(), 2 );
+    BOOST_CHECK_EQUAL( G.nb1(1).size(), 2 );
+    BOOST_CHECK_EQUAL( G.nb2(0).size(), 1 );
+    BOOST_CHECK_EQUAL( G.nb2(1).size(), 2 );
+    BOOST_CHECK_EQUAL( G.nb2(2).size(), 1 );
+    BOOST_CHECK_EQUAL( G.nb1(0,0).iter, 0 );
+    BOOST_CHECK_EQUAL( G.nb1(0,0).node, 0 );
+    BOOST_CHECK_EQUAL( G.nb1(0,0).dual, 0 );
+    BOOST_CHECK_EQUAL( G.nb1(0,1).iter, 1 );
+    BOOST_CHECK_EQUAL( G.nb1(0,1).node, 1 );
+    BOOST_CHECK_EQUAL( G.nb1(0,1).dual, 0 );
+    BOOST_CHECK_EQUAL( G.nb1(1,0).iter, 0 );
+    BOOST_CHECK_EQUAL( G.nb1(1,0).node, 1 );
+    BOOST_CHECK_EQUAL( G.nb1(1,0).dual, 1 );
+    BOOST_CHECK_EQUAL( G.nb1(1,1).iter, 1 );
+    BOOST_CHECK_EQUAL( G.nb1(1,1).node, 2 );
+    BOOST_CHECK_EQUAL( G.nb1(1,1).dual, 0 );
+    BOOST_CHECK_EQUAL( G.nb2(0,0).iter, 0 );
+    BOOST_CHECK_EQUAL( G.nb2(0,0).node, 0 );
+    BOOST_CHECK_EQUAL( G.nb2(0,0).dual, 0 );
+    BOOST_CHECK_EQUAL( G.nb2(1,0).iter, 0 );
+    BOOST_CHECK_EQUAL( G.nb2(1,0).node, 0 );
+    BOOST_CHECK_EQUAL( G.nb2(1,0).dual, 1 );
+    BOOST_CHECK_EQUAL( G.nb2(1,1).iter, 1 );
+    BOOST_CHECK_EQUAL( G.nb2(1,1).node, 1 );
+    BOOST_CHECK_EQUAL( G.nb2(1,1).dual, 0 );
+    BOOST_CHECK_EQUAL( G.nb2(2,0).iter, 0 );
+    BOOST_CHECK_EQUAL( G.nb2(2,0).node, 1 );
+    BOOST_CHECK_EQUAL( G.nb2(2,0).dual, 1 );
 }
 
 
 BOOST_AUTO_TEST_CASE( AddEraseTest ) {
-    // TODO   
+    // check addition and erasure of nodes and edges
+    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 ) );
+    BipartiteGraph G( 2, 2, edges.begin(), edges.end() );
+    G.checkConsistency();
+    BOOST_CHECK_EQUAL( G.nrNodes1(), 2 );
+    BOOST_CHECK_EQUAL( G.nrNodes2(), 2 );
+    BOOST_CHECK_EQUAL( G.nrEdges(), 3 );
+    BOOST_CHECK( G.isConnected() );
+    BOOST_CHECK( G.isTree() );
+    BOOST_CHECK_EQUAL( G.addNode1(), 2 );
+    BOOST_CHECK( !G.isConnected() );
+    BOOST_CHECK( !G.isTree() );
+    BOOST_CHECK_EQUAL( G.addNode2(), 2 );
+    BOOST_CHECK( !G.isConnected() );
+    BOOST_CHECK( !G.isTree() );
+    BOOST_CHECK_EQUAL( G.addNode1(), 3 );
+    BOOST_CHECK( !G.isConnected() );
+    BOOST_CHECK( !G.isTree() );
+    G.checkConsistency();
+    std::vector<size_t> nbs;
+    nbs.push_back( 2 );
+    nbs.push_back( 0 );
+    BOOST_CHECK_EQUAL( G.addNode1( nbs.begin(), nbs.end() ), 4 );
+    G.checkConsistency();
+    BOOST_CHECK( !G.isConnected() );
+    BOOST_CHECK( !G.isTree() );
+    BOOST_CHECK_EQUAL( G.addNode2( nbs.begin(), nbs.end() ), 3 );
+    G.checkConsistency();
+    BOOST_CHECK( !G.isConnected() );
+    BOOST_CHECK( !G.isTree() );
+    G.addEdge( 3, 3 );
+    G.checkConsistency();
+    BOOST_CHECK( G.isConnected() );
+    BOOST_CHECK( G.isTree() );
+    G.addEdge( 1, 3 );
+    G.checkConsistency();
+    BOOST_CHECK( G.isConnected() );
+    BOOST_CHECK( !G.isTree() );
+    BOOST_CHECK_EQUAL( G.nrNodes1(), 5 );
+    BOOST_CHECK_EQUAL( G.nrNodes2(), 4 );
+    BOOST_CHECK_EQUAL( G.nrEdges(), 9 );
+    G.eraseEdge( 0, 3 );
+    G.checkConsistency();
+    BOOST_CHECK( G.isConnected() );
+    BOOST_CHECK( G.isTree() );
+    G.eraseEdge( 4, 2 );
+    G.checkConsistency();
+    BOOST_CHECK( !G.isConnected() );
+    BOOST_CHECK( !G.isTree() );
+    G.eraseNode2( 2 );
+    G.checkConsistency();
+    BOOST_CHECK( G.isConnected() );
+    BOOST_CHECK( G.isTree() );
+    G.eraseNode1( 0 );
+    G.checkConsistency();
+    BOOST_CHECK( !G.isConnected() );
+    BOOST_CHECK( !G.isTree() );
+    G.addEdge( 1, 0 );
+    G.checkConsistency();
+    BOOST_CHECK( G.isConnected() );
+    BOOST_CHECK( G.isTree() );
+    G.eraseNode1( 2 );
+    G.checkConsistency();
+    BOOST_CHECK( G.isConnected() );
+    BOOST_CHECK( G.isTree() );
+    G.eraseNode2( 2 );
+    G.checkConsistency();
+    BOOST_CHECK( !G.isConnected() );
+    BOOST_CHECK( !G.isTree() );
+    G.addEdge( 1, 1 );
+    G.checkConsistency();
+    BOOST_CHECK( G.isConnected() );
+    BOOST_CHECK( G.isTree() );
+    G.eraseNode2( 1 );
+    G.checkConsistency();
+    BOOST_CHECK( !G.isConnected() );
+    BOOST_CHECK( !G.isTree() );
+    G.eraseNode1( 1 );
+    G.checkConsistency();
+    BOOST_CHECK( !G.isConnected() );
+    BOOST_CHECK( !G.isTree() );
+    G.addEdge( 0, 0 );
+    G.checkConsistency();
+    BOOST_CHECK( G.isConnected() );
+    BOOST_CHECK( G.isTree() );
+    G.eraseNode2( 0 );
+    G.checkConsistency();
+    BOOST_CHECK( !G.isConnected() );
+    BOOST_CHECK( !G.isTree() );
+    G.eraseNode1( 0 );
+    G.checkConsistency();
+    BOOST_CHECK( G.isConnected() );
+    BOOST_CHECK( G.isTree() );
+    G.eraseNode1( 0 );
+    G.checkConsistency();
+    BOOST_CHECK( G.isConnected() );
+    BOOST_CHECK( G.isTree() );
+    BOOST_CHECK_EQUAL( G.nrNodes1(), 0 );
+    BOOST_CHECK_EQUAL( G.nrNodes2(), 0 );
+    BOOST_CHECK_EQUAL( G.nrEdges(), 0 );
 }
 
 
 BOOST_AUTO_TEST_CASE( QueriesTest ) {
-    // TODO   
+    // 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 ) );
+    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 );
 }
 
 
index b2e475c..5c907e6 100644 (file)
@@ -41,11 +41,12 @@ BOOST_AUTO_TEST_CASE( ConstructorsTest ) {
     BOOST_CHECK_EQUAL( G2.isTree(), false );
     G2.checkConsistency();
     
-    std::vector<GraphAL::Edge> edges;
-    edges.push_back( GraphAL::Edge( 0, 1 ) );
-    edges.push_back( GraphAL::Edge( 1, 2 ) );
-    edges.push_back( GraphAL::Edge( 2, 1 ) );
-    edges.push_back( GraphAL::Edge( 1, 2 ) );
+    typedef GraphAL::Edge Edge;
+    std::vector<Edge> edges;
+    edges.push_back( Edge( 0, 1 ) );
+    edges.push_back( Edge( 1, 2 ) );
+    edges.push_back( Edge( 2, 1 ) );
+    edges.push_back( Edge( 1, 2 ) );
     GraphAL G3( 3, edges.begin(), edges.end() );
     BOOST_CHECK_EQUAL( G3.nrNodes(), 3 );
     BOOST_CHECK_EQUAL( G3.nrEdges(), 2 );
@@ -57,91 +58,104 @@ BOOST_AUTO_TEST_CASE( ConstructorsTest ) {
 
 BOOST_AUTO_TEST_CASE( NeighborTest ) {
     // check nb() accessor / mutator
-    std::vector<GraphAL::Edge> edges;
-    edges.push_back( GraphAL::Edge( 0, 1 ) );
-    edges.push_back( GraphAL::Edge( 1, 2 ) );
-    GraphAL G3( 3, edges.begin(), edges.end() );
-    BOOST_CHECK_EQUAL( G3.nb(0).size(), 1 );
-    BOOST_CHECK_EQUAL( G3.nb(1).size(), 2 );
-    BOOST_CHECK_EQUAL( G3.nb(2).size(), 1 );
-    BOOST_CHECK_EQUAL( G3.nb(0,0).iter, 0 );
-    BOOST_CHECK_EQUAL( G3.nb(0,0).node, 1 );
-    BOOST_CHECK_EQUAL( G3.nb(0,0).dual, 0 );
-    BOOST_CHECK_EQUAL( G3.nb(1,0).iter, 0 );
-    BOOST_CHECK_EQUAL( G3.nb(1,0).node, 0 );
-    BOOST_CHECK_EQUAL( G3.nb(1,0).dual, 0 );
-    BOOST_CHECK_EQUAL( G3.nb(1,1).iter, 1 );
-    BOOST_CHECK_EQUAL( G3.nb(1,1).node, 2 );
-    BOOST_CHECK_EQUAL( G3.nb(1,1).dual, 0 );
-    BOOST_CHECK_EQUAL( G3.nb(2,0).iter, 0 );
-    BOOST_CHECK_EQUAL( G3.nb(2,0).node, 1 );
-    BOOST_CHECK_EQUAL( G3.nb(2,0).dual, 1 );
+    typedef GraphAL::Edge Edge;
+    std::vector<Edge> edges;
+    edges.push_back( Edge( 0, 1 ) );
+    edges.push_back( Edge( 1, 2 ) );
+    GraphAL G( 3, edges.begin(), edges.end() );
+    BOOST_CHECK_EQUAL( G.nb(0).size(), 1 );
+    BOOST_CHECK_EQUAL( G.nb(1).size(), 2 );
+    BOOST_CHECK_EQUAL( G.nb(2).size(), 1 );
+    BOOST_CHECK_EQUAL( G.nb(0,0).iter, 0 );
+    BOOST_CHECK_EQUAL( G.nb(0,0).node, 1 );
+    BOOST_CHECK_EQUAL( G.nb(0,0).dual, 0 );
+    BOOST_CHECK_EQUAL( G.nb(1,0).iter, 0 );
+    BOOST_CHECK_EQUAL( G.nb(1,0).node, 0 );
+    BOOST_CHECK_EQUAL( G.nb(1,0).dual, 0 );
+    BOOST_CHECK_EQUAL( G.nb(1,1).iter, 1 );
+    BOOST_CHECK_EQUAL( G.nb(1,1).node, 2 );
+    BOOST_CHECK_EQUAL( G.nb(1,1).dual, 0 );
+    BOOST_CHECK_EQUAL( G.nb(2,0).iter, 0 );
+    BOOST_CHECK_EQUAL( G.nb(2,0).node, 1 );
+    BOOST_CHECK_EQUAL( G.nb(2,0).dual, 1 );
 }
 
 
 BOOST_AUTO_TEST_CASE( AddEraseTest ) {
     // check addition and erasure of nodes and edges
-    std::vector<GraphAL::Edge> edges;
-    edges.push_back( GraphAL::Edge( 0, 1 ) );
-    edges.push_back( GraphAL::Edge( 1, 2 ) );
-    edges.push_back( GraphAL::Edge( 1, 0 ) );
-    GraphAL G3( 2 );
-    G3.construct( 3, edges.begin(), edges.end() );
-    G3.checkConsistency();
-    BOOST_CHECK_EQUAL( G3.nrNodes(), 3 );
-    BOOST_CHECK_EQUAL( G3.nrEdges(), 2 );
-    BOOST_CHECK_EQUAL( G3.addNode(), 3 );
-    G3.checkConsistency();
+    typedef GraphAL::Edge Edge;
+    std::vector<Edge> edges;
+    edges.push_back( Edge( 0, 1 ) );
+    edges.push_back( Edge( 1, 2 ) );
+    edges.push_back( Edge( 1, 0 ) );
+    GraphAL G( 2 );
+    G.construct( 3, edges.begin(), edges.end() );
+    G.checkConsistency();
+    BOOST_CHECK_EQUAL( G.nrNodes(), 3 );
+    BOOST_CHECK_EQUAL( G.nrEdges(), 2 );
+    BOOST_CHECK_EQUAL( G.addNode(), 3 );
+    G.checkConsistency();
     std::vector<size_t> nbs;
     nbs.push_back( 3 );
-    G3.addNode( nbs.begin(), nbs.end() );
-    BOOST_CHECK_EQUAL( G3.addNode(), 5 );
-    G3.checkConsistency();
-    G3.addEdge( 0, 4 );
-    G3.checkConsistency();
-    G3.addEdge( 0, 5 );
-    BOOST_CHECK( G3.isTree() );
-    G3.checkConsistency();
-    BOOST_CHECK_EQUAL( G3.nrNodes(), 6 );
-    BOOST_CHECK_EQUAL( G3.nrEdges(), 5 );
-    G3.addEdge( 2, 3 );
-    BOOST_CHECK( !G3.isTree() );
+    BOOST_CHECK_EQUAL( G.addNode( nbs.begin(), nbs.end() ), 4 );
+    BOOST_CHECK_EQUAL( G.addNode(), 5 );
+    G.checkConsistency();
+    G.addEdge( 0, 4 );
+    G.checkConsistency();
+    G.addEdge( 0, 5 );
+    BOOST_CHECK( G.isTree() );
+    G.checkConsistency();
+    BOOST_CHECK_EQUAL( G.nrNodes(), 6 );
+    BOOST_CHECK_EQUAL( G.nrEdges(), 5 );
+    G.addEdge( 2, 3 );
+    BOOST_CHECK( !G.isTree() );
 
-    G3.addEdge( 5, 3 );
-    G3.eraseNode( 0 );
-    G3.checkConsistency();
-    BOOST_CHECK( G3.isTree() );
-    G3.eraseEdge( 0, 1 );
-    G3.checkConsistency();
-    BOOST_CHECK( !G3.isTree() );
-    BOOST_CHECK( !G3.isConnected() );
-    G3.eraseNode( 0 );
-    G3.checkConsistency();
-    BOOST_CHECK( G3.isTree() );
-    G3.addEdge( 3, 2 );
-    G3.checkConsistency();
-    BOOST_CHECK( !G3.isTree() );
-    G3.eraseNode( 1 );
-    G3.checkConsistency();
-    BOOST_CHECK( !G3.isTree() );
-    BOOST_CHECK( !G3.isConnected() );
-    G3.eraseNode( 2 );
-    G3.checkConsistency();
-    BOOST_CHECK( !G3.isTree() );
-    BOOST_CHECK( !G3.isConnected() );
-    G3.addEdge( 1, 0 );
-    G3.checkConsistency();
-    BOOST_CHECK( G3.isTree() );
-    BOOST_CHECK( G3.isConnected() );
-    G3.eraseNode( 1 );
-    G3.checkConsistency();
-    BOOST_CHECK( G3.isTree() );
-    BOOST_CHECK( G3.isConnected() );
-    G3.eraseNode( 0 );
-    BOOST_CHECK( G3.isTree() );
-    BOOST_CHECK( G3.isConnected() );
-    BOOST_CHECK_EQUAL( G3.nrNodes(), 0 );
-    BOOST_CHECK_EQUAL( G3.nrEdges(), 0 );
+    G.addEdge( 5, 3 );
+    G.eraseNode( 0 );
+    G.checkConsistency();
+    BOOST_CHECK( G.isTree() );
+    G.eraseEdge( 0, 1 );
+    G.checkConsistency();
+    BOOST_CHECK( !G.isTree() );
+    BOOST_CHECK( !G.isConnected() );
+    G.eraseNode( 0 );
+    G.checkConsistency();
+    BOOST_CHECK( G.isTree() );
+    G.addEdge( 3, 2 );
+    G.checkConsistency();
+    BOOST_CHECK( !G.isTree() );
+    G.eraseNode( 1 );
+    G.checkConsistency();
+    BOOST_CHECK( !G.isTree() );
+    BOOST_CHECK( !G.isConnected() );
+    G.eraseNode( 2 );
+    G.checkConsistency();
+    BOOST_CHECK( !G.isTree() );
+    BOOST_CHECK( !G.isConnected() );
+    G.addEdge( 1, 0 );
+    G.checkConsistency();
+    BOOST_CHECK( G.isTree() );
+    BOOST_CHECK( G.isConnected() );
+    G.eraseNode( 1 );
+    G.checkConsistency();
+    BOOST_CHECK( G.isTree() );
+    BOOST_CHECK( G.isConnected() );
+    G.eraseNode( 0 );
+    BOOST_CHECK( G.isTree() );
+    BOOST_CHECK( G.isConnected() );
+    BOOST_CHECK_EQUAL( G.nrNodes(), 0 );
+    BOOST_CHECK_EQUAL( G.nrEdges(), 0 );
+
+    G.addNode();
+    G.addNode();
+    G.addNode();
+    G.addNode();
+    G.addEdge( 0, 1 );
+    G.addEdge( 2, 3 );
+    G.addEdge( 0, 3 );
+    G.checkConsistency();
+    G.eraseNode( 2 );
+    G.checkConsistency();
 }