Improved WeightedGraph code and added unit tests
authorJoris Mooij <joris.mooij@tuebingen.mpg.de>
Wed, 24 Mar 2010 12:41:55 +0000 (13:41 +0100)
committerJoris Mooij <joris.mooij@tuebingen.mpg.de>
Wed, 24 Mar 2010 12:41:55 +0000 (13:41 +0100)
  - Renamed MaxSpanningTreePrims into MaxSpanningTree
  - Renamed MinSpanningTreePrims into MinSpanningTree
  - Added option to MaxSpanningTree and MinSpanningTree for
    choosing between Prim's algorithm and Kruskal's algorithm
  - More error checking in RootedTree constructor

ChangeLog
Makefile
include/dai/weightedgraph.h
src/jtree.cpp
src/treeep.cpp
src/trwbp.cpp
src/weightedgraph.cpp
tests/unit/weightedgraph.cpp [new file with mode: 0644]

index 5e2fe2d..c0eb580 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,6 +1,12 @@
 git HEAD
 --------
 
+* Improved WeightedGraph code:
+  - Renamed MaxSpanningTreePrims into MaxSpanningTree
+  - Renamed MinSpanningTreePrims into MinSpanningTree
+  - Added option to MaxSpanningTree and MinSpanningTree for
+    choosing between Prim's algorithm and Kruskal's algorithm
+  - More error checking in RootedTree constructor
 * Improved BipartiteGraph code:
   - Fixed bug in BipartiteGraph::eraseNode1()
   - Fixed bug in BipartiteGraph::eraseNode2()
@@ -27,7 +33,8 @@ git HEAD
     constructor.
 * Removed RandomDRegularGraph()
 * Compressed Makefile
-* Added unit tests for Var, SmallSet, VarSet, Graph, BipartiteGraph
+* Added unit tests for Var, SmallSet, VarSet, Graph, BipartiteGraph,
+  WeightedGraph
 * Added unit testing framework
 * Added initialization of TRWBP weights by sampling spanning trees
 * Cleaned up MR code:
index 2ea30fa..37767aa 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -122,13 +122,14 @@ 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) tests/unit/graph$(EE) tests/unit/bipgraph$(EE)
+unittests : tests/unit/var$(EE) tests/unit/smallset$(EE) tests/unit/varset$(EE) tests/unit/graph$(EE) tests/unit/bipgraph$(EE) tests/unit/weightedgraph$(EE)
        echo Running unit tests...
        tests/unit/var
        tests/unit/smallset
        tests/unit/varset
        tests/unit/graph
        tests/unit/bipgraph
+       tests/unit/weightedgraph
 
 tests : tests/testdai$(EE) tests/testem/testem$(EE) tests/testbbp$(EE) $(unittests)
 
@@ -200,6 +201,8 @@ tests/unit/graph$(EE) : tests/unit/graph.cpp $(HEADERS) $(LIB)/libdai$(LE)
        $(CC) $(CCO)$@ $< $(LIBS) $(BOOSTLIBS_UTF)
 tests/unit/bipgraph$(EE) : tests/unit/bipgraph.cpp $(HEADERS) $(LIB)/libdai$(LE)
        $(CC) $(CCO)$@ $< $(LIBS) $(BOOSTLIBS_UTF)
+tests/unit/weightedgraph$(EE) : tests/unit/weightedgraph.cpp $(HEADERS) $(LIB)/libdai$(LE)
+       $(CC) $(CCO)$@ $< $(LIBS) $(BOOSTLIBS_UTF)
 
 
 # TESTS
@@ -306,7 +309,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) tests/unit/graph$(EE) tests/unit/bipgraph$(EE)
+       -rm tests/unit/var$(EE) tests/unit/smallset$(EE) tests/unit/varset$(EE) tests/unit/graph$(EE) tests/unit/bipgraph$(EE) tests/unit/weightedgraph$(EE)
        -rm utils/fg2dot$(EE) utils/createfg$(EE) utils/fginfo$(EE)
        -rm -R doc
        -rm -R lib
@@ -338,6 +341,7 @@ clean :
        -del tests\unit\varset$(EE)
        -del tests\unit\graph$(EE)
        -del tests\unit\bipgraph$(EE)
+       -del tests\unit\weightedgraph$(EE)
        -del $(LIB)\libdai$(LE)
        -rmdir lib
 endif
index f8b5bff..8f907db 100644 (file)
 #include <set>
 #include <limits>
 #include <climits>   // Work-around for bug in boost graph library
+#include <dai/util.h>
+#include <dai/exceptions.h>
 
 #include <boost/graph/adjacency_list.hpp>
 #include <boost/graph/prim_minimum_spanning_tree.hpp>
+#include <boost/graph/kruskal_min_spanning_tree.hpp>
 
 
 namespace dai {
@@ -37,13 +40,19 @@ namespace dai {
 class DEdge {
     public:
         /// First node index (source of edge)
-        size_t n1;
+        union {
+            size_t n1;
+            size_t first;   /// alias
+        };
 
-        /// Second node index (sink of edge)
-        size_t n2;
+        /// Second node index (target of edge)
+        union {
+            size_t n2;
+            size_t second;   /// alias
+        };
 
         /// Default constructor
-        DEdge() {}
+        DEdge() : n1(0), n2(0) {}
 
         /// Constructs a directed edge pointing from \a m1 to \a m2
         DEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
@@ -51,9 +60,6 @@ class DEdge {
         /// Tests for equality
         bool operator==( const DEdge &x ) const { return ((n1 == x.n1) && (n2 == x.n2)); }
 
-        /// Tests for inequality
-        bool operator!=( const DEdge &x ) const { return !(*this == x); }
-
         /// Smaller-than operator (performs lexicographical comparison)
         bool operator<( const DEdge &x ) const {
             return( (n1 < x.n1) || ((n1 == x.n1) && (n2 < x.n2)) );
@@ -61,7 +67,7 @@ class DEdge {
 
         /// Writes a directed edge to an output stream
         friend std::ostream & operator << (std::ostream & os, const DEdge & e) {
-            os << "(" << e.n1 << "," << e.n2 << ")";
+            os << "(" << e.n1 << "->" << e.n2 << ")";
             return os;
         }
 };
@@ -82,7 +88,7 @@ class UEdge {
         };
 
         /// Default constructor
-        UEdge() {}
+        UEdge() : n1(0), n2(0) {}
 
         /// Constructs an undirected edge between \a m1 and \a m2
         UEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
@@ -109,9 +115,9 @@ class UEdge {
         /// Writes an undirected edge to an output stream
         friend std::ostream & operator << (std::ostream & os, const UEdge & e) {
             if( e.n1 < e.n2 )
-                os << "{" << e.n1 << "," << e.n2 << "}";
+                os << "{" << e.n1 << "--" << e.n2 << "}";
             else
-                os << "{" << e.n2 << "," << e.n1 << "}";
+                os << "{" << e.n2 << "--" << e.n1 << "}";
             return os;
         }
 };
@@ -123,7 +129,7 @@ class GraphEL : public std::set<UEdge> {
         /// Default constructor
         GraphEL() {}
 
-        /// Construct from range of objects that can be cast to DEdge
+        /// Construct from range of objects that can be cast to UEdge
         template <class InputIterator>
         GraphEL( InputIterator begin, InputIterator end ) {
             insert( begin, end );
@@ -152,52 +158,75 @@ class RootedTree : public std::vector<DEdge> {
 };
 
 
-/// Uses Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph \a G.
-/** Uses implementation in Boost Graph Library.
+/// Constructs a minimum spanning tree from the (non-negatively) weighted graph \a G.
+/** \param usePrim If true, use Prim's algorithm (complexity O(E log(V))), otherwise, use Kruskal's algorithm (complexity O(E log(E)))
+ *  \note Uses implementation from Boost Graph Library.
+ *  \note The vertices of \a G must be in the range [0,N) where N is the number of vertices of \a G.
  */
-template<typename T> RootedTree MinSpanningTreePrims( const WeightedGraph<T> &G ) {
+template<typename T> RootedTree MinSpanningTree( const WeightedGraph<T> &G, bool usePrim ) {
     RootedTree result;
     if( G.size() > 0 ) {
         using namespace boost;
         using namespace std;
-        typedef adjacency_list< vecS, vecS, undirectedS, property<vertex_distance_t, int>, property<edge_weight_t, double> > boostGraph;
-        typedef pair<size_t, size_t> E;
+        typedef adjacency_list< listS, vecS, undirectedS, no_property, property<edge_weight_t, double> > boostGraph;
 
         set<size_t> nodes;
-        vector<E> edges;
+        vector<UEdge> edges;
         vector<double> weights;
         edges.reserve( G.size() );
         weights.reserve( G.size() );
         for( typename WeightedGraph<T>::const_iterator e = G.begin(); e != G.end(); e++ ) {
             weights.push_back( e->second );
-            edges.push_back( E( e->first.n1, e->first.n2 ) );
+            edges.push_back( e->first );
             nodes.insert( e->first.n1 );
             nodes.insert( e->first.n2 );
         }
 
-        boostGraph g( edges.begin(), edges.end(), weights.begin(), nodes.size() );
-        vector< graph_traits< boostGraph >::vertex_descriptor > p( num_vertices(g) );
-        prim_minimum_spanning_tree( g, &(p[0]) );
+        size_t N = nodes.size();
+        for( set<size_t>::const_iterator it = nodes.begin(); it != nodes.end(); it++ )
+            if( *it >= N )
+                DAI_THROWE(RUNTIME_ERROR,"Vertices must be in range [0..N) where N is the number of vertices.");
 
-        // Store tree edges in result
+        boostGraph g( edges.begin(), edges.end(), weights.begin(), nodes.size() );
+        size_t root = *(nodes.begin());
         GraphEL tree;
-        size_t root = 0;
-        for( size_t i = 0; i != p.size(); i++ )
-            if( p[i] != i )
-                tree.insert( UEdge( p[i], i ) );
-            else
-                root = i;
-        // Order them to obtain a rooted tree
+        if( usePrim ) {
+            // Prim's algorithm
+            vector< graph_traits< boostGraph >::vertex_descriptor > p( num_vertices(g) );
+            prim_minimum_spanning_tree( g, &(p[0]) );
+
+            // Store tree edges in result
+            for( size_t i = 0; i != p.size(); i++ ) {
+                if( p[i] != i )
+                    tree.insert( UEdge( p[i], i ) );
+            }
+        } else {
+            // Kruskal's algorithm
+            vector< graph_traits< boostGraph >::edge_descriptor > p( num_vertices(g) );
+            kruskal_minimum_spanning_tree( g, &(p[0]) );
+
+            // Store tree edges in result
+            for( size_t i = 0; i != p.size(); i++ ) {
+                size_t v1 = source( p[i], g );
+                size_t v2 = target( p[i], g );
+                if( v1 != v2 )
+                    tree.insert( UEdge( v1, v2 ) );
+            }
+        }
+
+        // Direct edges in order to obtain a rooted tree
         result = RootedTree( tree, root );
     }
     return result;
 }
 
 
-/// Use Prim's algorithm to construct a maximal spanning tree from the (positively) weighted graph \a G.
-/** Uses implementation in Boost Graph Library.
+/// Constructs a minimum spanning tree from the (non-negatively) weighted graph \a G.
+/** \param usePrim If true, use Prim's algorithm (complexity O(E log(V))), otherwise, use Kruskal's algorithm (complexity O(E log(E)))
+ *  \note Uses implementation from Boost Graph Library.
+ *  \note The vertices of \a G must be in the range [0,N) where N is the number of vertices of \a G.
  */
-template<typename T> RootedTree MaxSpanningTreePrims( const WeightedGraph<T> &G ) {
+template<typename T> RootedTree MaxSpanningTree( const WeightedGraph<T> &G, bool usePrim ) {
     if( G.size() == 0 )
         return RootedTree();
     else {
@@ -207,11 +236,11 @@ template<typename T> RootedTree MaxSpanningTreePrims( const WeightedGraph<T> &G
                 maxweight = it->second;
         // make a copy of the graph
         WeightedGraph<T> gr( G );
-        // invoke MinSpanningTreePrims with negative weights
+        // invoke MinSpanningTree with negative weights
         // (which have to be shifted to satisfy positivity criterion)
         for( typename WeightedGraph<T>::iterator it = gr.begin(); it != gr.end(); it++ )
             it->second = maxweight - it->second;
-        return MinSpanningTreePrims( gr );
+        return MinSpanningTree( gr, usePrim );
     }
 }
 
index 8b7fd75..7e4eea6 100644 (file)
@@ -123,7 +123,7 @@ void JTree::construct( const std::vector<VarSet> &cl, bool verify ) {
         }
 
     // Construct maximal spanning tree using Prim's algorithm
-    RTree = MaxSpanningTreePrims( JuncGraph );
+    RTree = MaxSpanningTree( JuncGraph, true );
 
     // Construct corresponding region graph
 
index 5c9f369..68f0ecc 100644 (file)
@@ -109,7 +109,7 @@ TreeEP::TreeEP( const FactorGraph &fg, const PropertySet &opts ) : JTree(fg, opt
             }
 
             // find maximal spanning tree
-            construct( MaxSpanningTreePrims( wg ) );
+            construct( MaxSpanningTree( wg, true ) );
         } else
             DAI_THROW(UNKNOWN_ENUM_VALUE);
     }
index 3184376..95032b0 100644 (file)
@@ -184,7 +184,7 @@ void TRWBP::sampleWeights( size_t nrTrees ) {
     // now repeatedly change the random weights, find the minimal spanning tree, and add it to the weights
     for( size_t nr = 0; nr < nrTrees; nr++ ) {
         // find minimal spanning tree
-        RootedTree randTree = MinSpanningTreePrims( wg );
+        RootedTree randTree = MinSpanningTree( wg, true );
         // add it to the weights
         addTreeToWeights( randTree );
         // resample weights of the graph
index 3c45bdd..703e5e1 100644 (file)
@@ -29,30 +29,48 @@ RootedTree::RootedTree( const GraphEL &T, size_t Root ) {
         // Nodes in the tree
         set<size_t> nodes;
 
+        // Check whether the root is in the tree
+        bool valid = false;
+        for( GraphEL::iterator e = Gr.begin(); e != Gr.end() && !valid; e++ )
+            if( e->n1 == Root || e->n2 == Root )
+                valid = true;
+        if( !valid )
+            DAI_THROWE(RUNTIME_ERROR,"Graph does not contain specified root.");
+
         // Start with the root
         nodes.insert( Root );
 
         // Keep adding edges until done
-        while( !(Gr.empty()) )
+        bool done = false;
+        while( !done ) {
+            bool changed = false;
             for( GraphEL::iterator e = Gr.begin(); e != Gr.end(); ) {
                 bool e1_in_nodes = nodes.count( e->n1 );
                 bool e2_in_nodes = nodes.count( e->n2 );
-                DAI_ASSERT( !(e1_in_nodes && e2_in_nodes) );
+                if( e1_in_nodes && e2_in_nodes )
+                    DAI_THROWE(RUNTIME_ERROR,"Graph is not acyclic.");
                 if( e1_in_nodes ) {
                     // Add directed edge, pointing away from the root
                     push_back( DEdge( e->n1, e->n2 ) );
                     nodes.insert( e->n2 );
                     // Erase the edge
                     Gr.erase( e++ );
+                    changed = true;
                 } else if( e2_in_nodes ) {
                     // Add directed edge, pointing away from the root
                     push_back( DEdge( e->n2, e->n1 ) );
                     nodes.insert( e->n1 );
                     // Erase the edge
                     Gr.erase( e++ );
+                    changed = true;
                 } else
                     e++;
             }
+            if( Gr.empty() )
+                done = true;
+            if( !changed && !done )
+                DAI_THROWE(RUNTIME_ERROR,"Graph is not connected.");
+        }
     }
 }
 
diff --git a/tests/unit/weightedgraph.cpp b/tests/unit/weightedgraph.cpp
new file mode 100644 (file)
index 0000000..73bef82
--- /dev/null
@@ -0,0 +1,255 @@
+/*  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/weightedgraph.h>
+#include <dai/exceptions.h>
+#include <strstream>
+#include <vector>
+
+
+using namespace dai;
+
+
+#define BOOST_TEST_MODULE WeighedGraphTest
+
+
+#include <boost/test/unit_test.hpp>
+
+
+BOOST_AUTO_TEST_CASE( DEdgeTest ) {
+    DEdge a;
+    BOOST_CHECK_EQUAL( a.n1, 0 );
+    BOOST_CHECK_EQUAL( a.n2, 0 );
+    DEdge b( 3, 5 );
+    BOOST_CHECK_EQUAL( b.n1, 3 );
+    BOOST_CHECK_EQUAL( b.n2, 5 );
+    DEdge c( 5, 3 );
+    BOOST_CHECK_EQUAL( c.n1, 5 );
+    BOOST_CHECK_EQUAL( c.n2, 3 );
+    DEdge d( c );
+    DEdge e = c;
+    DEdge f( 5, 4 );
+    DEdge g( 3, 6 );
+
+    BOOST_CHECK( !(a == b) );
+    BOOST_CHECK( !(a == c) );
+    BOOST_CHECK( !(b == c) );
+    BOOST_CHECK( d == c );
+    BOOST_CHECK( c == d );
+    BOOST_CHECK( e == c );
+    BOOST_CHECK( c == e );
+    BOOST_CHECK( d == e );
+    BOOST_CHECK( e == d );
+
+    BOOST_CHECK( a < b );
+    BOOST_CHECK( a < c );
+    BOOST_CHECK( b < c );
+    BOOST_CHECK( !(c < d) );
+    BOOST_CHECK( !(b < a) );
+    BOOST_CHECK( !(c < a) );
+    BOOST_CHECK( !(c < b) );
+    BOOST_CHECK( !(d < c) );
+    BOOST_CHECK( a < f );
+    BOOST_CHECK( b < f );
+    BOOST_CHECK( c < f );
+    BOOST_CHECK( g < f );
+    BOOST_CHECK( !(f < a) );
+    BOOST_CHECK( !(f < b) );
+    BOOST_CHECK( !(f < c) );
+    BOOST_CHECK( !(f < g) );
+    BOOST_CHECK( a < g );
+    BOOST_CHECK( b < g );
+    BOOST_CHECK( !(c < g) );
+    BOOST_CHECK( !(g < a) );
+    BOOST_CHECK( !(g < b) );
+    BOOST_CHECK( g < c );
+
+    std::stringstream ss;
+    ss << c;
+    std::string s;
+    ss >> s;
+    BOOST_CHECK_EQUAL( s, "(5->3)" );
+}
+
+
+BOOST_AUTO_TEST_CASE( UEdgeTest ) {
+    UEdge a;
+    BOOST_CHECK_EQUAL( a.n1, 0 );
+    BOOST_CHECK_EQUAL( a.n2, 0 );
+    UEdge b( 3, 5 );
+    BOOST_CHECK_EQUAL( b.n1, 3 );
+    BOOST_CHECK_EQUAL( b.n2, 5 );
+    UEdge c( 5, 3 );
+    BOOST_CHECK_EQUAL( c.n1, 5 );
+    BOOST_CHECK_EQUAL( c.n2, 3 );
+    UEdge d( c );
+    UEdge e = c;
+    UEdge f( 5, 4 );
+    UEdge g( 3, 6 );
+
+    UEdge h( DEdge( 5, 3 ) );
+    BOOST_CHECK_EQUAL( h.n1, 5 );
+    BOOST_CHECK_EQUAL( h.n2, 3 );
+
+    BOOST_CHECK( !(a == b) );
+    BOOST_CHECK( !(a == c) );
+    BOOST_CHECK( b == c );
+    BOOST_CHECK( d == c );
+    BOOST_CHECK( c == d );
+    BOOST_CHECK( e == c );
+    BOOST_CHECK( c == e );
+    BOOST_CHECK( d == e );
+    BOOST_CHECK( e == d );
+
+    BOOST_CHECK( a < b );
+    BOOST_CHECK( a < c );
+    BOOST_CHECK( !(b < c) );
+    BOOST_CHECK( !(c < d) );
+    BOOST_CHECK( !(b < a) );
+    BOOST_CHECK( !(c < a) );
+    BOOST_CHECK( !(c < b) );
+    BOOST_CHECK( !(d < c) );
+    BOOST_CHECK( a < f );
+    BOOST_CHECK( b < f );
+    BOOST_CHECK( c < f );
+    BOOST_CHECK( g < f );
+    BOOST_CHECK( !(f < a) );
+    BOOST_CHECK( !(f < b) );
+    BOOST_CHECK( !(f < c) );
+    BOOST_CHECK( !(f < g) );
+    BOOST_CHECK( a < g );
+    BOOST_CHECK( b < g );
+    BOOST_CHECK( c < g );
+    BOOST_CHECK( !(g < a) );
+    BOOST_CHECK( !(g < b) );
+    BOOST_CHECK( !(g < c) );
+
+    std::stringstream ss;
+    std::string s;
+    ss << c;
+    ss >> s;
+    BOOST_CHECK_EQUAL( s, "{3--5}" );
+    ss << b;
+    ss >> s;
+    BOOST_CHECK_EQUAL( s, "{3--5}" );
+}
+
+
+BOOST_AUTO_TEST_CASE( RootedTreeTest ) {
+    typedef UEdge E;
+    std::vector<E> edges;
+    edges.push_back( E( 1, 2 ) );
+    edges.push_back( E( 2, 3 ) );
+    edges.push_back( E( 3, 1 ) );
+    GraphEL G( edges.begin(), edges.end() );
+    
+    bool thrown = false;
+    try {
+        RootedTree T( G, 0 );
+    } catch( Exception &e ) {
+        if( e.code() == Exception::RUNTIME_ERROR )
+            thrown = true;
+        else
+            throw;
+    }
+    BOOST_CHECK( thrown );
+
+    thrown = false;
+    try {
+        RootedTree T( G, 1 );
+    } catch( Exception &e ) {
+        if( e.code() == Exception::RUNTIME_ERROR )
+            thrown = true;
+        else
+            throw;
+    }
+    BOOST_CHECK( thrown );
+
+    edges.back().n2 = 4;
+    G = GraphEL( edges.begin(), edges.end() );
+    thrown = false;
+    RootedTree T;
+    try {
+        T = RootedTree( G, 1 );
+    } catch( Exception &e ) {
+        if( e.code() == Exception::RUNTIME_ERROR )
+            thrown = true;
+        else
+            throw;
+    }
+    BOOST_CHECK( !thrown );
+    BOOST_CHECK_EQUAL( T.size(), 3 );
+    BOOST_CHECK_EQUAL( T[0], DEdge( 1, 2 ) );
+    BOOST_CHECK_EQUAL( T[1], DEdge( 2, 3 ) );
+    BOOST_CHECK_EQUAL( T[2], DEdge( 3, 4 ) );
+
+    edges.push_back( E(5, 6) );
+    G = GraphEL( edges.begin(), edges.end() );
+    thrown = false;
+    try {
+        RootedTree T( G, 1 );
+    } catch( Exception &e ) {
+        if( e.code() == Exception::RUNTIME_ERROR )
+            thrown = true;
+        else
+            throw;
+    }
+    BOOST_CHECK( thrown );
+}
+
+
+BOOST_AUTO_TEST_CASE( SpanningTreeTest ) {
+    RootedTree T;
+    WeightedGraph<int> G;
+    G[UEdge(0,1)] = 1;
+    G[UEdge(0,2)] = 2;
+    G[UEdge(1,2)] = 3;
+    G[UEdge(1,3)] = 4;
+    G[UEdge(2,3)] = 5;
+   
+    RootedTree TMin;
+    TMin.push_back( DEdge( 0,1 ) );
+    TMin.push_back( DEdge( 0,2 ) );
+    TMin.push_back( DEdge( 1,3 ) );
+    RootedTree TMax;
+    TMax.push_back( DEdge( 0,2 ) );
+    TMax.push_back( DEdge( 2,3 ) );
+    TMax.push_back( DEdge( 3,1 ) );
+
+    T = MinSpanningTree( G, true );
+    BOOST_CHECK_EQUAL( T, TMin );
+    T = MinSpanningTree( G, false );
+    BOOST_CHECK_EQUAL( T, TMin );
+
+    T = MaxSpanningTree( G, true );
+    BOOST_CHECK_EQUAL( T, TMax );
+    T = MaxSpanningTree( G, false );
+    BOOST_CHECK_EQUAL( T, TMax );
+
+    WeightedGraph<double> H;
+    H[UEdge(1,2)] = 1;
+    H[UEdge(1,3)] = 2;
+    H[UEdge(2,3)] = 3;
+    H[UEdge(2,4)] = 4;
+    H[UEdge(3,4)] = 5;
+    bool thrown = false;
+    try {
+        T = MinSpanningTree( H, true );
+    } catch( Exception &e ) {
+        if( e.code() == Exception::RUNTIME_ERROR )
+            thrown = true;
+        else
+            throw;
+    }
+    BOOST_CHECK( thrown );
+}