Added GraphAL unit tests, fixed 6 bugs in GraphAL and added functionality:
authorJoris Mooij <joris.mooij@tuebingen.mpg.de>
Mon, 22 Mar 2010 12:51:57 +0000 (13:51 +0100)
committerJoris Mooij <joris.mooij@tuebingen.mpg.de>
Mon, 22 Mar 2010 12:51:57 +0000 (13:51 +0100)
  - Fixed bug in GraphAL::nrEdges()
  - Fixed bug in GraphAL::addEdge()
  - Fixed bug in GraphAL::isTree()
  - Fixed bug in GraphAL::printDot()
  - Fixed bug in createGraphGrid3D()
  - Fixed bug in createGraphRegular()
  - Added GraphAL::hasEdge(size_t,size_t)
  - Removed RandomDRegularGraph()

ChangeLog
Makefile
include/dai/graph.h
include/dai/weightedgraph.h
src/bipgraph.cpp
src/graph.cpp
src/weightedgraph.cpp
tests/unit/graph.cpp [new file with mode: 0644]
tests/unit/varset.cpp

index 5e6974d..218ba56 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,8 +1,17 @@
 git HEAD
 --------
 
+* Improved GraphAL code:
+  - Fixed bug in GraphAL::nrEdges()
+  - Fixed bug in GraphAL::addEdge()
+  - Fixed bug in GraphAL::isTree()
+  - 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
+* Added unit tests for Var, SmallSet, VarSet, Graph
 * Added unit testing framework
 * Added initialization of TRWBP weights by sampling spanning trees
 * Cleaned up MR code:
index ad71357..a5c6ce3 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -122,11 +122,12 @@ examples : examples/example$(EE) examples/example_bipgraph$(EE) examples/example
 
 matlabs : matlab/dai$(ME) matlab/dai_readfg$(ME) matlab/dai_writefg$(ME) matlab/dai_potstrength$(ME)
 
-unittests : tests/unit/var$(EE) tests/unit/smallset$(EE) tests/unit/varset$(EE)
+unittests : tests/unit/var$(EE) tests/unit/smallset$(EE) tests/unit/varset$(EE) tests/unit/graph$(EE)
        echo Running unit tests...
        tests/unit/var
        tests/unit/smallset
        tests/unit/varset
+       tests/unit/graph
 
 tests : tests/testdai$(EE) tests/testem/testem$(EE) tests/testbbp$(EE) $(unittests)
 
@@ -194,6 +195,8 @@ tests/unit/smallset$(EE) : tests/unit/smallset.cpp $(HEADERS) $(LIB)/libdai$(LE)
        $(CC) $(CCO)$@ $< $(LIBS) $(BOOSTLIBS_UTF)
 tests/unit/varset$(EE) : tests/unit/varset.cpp $(HEADERS) $(LIB)/libdai$(LE)
        $(CC) $(CCO)$@ $< $(LIBS) $(BOOSTLIBS_UTF)
+tests/unit/graph$(EE) : tests/unit/graph.cpp $(HEADERS) $(LIB)/libdai$(LE)
+       $(CC) $(CCO)$@ $< $(LIBS) $(BOOSTLIBS_UTF)
 
 
 # TESTS
@@ -300,7 +303,7 @@ clean :
        -rm matlab/*$(ME)
        -rm examples/example$(EE) examples/example_bipgraph$(EE) examples/example_varset$(EE) examples/example_permute$(EE) examples/example_sprinkler$(EE) examples/example_sprinkler_gibbs$(EE) examples/example_sprinkler_em$(EE)
        -rm tests/testdai$(EE) tests/testem/testem$(EE) tests/testbbp$(EE)
-       -rm tests/unit/var$(EE) tests/unit/smallset$(EE) tests/unit/varset$(EE)
+       -rm tests/unit/var$(EE) tests/unit/smallset$(EE) tests/unit/varset$(EE) tests/unit/graph$(EE)
        -rm utils/fg2dot$(EE) utils/createfg$(EE) utils/fginfo$(EE)
        -rm -R doc
        -rm -R lib
@@ -330,6 +333,7 @@ clean :
        -del tests\unit\var$(EE)
        -del tests\unit\smallset$(EE)
        -del tests\unit\varset$(EE)
+       -del tests\unit\graph$(EE)
        -del $(LIB)\libdai$(LE)
        -rmdir lib
 endif
index 9556ca2..3526ef6 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
  */
 
@@ -119,9 +119,6 @@ class GraphAL {
         /// Contains for each node a vector of its neighbors
         std::vector<Neighbors> _nb;
 
-        /// Used internally by isTree()
-        typedef std::vector<size_t> levelType;
-
     public:
     /// \name Constructors and destructors
     //@{
@@ -232,7 +229,17 @@ class GraphAL {
             size_t sum = 0;
             for( size_t i = 0; i < nrNodes(); i++ )
                 sum += nb(i).size();
-            return sum;
+            return sum / 2;
+        }
+
+        /// 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
+         */
+        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;
+            return false;
         }
 
         /// Returns the index of a given node \a n2 amongst the neighbors of \a n1
@@ -253,13 +260,13 @@ class GraphAL {
         /// 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;
     //@}
 
     /// \name Input and output
     //@{
-        /// Writes this GraphAL to an output stream in GraphALViz .dot syntax
+        /// Writes this GraphAL to an output stream in GraphViz .dot syntax
         void printDot( std::ostream& os ) const;
     //@}
 };
@@ -282,15 +289,21 @@ void GraphAL::construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator e
 
 /// Creates a fully-connected graph with \a N nodes
 GraphAL createGraphFull( size_t N );
-/// Creates a two-dimensional rectangular grid of \a n1 by \a n2 nodes, which can be \a periodic
-GraphAL createGraphGrid( size_t n1, size_t n2, bool periodic );
-/// Creates a three-dimensional rectangular grid of \a n1 by \a n2 by \a n3 nodes, which can be \a periodic
-GraphAL createGraphGrid3D( size_t n1, size_t n2, size_t n3, bool periodic );
+/// Creates a two-dimensional rectangular grid of \a N1 by \a N2 nodes, which can be \a periodic
+GraphAL createGraphGrid( size_t N1, size_t N2, bool periodic );
+/// Creates a three-dimensional rectangular grid of \a N1 by \a N2 by \a N3 nodes, which can be \a periodic
+GraphAL createGraphGrid3D( size_t N1, size_t N2, size_t N3, bool periodic );
 /// Creates a graph consisting of a single loop of \a N nodes
 GraphAL createGraphLoop( size_t N );
 /// Creates a random tree-structured graph of \a N nodes
 GraphAL createGraphTree( size_t N );
 /// Creates a random regular graph of \a N nodes with uniform connectivity \a d
+/** Algorithm 1 in [\ref StW99].
+ *  Draws a random graph of size \a N and uniform degree \a d
+ *  from an almost uniform probability distribution over these graphs
+ *  (which becomes uniform in the limit that \a d is small and \a N goes
+ *  to infinity).
+ */
 GraphAL createGraphRegular( size_t N, size_t d );
 
 
index 5c49bde..f8b5bff 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
  */
 
@@ -216,16 +216,6 @@ template<typename T> RootedTree MaxSpanningTreePrims( const WeightedGraph<T> &G
 }
 
 
-/// Constructs a random undirected graph of \a N nodes, where each node has connectivity \a d
-/** Algorithm 1 in [\ref StW99].
- *  Draws a random graph of size \a N and uniform degree \a d
- *  from an almost uniform probability distribution over these graphs
- *  (which becomes uniform in the limit that \a d is small and \a N goes
- *  to infinity).
- */
-GraphEL RandomDRegularGraph( size_t N, size_t d );
-
-
 } // end of namespace dai
 
 
index 8dbe4c1..d728d31 100644 (file)
@@ -226,7 +226,6 @@ bool BipartiteGraph::isConnected() const {
 
 
 bool BipartiteGraph::isTree() const {
-    using namespace std;
     vector<levelType> levels;
 
     bool foundCycle = false;
@@ -294,7 +293,6 @@ bool BipartiteGraph::isTree() const {
 
 
 void BipartiteGraph::printDot( std::ostream& os ) const {
-    using namespace std;
     os << "graph G {" << endl;
     os << "node[shape=circle,width=0.4,fixedsize=true];" << endl;
     for( size_t n1 = 0; n1 < nrNodes1(); n1++ )
index 73e5a54..034f269 100644 (file)
@@ -33,7 +33,7 @@ void GraphAL::addEdge( size_t n1, size_t n2, bool check ) {
                 break;
             }
     }
-    if( !exists ) { // Add edge
+    if( !exists && n1 != n2 ) { // Add edge
         Neighbor nb_1( nb(n1).size(), n2, nb(n2).size() );
         Neighbor nb_2( nb_1.dual, n1, nb_1.iter );
         nb(n1).push_back( nb_1 );
@@ -158,44 +158,43 @@ bool GraphAL::isConnected() const {
 
 
 bool GraphAL::isTree() const {
-    using namespace std;
+    typedef vector<Edge> levelType; // first is node, second is its parent
     vector<levelType> levels;
 
-    bool foundCycle = false;
-    size_t Nr = 0;
-
     if( nrNodes() == 0 )
         return true;
     else {
-        levelType newLevel;
+        // start with root node 0
+        levels.push_back( levelType( 1, Edge( 0, 0 ) ) );
+        size_t treeSize = 1;
+        bool foundCycle = false;
         do {
-            newLevel.clear();
-            if( levels.size() == 0 ) {
-                size_t n1 = 0;
-                // add n1
-                newLevel = vector<size_t>( 1, n1 );
-            } else {
-                const levelType &prevLevel = levels.back();
-                // build newLevel
-                foreach( size_t n2, prevLevel ) { // for all n2 in the previous level
-                    foreach( const Neighbor &n1, nb(n2) ) { // for all neighbors n1 of n2
-                        if( find( prevLevel.begin(), prevLevel.end(), n1 ) == prevLevel.end() ) { // n1 not in previous level
-                            if( find( newLevel.begin(), newLevel.end(), n1 ) != newLevel.end() )
-                                foundCycle = true; // n1 already in new level: we found a cycle
-                            else
-                                newLevel.push_back( n1 ); // add n1 to new level
-                        }
-                        if( foundCycle )
-                            break;
+            levels.push_back( levelType() );
+            const levelType &prevLevel = levels[levels.size() - 2];
+            // build new level: add all neighbors of nodes in the previous level
+            // (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
+                    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++ )
+                                if( levels[l][f].first == n1 )
+                                    // n1 has been visited before -> found a cycle
+                                    foundCycle = true;
+                        if( !foundCycle )
+                            // add n1 (and its parent n2) to current level
+                            levels.back().push_back( Edge( n1, n2 ) ); 
                     }
                     if( foundCycle )
                         break;
                 }
+                if( foundCycle )
+                    break;
             }
-            levels.push_back( newLevel );
-            Nr += newLevel.size();
-        } while( (newLevel.size() != 0) && !foundCycle );
-        if( Nr == nrNodes() && !foundCycle )
+            treeSize += levels.back().size();
+        } while( (levels.back().size() != 0) && !foundCycle );
+        if( treeSize == nrNodes() && !foundCycle )
             return true;
         else
             return false;
@@ -204,14 +203,14 @@ bool GraphAL::isTree() const {
 
 
 void GraphAL::printDot( std::ostream& os ) const {
-    using namespace std;
     os << "graph G {" << 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) )
-            os << "\tx" << n1 << " -- y" << n2 << ";" << endl;
+            if( n1 < n2 )
+                os << "\tx" << n1 << " -- x" << n2 << ";" << endl;
     os << "}" << endl;
 }
 
@@ -250,30 +249,32 @@ GraphAL createGraphFull( size_t N ) {
 }
 
 
-GraphAL createGraphGrid( size_t n1, size_t n2, bool periodic ) {
-    GraphAL result( n1*n2 );
-    for( size_t i1 = 0; i1 < n1; i1++ )
-        for( size_t i2 = 0; i2 < n2; i2++ ) {
-            if( i1+1 < n1 || periodic )
-                result.addEdge( i1*n2 + i2, ((i1+1)%n1)*n2 + i2, n1 <= 2 );
-            if( i2+1 < n2 || periodic )
-                result.addEdge( i1*n2 + i2, i1*n2 + ((i2+1)%n2), n2 <= 2 );
+GraphAL createGraphGrid( size_t N1, size_t N2, bool periodic ) {
+    GraphAL result( N1*N2 );
+    if( N1 == 1 && N2 == 1 )
+        return result;
+    for( size_t i1 = 0; i1 < N1; i1++ )
+        for( size_t i2 = 0; i2 < N2; i2++ ) {
+            if( i1+1 < N1 || periodic )
+                result.addEdge( i1*N2 + i2, ((i1+1)%N1)*N2 + i2, N1 <= 2 );
+            if( i2+1 < N2 || periodic )
+                result.addEdge( i1*N2 + i2, i1*N2 + ((i2+1)%N2), N2 <= 2 );
         }
     return result;
 }
 
 
-GraphAL createGraphGrid3D( size_t n1, size_t n2, size_t n3, bool periodic ) {
-    GraphAL result( n1*n2*n3 );
-    for( size_t i1 = 0; i1 < n1; i1++ )
-        for( size_t i2 = 0; i2 < n2; i2++ )
-            for( size_t i3 = 0; i3 < n3; i3++ ) {
-                if( i1+1 < n1 || periodic )
-                    result.addEdge( i1*n2*n3 + i2*n3 + i3, ((i1+1)%n1)*n2*n3 + i2*n3 + i3, n1 <= 2 );
-                if( i2+1 < n2 || periodic )
-                    result.addEdge( i1*n2*n3 + i2*n3 + i3, i1*n2*n3 + ((i2+1)%n2)*n3 + i3, n2 <= 2 );
-                if( i3+1 < n2 || periodic )
-                    result.addEdge( i1*n2*n3 + i2*n3 + i3, i1*n2*n3 + i2*n3 + ((i3+1)%n3), n3 <= 2 );
+GraphAL createGraphGrid3D( size_t N1, size_t N2, size_t N3, bool periodic ) {
+    GraphAL result( N1*N2*N3 );
+    for( size_t i1 = 0; i1 < N1; i1++ )
+        for( size_t i2 = 0; i2 < N2; i2++ )
+            for( size_t i3 = 0; i3 < N3; i3++ ) {
+                if( i1+1 < N1 || periodic )
+                    result.addEdge( i1*N2*N3 + i2*N3 + i3, ((i1+1)%N1)*N2*N3 + i2*N3 + i3, N1 <= 2 );
+                if( i2+1 < N2 || periodic )
+                    result.addEdge( i1*N2*N3 + i2*N3 + i3, i1*N2*N3 + ((i2+1)%N2)*N3 + i3, N2 <= 2 );
+                if( i3+1 < N3 || periodic )
+                    result.addEdge( i1*N2*N3 + i2*N3 + i3, i1*N2*N3 + i2*N3 + ((i3+1)%N3), N3 <= 2 );
             }
     return result;
 }
@@ -298,8 +299,61 @@ GraphAL createGraphTree( size_t N ) {
 
 
 GraphAL createGraphRegular( size_t N, size_t d ) {
-    GraphEL g = RandomDRegularGraph( N, d );
-    return GraphAL( N, g.begin(), g.end() );
+    DAI_ASSERT( (N * d) % 2 == 0 );
+    DAI_ASSERT( d < N );
+
+    GraphAL G( N );
+    if( d > 0 ) {
+        bool ready = false;
+        size_t tries = 0;
+        while( !ready ) {
+            tries++;
+
+            // Start with N*d points {0,1,...,N*d-1} (N*d even) in N groups.
+            // Put U = {0,1,...,N*d-1}. (U denotes the set of unpaired points.)
+            vector<size_t> U;
+            U.reserve( N * d );
+            for( size_t i = 0; i < N * d; i++ )
+                U.push_back( i );
+
+            // Repeat the following until no suitable pair can be found: Choose
+            // two random points i and j in U, and if they are suitable, pair
+            // i with j and delete i and j from U.
+            G = GraphAL( N );
+            bool finished = false;
+            while( !finished ) {
+                random_shuffle( U.begin(), U.end() );
+                size_t i1, i2;
+                bool suit_pair_found = false;
+                for( i1 = 0; i1 < U.size()-1 && !suit_pair_found; i1++ )
+                    for( i2 = i1+1; i2 < U.size() && !suit_pair_found; i2++ )
+                        if( ((U[i1] / d) != (U[i2] / d)) && !G.hasEdge( U[i1] / d, U[i2] / d ) ) {
+                            // they are suitable
+                            suit_pair_found = true;
+                            G.addEdge( U[i1] / d, U[i2] / d, false );
+                            U.erase( U.begin() + i2 );  // first remove largest
+                            U.erase( U.begin() + i1 );  // remove smallest
+                        }
+                if( !suit_pair_found || U.empty() )
+                    finished = true;
+            }
+
+            if( U.empty() ) {
+                // G is a graph with edge from vertex r to vertex s if and only if
+                // there is a pair containing points in the r'th and s'th groups.
+                // If G is d-regular, output, otherwise return to Step 1.
+                ready = true;
+                for( size_t n = 0; n < N; n++ )
+                    if( G.nb(n).size() != d ) {
+                        ready = false;
+                        break;
+                    }
+            } else
+                ready = false;
+        }
+    }
+
+    return G;
 }
 
 
index f51e982..3c45bdd 100644 (file)
@@ -57,68 +57,4 @@ RootedTree::RootedTree( const GraphEL &T, size_t Root ) {
 }
 
 
-GraphEL RandomDRegularGraph( size_t N, size_t d ) {
-    DAI_ASSERT( (N * d) % 2 == 0 );
-
-    bool ready = false;
-    std::vector<UEdge> G;
-
-    size_t tries = 0;
-    while( !ready ) {
-        tries++;
-
-        // Start with N*d points {0,1,...,N*d-1} (N*d even) in N groups.
-        // Put U = {0,1,...,N*d-1}. (U denotes the set of unpaired points.)
-        vector<size_t> U;
-        U.reserve( N * d );
-        for( size_t i = 0; i < N * d; i++ )
-            U.push_back( i );
-
-        // Repeat the following until no suitable pair can be found: Choose
-        // two random points i and j in U, and if they are suitable, pair
-        // i with j and delete i and j from U.
-        G.clear();
-        bool finished = false;
-        while( !finished ) {
-            random_shuffle( U.begin(), U.end() );
-            size_t i1, i2;
-            bool suit_pair_found = false;
-            for( i1 = 0; i1 < U.size()-1 && !suit_pair_found; i1++ )
-                for( i2 = i1+1; i2 < U.size() && !suit_pair_found; i2++ )
-                    if( (U[i1] / d) != (U[i2] / d) ) {
-                        // they are suitable
-                        suit_pair_found = true;
-                        G.push_back( UEdge( U[i1] / d, U[i2] / d ) );
-                        U.erase( U.begin() + i2 );  // first remove largest
-                        U.erase( U.begin() + i1 );  // remove smallest
-                    }
-            if( !suit_pair_found || U.empty() )
-                finished = true;
-        }
-
-        if( U.empty() ) {
-            // G is a graph with edge from vertex r to vertex s if and only if
-            // there is a pair containing points in the r'th and s'th groups.
-            // If G is d-regular, output, otherwise return to Step 1.
-
-            vector<size_t> degrees;
-            degrees.resize( N, 0 );
-            foreach( const UEdge &e, G ) {
-                degrees[e.n1]++;
-                degrees[e.n2]++;
-            }
-            ready = true;
-            for( size_t n = 0; n < N; n++ )
-                if( degrees[n] != d ) {
-                    ready = false;
-                    break;
-                }
-        } else
-            ready = false;
-    }
-
-    return GraphEL( G.begin(), G.end() );
-}
-
-
 } // end of namespace dai
diff --git a/tests/unit/graph.cpp b/tests/unit/graph.cpp
new file mode 100644 (file)
index 0000000..b2e475c
--- /dev/null
@@ -0,0 +1,384 @@
+/*  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) 2010  Joris Mooij      [joris dot mooij at libdai dot org]
+ */
+
+
+#define BOOST_TEST_DYN_LINK
+
+
+#include <dai/graph.h>
+#include <vector>
+#include <strstream>
+
+
+using namespace dai;
+
+
+#define BOOST_TEST_MODULE GraphALTest
+
+
+#include <boost/test/unit_test.hpp>
+
+
+BOOST_AUTO_TEST_CASE( ConstructorsTest ) {
+    // check constructors
+    GraphAL G0;
+    BOOST_CHECK_EQUAL( G0.nrNodes(), 0 );
+    BOOST_CHECK_EQUAL( G0.nrEdges(), 0 );
+    BOOST_CHECK_EQUAL( G0.isConnected(), true );
+    BOOST_CHECK_EQUAL( G0.isTree(), true );
+    G0.checkConsistency();
+
+    GraphAL G2( 2 );
+    BOOST_CHECK_EQUAL( G2.nrNodes(), 2 );
+    BOOST_CHECK_EQUAL( G2.nrEdges(), 0 );
+    BOOST_CHECK_EQUAL( G2.isConnected(), false );
+    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 ) );
+    GraphAL G3( 3, edges.begin(), edges.end() );
+    BOOST_CHECK_EQUAL( G3.nrNodes(), 3 );
+    BOOST_CHECK_EQUAL( G3.nrEdges(), 2 );
+    BOOST_CHECK_EQUAL( G3.isConnected(), true );
+    BOOST_CHECK_EQUAL( G3.isTree(), true );
+    G3.checkConsistency();
+}
+
+
+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 );
+}
+
+
+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();
+    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() );
+
+    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 );
+}
+
+
+BOOST_AUTO_TEST_CASE( QueriesAndCreationTest ) {
+    // check queries and createGraph* functions
+
+    // createGraphFull
+    for( size_t N = 0; N < 20; N++ ) {
+        GraphAL G = createGraphFull( N );
+        BOOST_CHECK_EQUAL( G.nrNodes(), N );
+        BOOST_CHECK_EQUAL( G.nrEdges(), N > 0 ? N * (N-1) / 2 : 0 );
+        BOOST_CHECK( G.isConnected() );
+        BOOST_CHECK_EQUAL( G.isTree(), N < 3 );
+        for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
+            foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
+                BOOST_CHECK( G.hasEdge( n1, n2 ) );
+                BOOST_CHECK( G.hasEdge( n2, n1 ) );
+            }
+            for( size_t n2 = 0; n2 < G.nrNodes(); n2++ )
+                if( G.hasEdge( n1, n2 ) ) {
+                    BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ), n2 );
+                    BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ), n1 );
+                    BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ).iter, G.findNb( n1, n2 ) );
+                    BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ).iter, G.findNb( n2, n1 ) );
+                }
+        }
+        G.checkConsistency();
+    }
+
+    // createGraphGrid
+    for( size_t N1 = 0; N1 < 10; N1++ )
+        for( size_t N2 = 0; N2 < 10; N2++ ) {
+            GraphAL G = createGraphGrid( N1, N2, false );
+            BOOST_CHECK_EQUAL( G.nrNodes(), N1 * N2 );
+            BOOST_CHECK_EQUAL( G.nrEdges(), (N1 > 0 && N2 > 0) ? 2 * (N1-1) * (N2-1) + (N1-1) + (N2-1) : 0 );
+            BOOST_CHECK( G.isConnected() );
+            BOOST_CHECK_EQUAL( G.isTree(), (N1 <= 1) || (N2 <= 1) );
+            for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
+                foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
+                    BOOST_CHECK( G.hasEdge( n1, n2 ) );
+                    BOOST_CHECK( G.hasEdge( n2, n1 ) );
+                }
+                for( size_t n2 = 0; n2 < G.nrNodes(); n2++ )
+                    if( G.hasEdge( n1, n2 ) ) {
+                        BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ), n2 );
+                        BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ), n1 );
+                        BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ).iter, G.findNb( n1, n2 ) );
+                        BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ).iter, G.findNb( n2, n1 ) );
+                    }
+            }
+            G.checkConsistency();
+            
+            G = createGraphGrid( N1, N2, true );
+            BOOST_CHECK_EQUAL( G.nrNodes(), N1 * N2 );
+            if( N1 == 0 || N2 == 0 )
+                BOOST_CHECK_EQUAL( G.nrEdges(), 0 );
+            else
+                BOOST_CHECK_EQUAL( G.nrEdges(), (N1 <= 2 ? (N1-1) : N1) * N2 + N1 * (N2 <= 2 ? (N2-1) : N2) );
+            BOOST_CHECK( G.isConnected() );
+            BOOST_CHECK_EQUAL( G.isTree(), (G.nrNodes() <= 2) );
+            for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
+                foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
+                    BOOST_CHECK( G.hasEdge( n1, n2 ) );
+                    BOOST_CHECK( G.hasEdge( n2, n1 ) );
+                }
+                for( size_t n2 = 0; n2 < G.nrNodes(); n2++ )
+                    if( G.hasEdge( n1, n2 ) ) {
+                        BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ), n2 );
+                        BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ), n1 );
+                        BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ).iter, G.findNb( n1, n2 ) );
+                        BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ).iter, G.findNb( n2, n1 ) );
+                    }
+            }
+            G.checkConsistency();
+        }
+
+    // createGraphGrid3D
+    for( size_t N1 = 0; N1 < 10; N1++ )
+        for( size_t N2 = 0; N2 < 10; N2++ )
+            for( size_t N3 = 0; N3 < 10; N3++ ) {
+                GraphAL G = createGraphGrid3D( N1, N2, N3, false );
+                BOOST_CHECK_EQUAL( G.nrNodes(), N1 * N2 * N3 );
+                BOOST_CHECK_EQUAL( G.nrEdges(), (N1 > 0 && N2 > 0 && N3 > 0) ? 3 * (N1-1) * (N2-1) * (N3-1) + 2 * (N1-1) * (N2-1) + 2 * (N1-1) * (N3-1) + 2 *  (N2-1) * (N3-1) + (N1-1) + (N2-1) + (N3-1) : 0 );
+                BOOST_CHECK( G.isConnected() );
+                BOOST_CHECK_EQUAL( G.isTree(), (G.nrNodes() == 0) || (N1 <= 1 && N2 <= 1) || (N1 <= 1 && N3 <= 1) || (N2 <= 1 && N3 <= 1) );
+                for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
+                    foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
+                        BOOST_CHECK( G.hasEdge( n1, n2 ) );
+                        BOOST_CHECK( G.hasEdge( n2, n1 ) );
+                    }
+                    for( size_t n2 = 0; n2 < G.nrNodes(); n2++ )
+                        if( G.hasEdge( n1, n2 ) ) {
+                            BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ), n2 );
+                            BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ), n1 );
+                            BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ).iter, G.findNb( n1, n2 ) );
+                            BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ).iter, G.findNb( n2, n1 ) );
+                        }
+                }
+                G.checkConsistency();
+                
+                G = createGraphGrid3D( N1, N2, N3, true );
+                BOOST_CHECK_EQUAL( G.nrNodes(), N1 * N2 * N3 );
+                if( N1 == 0 || N2 == 0 || N3 == 0 )
+                    BOOST_CHECK_EQUAL( G.nrEdges(), 0 );
+                else
+                    BOOST_CHECK_EQUAL( G.nrEdges(), (N1 <= 2 ? (N1-1) : N1) * N2 * N3 + N1 * (N2 <= 2 ? (N2-1) : N2) * N3 + N1 * N2 * (N3 <= 2 ? (N3-1) : N3) );
+                BOOST_CHECK( G.isConnected() );
+                BOOST_CHECK_EQUAL( G.isTree(), (G.nrNodes() <= 2) );
+                for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
+                    foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
+                        BOOST_CHECK( G.hasEdge( n1, n2 ) );
+                        BOOST_CHECK( G.hasEdge( n2, n1 ) );
+                    }
+                    for( size_t n2 = 0; n2 < G.nrNodes(); n2++ )
+                        if( G.hasEdge( n1, n2 ) ) {
+                            BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ), n2 );
+                            BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ), n1 );
+                            BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ).iter, G.findNb( n1, n2 ) );
+                            BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ).iter, G.findNb( n2, n1 ) );
+                        }
+                }
+                G.checkConsistency();
+            }
+
+    // createGraphLoop
+    for( size_t N = 0; N < 100; N++ ) {
+        GraphAL G = createGraphLoop( N );
+        BOOST_CHECK_EQUAL( G.nrNodes(), N );
+        if( N == 0 )
+            BOOST_CHECK_EQUAL( G.nrEdges(), 0 );
+        else if( N <= 2 )
+            BOOST_CHECK_EQUAL( G.nrEdges(), N-1 );
+        else
+            BOOST_CHECK_EQUAL( G.nrEdges(), N );
+        BOOST_CHECK( G.isConnected() );
+        BOOST_CHECK_EQUAL( G.isTree(), N <= 2 );
+        for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
+            foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
+                BOOST_CHECK( G.hasEdge( n1, n2 ) );
+                BOOST_CHECK( G.hasEdge( n2, n1 ) );
+            }
+            for( size_t n2 = 0; n2 < G.nrNodes(); n2++ )
+                if( G.hasEdge( n1, n2 ) ) {
+                    BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ), n2 );
+                    BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ), n1 );
+                    BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ).iter, G.findNb( n1, n2 ) );
+                    BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ).iter, G.findNb( n2, n1 ) );
+                }
+        }
+        G.checkConsistency();
+    }
+
+    // createGraphTree
+    for( size_t N = 0; N < 100; N++ ) {
+        GraphAL G = createGraphTree( N );
+        BOOST_CHECK_EQUAL( G.nrNodes(), N );
+        BOOST_CHECK_EQUAL( G.nrEdges(), N > 0 ? N - 1 : N );
+        BOOST_CHECK( G.isConnected() );
+        BOOST_CHECK( G.isTree() );
+        for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
+            foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
+                BOOST_CHECK( G.hasEdge( n1, n2 ) );
+                BOOST_CHECK( G.hasEdge( n2, n1 ) );
+            }
+            for( size_t n2 = 0; n2 < G.nrNodes(); n2++ )
+                if( G.hasEdge( n1, n2 ) ) {
+                    BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ), n2 );
+                    BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ), n1 );
+                    BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ).iter, G.findNb( n1, n2 ) );
+                    BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ).iter, G.findNb( n2, n1 ) );
+                }
+        }
+        G.checkConsistency();
+    }
+
+    // createGraphRegular
+    for( size_t N = 0; N < 100; N++ ) {
+        for( size_t d = 0; d < N && d <= 20; d++ ) {
+            if( (N * d) % 2 == 0 ) {
+                GraphAL G = createGraphRegular( N, d );
+                BOOST_CHECK_EQUAL( G.nrNodes(), N );
+                BOOST_CHECK_EQUAL( G.nrEdges(), d * N / 2 );
+                for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
+                    BOOST_CHECK_EQUAL( G.nb(n1).size(), d );
+                    foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
+                        BOOST_CHECK( G.hasEdge( n1, n2 ) );
+                        BOOST_CHECK( G.hasEdge( n2, n1 ) );
+                    }
+                    for( size_t n2 = 0; n2 < G.nrNodes(); n2++ )
+                        if( G.hasEdge( n1, n2 ) ) {
+                            BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ), n2 );
+                            BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ), n1 );
+                            BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ).iter, G.findNb( n1, n2 ) );
+                            BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ).iter, G.findNb( n2, n1 ) );
+                        }
+                }
+                G.checkConsistency();
+            }
+        }
+    }
+}
+
+
+BOOST_AUTO_TEST_CASE( StreamTest ) {
+    // check printDot
+    GraphAL G( 4 );
+    G.addEdge( 0, 1 );
+    G.addEdge( 0, 2 );
+    G.addEdge( 1, 3 );
+    G.addEdge( 2, 3 );
+    G.addEdge( 2, 2 );
+    G.addEdge( 3, 2 );
+
+    std::stringstream ss;
+    G.printDot( ss );
+
+    std::string s;
+    std::getline( ss, s );
+    BOOST_CHECK_EQUAL( s, "graph G {" );
+    std::getline( ss, s );
+    BOOST_CHECK_EQUAL( s, "node[shape=circle,width=0.4,fixedsize=true];" );
+    std::getline( ss, s );
+    BOOST_CHECK_EQUAL( s, "\tx0;" );
+    std::getline( ss, s );
+    BOOST_CHECK_EQUAL( s, "\tx1;" );
+    std::getline( ss, s );
+    BOOST_CHECK_EQUAL( s, "\tx2;" );
+    std::getline( ss, s );
+    BOOST_CHECK_EQUAL( s, "\tx3;" );
+    std::getline( ss, s );
+    BOOST_CHECK_EQUAL( s, "\tx0 -- x1;" );
+    std::getline( ss, s );
+    BOOST_CHECK_EQUAL( s, "\tx0 -- x2;" );
+    std::getline( ss, s );
+    BOOST_CHECK_EQUAL( s, "\tx1 -- x3;" );
+    std::getline( ss, s );
+    BOOST_CHECK_EQUAL( s, "\tx2 -- x3;" );
+    std::getline( ss, s );
+    BOOST_CHECK_EQUAL( s, "}" );
+}
index 3cb8152..f385268 100644 (file)
@@ -809,7 +809,7 @@ BOOST_AUTO_TEST_CASE( StreamTest ) {
     std::stringstream ss;
     ss << x << std::endl;
     std::string s;
-    getline( ss, s );
+    std::getline( ss, s );
     BOOST_CHECK_EQUAL( s, "{x1, x2}" );
 }