Fixed a bug in the Kruskal part of MinSpanningTree
authorJoris Mooij <joris.mooij@tuebingen.mpg.de>
Thu, 25 Mar 2010 09:12:58 +0000 (10:12 +0100)
committerJoris Mooij <joris.mooij@tuebingen.mpg.de>
Thu, 25 Mar 2010 09:12:58 +0000 (10:12 +0100)
ChangeLog
include/dai/weightedgraph.h
src/jtree.cpp
src/treeep.cpp
src/trwbp.cpp
src/weightedgraph.cpp
tests/unit/weightedgraph.cpp

index 100f69f..810817f 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -10,6 +10,8 @@ git HEAD
   - Added option to MaxSpanningTree and MinSpanningTree for
     choosing between Prim's algorithm and Kruskal's algorithm
   - More error checking in RootedTree constructor
+  - The vertices in DEdge and UEdge are now named "first" and "second"
+    for compatibility with a std::pair<size_t,size_t>
 * Improved bipgraph.h/cpp:
   - Fixed bug in BipartiteGraph::eraseNode1()
   - Fixed bug in BipartiteGraph::eraseNode2()
index 8f907db..af6384b 100644 (file)
@@ -40,34 +40,28 @@ namespace dai {
 class DEdge {
     public:
         /// First node index (source of edge)
-        union {
-            size_t n1;
-            size_t first;   /// alias
-        };
+        size_t first;
 
         /// Second node index (target of edge)
-        union {
-            size_t n2;
-            size_t second;   /// alias
-        };
+        size_t second;
 
         /// Default constructor
-        DEdge() : n1(0), n2(0) {}
+        DEdge() : first(0), second(0) {}
 
         /// Constructs a directed edge pointing from \a m1 to \a m2
-        DEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
+        DEdge( size_t m1, size_t m2 ) : first(m1), second(m2) {}
 
         /// Tests for equality
-        bool operator==( const DEdge &x ) const { return ((n1 == x.n1) && (n2 == x.n2)); }
+        bool operator==( const DEdge &x ) const { return ((first == x.first) && (second == x.second)); }
 
         /// Smaller-than operator (performs lexicographical comparison)
         bool operator<( const DEdge &x ) const {
-            return( (n1 < x.n1) || ((n1 == x.n1) && (n2 < x.n2)) );
+            return( (first < x.first) || ((first == x.first) && (second < x.second)) );
         }
 
         /// 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.first << "->" << e.second << ")";
             return os;
         }
 };
@@ -77,47 +71,40 @@ class DEdge {
 class UEdge {
     public:
         /// First node index
-        union {
-            size_t n1;
-            size_t first;   /// alias
-        };
+        size_t first;
+
         /// Second node index
-        union {
-            size_t n2;
-            size_t second;  /// alias
-        };
+        size_t second;
 
         /// Default constructor
-        UEdge() : n1(0), n2(0) {}
+        UEdge() : first(0), second(0) {}
 
         /// Constructs an undirected edge between \a m1 and \a m2
-        UEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
+        UEdge( size_t m1, size_t m2 ) : first(m1), second(m2) {}
 
         /// Construct from DEdge
-        UEdge( const DEdge &e ) : n1(e.n1), n2(e.n2) {}
+        UEdge( const DEdge &e ) : first(e.first), second(e.second) {}
 
         /// Tests for inequality (disregarding the ordering of the nodes)
         bool operator==( const UEdge &x ) {
-            return ((n1 == x.n1) && (n2 == x.n2)) || ((n1 == x.n2) && (n2 == x.n1));
+            return ((first == x.first) && (second == x.second)) || ((first == x.second) && (second == x.first));
         }
 
         /// Smaller-than operator
         bool operator<( const UEdge &x ) const {
-            size_t s = n1, l = n2;
-            if( s > l )
-                std::swap( s, l );
-            size_t xs = x.n1, xl = x.n2;
-            if( xs > xl )
-                std::swap( xs, xl );
+            size_t s = std::min( first, second );
+            size_t l = std::max( first, second );
+            size_t xs = std::min( x.first, x.second );
+            size_t xl = std::max( x.first, x.second );
             return( (s < xs) || ((s == xs) && (l < xl)) );
         }
 
         /// 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 << "}";
+            if( e.first < e.second )
+                os << "{" << e.first << "--" << e.second << "}";
             else
-                os << "{" << e.n2 << "--" << e.n1 << "}";
+                os << "{" << e.second << "--" << e.first << "}";
             return os;
         }
 };
@@ -168,7 +155,7 @@ template<typename T> RootedTree MinSpanningTree( const WeightedGraph<T> &G, bool
     if( G.size() > 0 ) {
         using namespace boost;
         using namespace std;
-        typedef adjacency_list< listS, vecS, undirectedS, no_property, property<edge_weight_t, double> > boostGraph;
+        typedef adjacency_list< vecS, vecS, undirectedS, no_property, property<edge_weight_t, double> > boostGraph;
 
         set<size_t> nodes;
         vector<UEdge> edges;
@@ -178,8 +165,8 @@ template<typename T> RootedTree MinSpanningTree( const WeightedGraph<T> &G, bool
         for( typename WeightedGraph<T>::const_iterator e = G.begin(); e != G.end(); e++ ) {
             weights.push_back( e->second );
             edges.push_back( e->first );
-            nodes.insert( e->first.n1 );
-            nodes.insert( e->first.n2 );
+            nodes.insert( e->first.first );
+            nodes.insert( e->first.second );
         }
 
         size_t N = nodes.size();
@@ -192,7 +179,7 @@ template<typename T> RootedTree MinSpanningTree( const WeightedGraph<T> &G, bool
         GraphEL tree;
         if( usePrim ) {
             // Prim's algorithm
-            vector< graph_traits< boostGraph >::vertex_descriptor > p( num_vertices(g) );
+            vector< graph_traits< boostGraph >::vertex_descriptor > p(N);
             prim_minimum_spanning_tree( g, &(p[0]) );
 
             // Store tree edges in result
@@ -202,13 +189,14 @@ template<typename T> RootedTree MinSpanningTree( const WeightedGraph<T> &G, bool
             }
         } else {
             // Kruskal's algorithm
-            vector< graph_traits< boostGraph >::edge_descriptor > p( num_vertices(g) );
-            kruskal_minimum_spanning_tree( g, &(p[0]) );
+            vector< graph_traits< boostGraph >::edge_descriptor > t;
+            t.reserve(  N - 1 );
+            kruskal_minimum_spanning_tree( g, std::back_inserter(t) );
 
             // 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 );
+            for( size_t i = 0; i != t.size(); i++ ) {
+                size_t v1 = source( t[i], g );
+                size_t v2 = target( t[i], g );
                 if( v1 != v2 )
                     tree.insert( UEdge( v1, v2 ) );
             }
index 7e4eea6..294e72e 100644 (file)
@@ -155,10 +155,10 @@ void JTree::construct( const std::vector<VarSet> &cl, bool verify ) {
     vector<Edge> edges;
     edges.reserve( 2 * RTree.size() );
     for( size_t i = 0; i < RTree.size(); i++ ) {
-        edges.push_back( Edge( RTree[i].n1, nrIRs() ) );
-        edges.push_back( Edge( RTree[i].n2, nrIRs() ) );
+        edges.push_back( Edge( RTree[i].first, nrIRs() ) );
+        edges.push_back( Edge( RTree[i].second, nrIRs() ) );
         // inner clusters have counting number -1
-        IRs.push_back( Region( cl[RTree[i].n1] & cl[RTree[i].n2], -1.0 ) );
+        IRs.push_back( Region( cl[RTree[i].first] & cl[RTree[i].second], -1.0 ) );
     }
 
     // create bipartite graph
@@ -246,34 +246,34 @@ void JTree::runHUGIN() {
     // CollectEvidence
     _logZ = 0.0;
     for( size_t i = RTree.size(); (i--) != 0; ) {
-//      Make outer region RTree[i].n1 consistent with outer region RTree[i].n2
-//      IR(i) = seperator OR(RTree[i].n1) && OR(RTree[i].n2)
+//      Make outer region RTree[i].first consistent with outer region RTree[i].second
+//      IR(i) = seperator OR(RTree[i].first) && OR(RTree[i].second)
         Factor new_Qb;
         if( props.inference == Properties::InfType::SUMPROD )
-            new_Qb = Qa[RTree[i].n2].marginal( IR( i ), false );
+            new_Qb = Qa[RTree[i].second].marginal( IR( i ), false );
         else
-            new_Qb = Qa[RTree[i].n2].maxMarginal( IR( i ), false );
+            new_Qb = Qa[RTree[i].second].maxMarginal( IR( i ), false );
 
         _logZ += log(new_Qb.normalize());
-        Qa[RTree[i].n1] *= new_Qb / Qb[i];
+        Qa[RTree[i].first] *= new_Qb / Qb[i];
         Qb[i] = new_Qb;
     }
     if( RTree.empty() )
         _logZ += log(Qa[0].normalize() );
     else
-        _logZ += log(Qa[RTree[0].n1].normalize());
+        _logZ += log(Qa[RTree[0].first].normalize());
 
     // DistributeEvidence
     for( size_t i = 0; i < RTree.size(); i++ ) {
-//      Make outer region RTree[i].n2 consistent with outer region RTree[i].n1
-//      IR(i) = seperator OR(RTree[i].n1) && OR(RTree[i].n2)
+//      Make outer region RTree[i].second consistent with outer region RTree[i].first
+//      IR(i) = seperator OR(RTree[i].first) && OR(RTree[i].second)
         Factor new_Qb;
         if( props.inference == Properties::InfType::SUMPROD )
-            new_Qb = Qa[RTree[i].n1].marginal( IR( i ) );
+            new_Qb = Qa[RTree[i].first].marginal( IR( i ) );
         else
-            new_Qb = Qa[RTree[i].n1].maxMarginal( IR( i ) );
+            new_Qb = Qa[RTree[i].first].maxMarginal( IR( i ) );
 
-        Qa[RTree[i].n2] *= new_Qb / Qb[i];
+        Qa[RTree[i].second] *= new_Qb / Qb[i];
         Qb[i] = new_Qb;
     }
 
@@ -287,11 +287,11 @@ void JTree::runShaferShenoy() {
     // First pass
     _logZ = 0.0;
     for( size_t e = nrIRs(); (e--) != 0; ) {
-        // send a message from RTree[e].n2 to RTree[e].n1
-        // or, actually, from the seperator IR(e) to RTree[e].n1
+        // send a message from RTree[e].second to RTree[e].first
+        // or, actually, from the seperator IR(e) to RTree[e].first
 
-        size_t i = nbIR(e)[1].node; // = RTree[e].n2
-        size_t j = nbIR(e)[0].node; // = RTree[e].n1
+        size_t i = nbIR(e)[1].node; // = RTree[e].second
+        size_t j = nbIR(e)[0].node; // = RTree[e].first
         size_t _e = nbIR(e)[0].dual;
 
         Factor msg = OR(i);
@@ -307,8 +307,8 @@ void JTree::runShaferShenoy() {
 
     // Second pass
     for( size_t e = 0; e < nrIRs(); e++ ) {
-        size_t i = nbIR(e)[0].node; // = RTree[e].n1
-        size_t j = nbIR(e)[1].node; // = RTree[e].n2
+        size_t i = nbIR(e)[0].node; // = RTree[e].first
+        size_t j = nbIR(e)[1].node; // = RTree[e].second
         size_t _e = nbIR(e)[1].dual;
 
         Factor msg = OR(i);
@@ -329,7 +329,7 @@ void JTree::runShaferShenoy() {
         if( nrIRs() == 0 ) {
             _logZ += log( piet.normalize() );
             Qa[alpha] = piet;
-        } else if( alpha == nbIR(0)[0].node /*RTree[0].n1*/ ) {
+        } else if( alpha == nbIR(0)[0].node /*RTree[0].first*/ ) {
             _logZ += log( piet.normalize() );
             Qa[alpha] = piet;
         } else
@@ -388,14 +388,14 @@ size_t JTree::findEfficientTree( const VarSet& vs, RootedTree &Tree, size_t Prev
     // for each variable in vs
     for( VarSet::const_iterator n = vs.begin(); n != vs.end(); n++ ) {
         for( size_t e = 0; e < newTree.size(); e++ ) {
-            if( OR(newTree[e].n2).vars().contains( *n ) ) {
+            if( OR(newTree[e].second).vars().contains( *n ) ) {
                 size_t f = e;
                 subTree.insert( newTree[f] );
-                size_t pos = newTree[f].n1;
+                size_t pos = newTree[f].first;
                 for( ; f > 0; f-- )
-                    if( newTree[f-1].n2 == pos ) {
+                    if( newTree[f-1].second == pos ) {
                         subTree.insert( newTree[f-1] );
-                        pos = newTree[f-1].n1;
+                        pos = newTree[f-1].first;
                     }
             }
         }
@@ -404,18 +404,18 @@ size_t JTree::findEfficientTree( const VarSet& vs, RootedTree &Tree, size_t Prev
         // find first occurence of PreviousRoot in the tree, which is closest to the new root
         size_t e = 0;
         for( ; e != newTree.size(); e++ ) {
-            if( newTree[e].n2 == PreviousRoot )
+            if( newTree[e].second == PreviousRoot )
                 break;
         }
         DAI_ASSERT( e != newTree.size() );
 
         // track-back path to root and add edges to subTree
         subTree.insert( newTree[e] );
-        size_t pos = newTree[e].n1;
+        size_t pos = newTree[e].first;
         for( ; e > 0; e-- )
-            if( newTree[e-1].n2 == pos ) {
+            if( newTree[e-1].second == pos ) {
                 subTree.insert( newTree[e-1] );
-                pos = newTree[e-1].n1;
+                pos = newTree[e-1].first;
             }
     }
 
@@ -456,7 +456,7 @@ Factor JTree::calcMarginal( const VarSet& vs ) {
             size_t Tsize = findEfficientTree( vs, T );
 
             // Find remaining variables (which are not in the new root)
-            VarSet vsrem = vs / OR(T.front().n1).vars();
+            VarSet vsrem = vs / OR(T.front().first).vars();
             Factor Pvs (vs, 0.0);
 
             // Save Qa and Qb on the subtree
@@ -464,11 +464,11 @@ Factor JTree::calcMarginal( const VarSet& vs ) {
             map<size_t,Factor> Qb_old;
             vector<size_t> b(Tsize, 0);
             for( size_t i = Tsize; (i--) != 0; ) {
-                size_t alpha1 = T[i].n1;
-                size_t alpha2 = T[i].n2;
+                size_t alpha1 = T[i].first;
+                size_t alpha2 = T[i].second;
                 size_t beta;
                 for( beta = 0; beta < nrIRs(); beta++ )
-                    if( UEdge( RTree[beta].n1, RTree[beta].n2 ) == UEdge( alpha1, alpha2 ) )
+                    if( UEdge( RTree[beta].first, RTree[beta].second ) == UEdge( alpha1, alpha2 ) )
                         break;
                 DAI_ASSERT( beta != nrIRs() );
                 b[i] = beta;
@@ -486,26 +486,26 @@ Factor JTree::calcMarginal( const VarSet& vs ) {
                 // CollectEvidence
                 Real logZ = 0.0;
                 for( size_t i = Tsize; (i--) != 0; ) {
-                // Make outer region T[i].n1 consistent with outer region T[i].n2
-                // IR(i) = seperator OR(T[i].n1) && OR(T[i].n2)
+                // Make outer region T[i].first consistent with outer region T[i].second
+                // IR(i) = seperator OR(T[i].first) && OR(T[i].second)
 
                     for( VarSet::const_iterator n = vsrem.begin(); n != vsrem.end(); n++ )
-                        if( Qa[T[i].n2].vars() >> *n ) {
+                        if( Qa[T[i].second].vars() >> *n ) {
                             Factor piet( *n, 0.0 );
                             piet[s(*n)] = 1.0;
-                            Qa[T[i].n2] *= piet;
+                            Qa[T[i].second] *= piet;
                         }
 
-                    Factor new_Qb = Qa[T[i].n2].marginal( IR( b[i] ), false );
+                    Factor new_Qb = Qa[T[i].second].marginal( IR( b[i] ), false );
                     logZ += log(new_Qb.normalize());
-                    Qa[T[i].n1] *= new_Qb / Qb[b[i]];
+                    Qa[T[i].first] *= new_Qb / Qb[b[i]];
                     Qb[b[i]] = new_Qb;
                 }
-                logZ += log(Qa[T[0].n1].normalize());
+                logZ += log(Qa[T[0].first].normalize());
 
                 Factor piet( vsrem, 0.0 );
                 piet[s] = exp(logZ);
-                Pvs += piet * Qa[T[0].n1].marginal( vs / vsrem, false );      // OPTIMIZE ME
+                Pvs += piet * Qa[T[0].first].marginal( vs / vsrem, false );      // OPTIMIZE ME
 
                 // Restore clamped beliefs
                 for( map<size_t,Factor>::const_iterator alpha = Qa_old.begin(); alpha != Qa_old.end(); alpha++ )
index 68f0ecc..9edb75d 100644 (file)
@@ -119,7 +119,7 @@ TreeEP::TreeEP( const FactorGraph &fg, const PropertySet &opts ) : JTree(fg, opt
 void TreeEP::construct( const RootedTree &tree ) {
     vector<VarSet> cl;
     for( size_t i = 0; i < tree.size(); i++ )
-        cl.push_back( VarSet( var(tree[i].n1), var(tree[i].n2) ) );
+        cl.push_back( VarSet( var(tree[i].first), var(tree[i].second) ) );
 
     // If no outer region can be found subsuming that factor, label the
     // factor as off-tree.
@@ -140,7 +140,7 @@ void TreeEP::construct( const RootedTree &tree ) {
                 // find efficient subtree
                 RootedTree subTree;
                 size_t subTreeSize = findEfficientTree( factor(I).vars(), subTree, PreviousRoot );
-                PreviousRoot = subTree[0].n1;
+                PreviousRoot = subTree[0].first;
                 subTree.resize( subTreeSize );
                 if( props.verbose >= 1 )
                     cerr << "Subtree " << I << " has size " << subTreeSize << endl;
@@ -252,11 +252,11 @@ TreeEP::TreeEPSubTree::TreeEPSubTree( const RootedTree &subRTree, const RootedTr
     _Qb.reserve( subRTree.size() );
     _RTree.reserve( subRTree.size() );
     for( size_t i = 0; i < subRTree.size(); i++ ) {
-        size_t alpha1 = subRTree[i].n1;     // old index 1
-        size_t alpha2 = subRTree[i].n2;     // old index 2
+        size_t alpha1 = subRTree[i].first;  // old index 1
+        size_t alpha2 = subRTree[i].second; // old index 2
         size_t beta;                        // old sep index
         for( beta = 0; beta < jt_RTree.size(); beta++ )
-            if( UEdge( jt_RTree[beta].n1, jt_RTree[beta].n2 ) == UEdge( alpha1, alpha2 ) )
+            if( UEdge( jt_RTree[beta].first, jt_RTree[beta].second ) == UEdge( alpha1, alpha2 ) )
                 break;
         DAI_ASSERT( beta != jt_RTree.size() );
 
@@ -319,20 +319,20 @@ void TreeEP::TreeEPSubTree::HUGIN_with_I( std::vector<Factor> &Qa, std::vector<F
         for( size_t i = _RTree.size(); (i--) != 0; ) {
             // clamp variables in nsrem
             for( VarSet::const_iterator n = _nsrem.begin(); n != _nsrem.end(); n++ )
-                if( _Qa[_RTree[i].n2].vars() >> *n ) {
+                if( _Qa[_RTree[i].second].vars() >> *n ) {
                     Factor delta( *n, 0.0 );
                     delta[s(*n)] = 1.0;
-                    _Qa[_RTree[i].n2] *= delta;
+                    _Qa[_RTree[i].second] *= delta;
                 }
-            Factor new_Qb = _Qa[_RTree[i].n2].marginal( _Qb[i].vars(), false );
-            _Qa[_RTree[i].n1] *= new_Qb / _Qb[i];
+            Factor new_Qb = _Qa[_RTree[i].second].marginal( _Qb[i].vars(), false );
+            _Qa[_RTree[i].first] *= new_Qb / _Qb[i];
             _Qb[i] = new_Qb;
         }
 
         // DistributeEvidence
         for( size_t i = 0; i < _RTree.size(); i++ ) {
-            Factor new_Qb = _Qa[_RTree[i].n1].marginal( _Qb[i].vars(), false );
-            _Qa[_RTree[i].n2] *= new_Qb / _Qb[i];
+            Factor new_Qb = _Qa[_RTree[i].first].marginal( _Qb[i].vars(), false );
+            _Qa[_RTree[i].second] *= new_Qb / _Qb[i];
             _Qb[i] = new_Qb;
         }
 
index 95032b0..13d951e 100644 (file)
@@ -156,7 +156,7 @@ void TRWBP::construct() {
 
 void TRWBP::addTreeToWeights( const RootedTree &tree ) {
     for( RootedTree::const_iterator e = tree.begin(); e != tree.end(); e++ ) {
-        VarSet ij( var(e->n1), var(e->n2) );
+        VarSet ij( var(e->first), var(e->second) );
         size_t I = findFactor( ij );
         _weight[I] += 1.0;
     }
index 703e5e1..3674f5a 100644 (file)
@@ -32,7 +32,7 @@ RootedTree::RootedTree( const GraphEL &T, size_t Root ) {
         // 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 )
+            if( e->first == Root || e->second == Root )
                 valid = true;
         if( !valid )
             DAI_THROWE(RUNTIME_ERROR,"Graph does not contain specified root.");
@@ -45,21 +45,21 @@ RootedTree::RootedTree( const GraphEL &T, size_t Root ) {
         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 );
+                bool e1_in_nodes = nodes.count( e->first );
+                bool e2_in_nodes = nodes.count( e->second );
                 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 );
+                    push_back( DEdge( e->first, e->second ) );
+                    nodes.insert( e->second );
                     // 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 );
+                    push_back( DEdge( e->second, e->first ) );
+                    nodes.insert( e->first );
                     // Erase the edge
                     Gr.erase( e++ );
                     changed = true;
index 73bef82..52445c2 100644 (file)
@@ -28,14 +28,14 @@ using namespace dai;
 
 BOOST_AUTO_TEST_CASE( DEdgeTest ) {
     DEdge a;
-    BOOST_CHECK_EQUAL( a.n1, 0 );
-    BOOST_CHECK_EQUAL( a.n2, 0 );
+    BOOST_CHECK_EQUAL( a.first, 0 );
+    BOOST_CHECK_EQUAL( a.second, 0 );
     DEdge b( 3, 5 );
-    BOOST_CHECK_EQUAL( b.n1, 3 );
-    BOOST_CHECK_EQUAL( b.n2, 5 );
+    BOOST_CHECK_EQUAL( b.first, 3 );
+    BOOST_CHECK_EQUAL( b.second, 5 );
     DEdge c( 5, 3 );
-    BOOST_CHECK_EQUAL( c.n1, 5 );
-    BOOST_CHECK_EQUAL( c.n2, 3 );
+    BOOST_CHECK_EQUAL( c.first, 5 );
+    BOOST_CHECK_EQUAL( c.second, 3 );
     DEdge d( c );
     DEdge e = c;
     DEdge f( 5, 4 );
@@ -84,22 +84,22 @@ BOOST_AUTO_TEST_CASE( DEdgeTest ) {
 
 BOOST_AUTO_TEST_CASE( UEdgeTest ) {
     UEdge a;
-    BOOST_CHECK_EQUAL( a.n1, 0 );
-    BOOST_CHECK_EQUAL( a.n2, 0 );
+    BOOST_CHECK_EQUAL( a.first, 0 );
+    BOOST_CHECK_EQUAL( a.second, 0 );
     UEdge b( 3, 5 );
-    BOOST_CHECK_EQUAL( b.n1, 3 );
-    BOOST_CHECK_EQUAL( b.n2, 5 );
+    BOOST_CHECK_EQUAL( b.first, 3 );
+    BOOST_CHECK_EQUAL( b.second, 5 );
     UEdge c( 5, 3 );
-    BOOST_CHECK_EQUAL( c.n1, 5 );
-    BOOST_CHECK_EQUAL( c.n2, 3 );
+    BOOST_CHECK_EQUAL( c.first, 5 );
+    BOOST_CHECK_EQUAL( c.second, 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_EQUAL( h.first, 5 );
+    BOOST_CHECK_EQUAL( h.second, 3 );
 
     BOOST_CHECK( !(a == b) );
     BOOST_CHECK( !(a == c) );
@@ -175,7 +175,7 @@ BOOST_AUTO_TEST_CASE( RootedTreeTest ) {
     }
     BOOST_CHECK( thrown );
 
-    edges.back().n2 = 4;
+    edges.back().second = 4;
     G = GraphEL( edges.begin(), edges.end() );
     thrown = false;
     RootedTree T;