tests/unit/weightedgraph_test.cpp

   1 /*  This file is part of libDAI - http://www.libdai.org/
   2  *
   3  *  Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
   4  *
   5  *  Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
   6  */
   7
   8
   9 #include <dai/weightedgraph.h>
  10 #include <dai/exceptions.h>
  11 #include <strstream>
  12 #include <vector>
  13
  14
  15 using namespace dai;
  16
  17
  18 #define BOOST_TEST_MODULE WeighedGraphTest
  19
  20
  21 #include <boost/test/unit_test.hpp>
  22
  23
  24 BOOST_AUTO_TEST_CASE( DEdgeTest ) {
  25     DEdge a;
  26     BOOST_CHECK_EQUAL( a.first, 0 );
  27     BOOST_CHECK_EQUAL( a.second, 0 );
  28     DEdge b( 3, 5 );
  29     BOOST_CHECK_EQUAL( b.first, 3 );
  30     BOOST_CHECK_EQUAL( b.second, 5 );
  31     DEdge c( 5, 3 );
  32     BOOST_CHECK_EQUAL( c.first, 5 );
  33     BOOST_CHECK_EQUAL( c.second, 3 );
  34     DEdge d( c );
  35     DEdge e = c;
  36     DEdge f( 5, 4 );
  37     DEdge g( 3, 6 );
  38
  39     BOOST_CHECK( !(a == b) );
  40     BOOST_CHECK( !(a == c) );
  41     BOOST_CHECK( !(b == c) );
  42     BOOST_CHECK( d == c );
  43     BOOST_CHECK( c == d );
  44     BOOST_CHECK( e == c );
  45     BOOST_CHECK( c == e );
  46     BOOST_CHECK( d == e );
  47     BOOST_CHECK( e == d );
  48
  49     BOOST_CHECK( a < b );
  50     BOOST_CHECK( a < c );
  51     BOOST_CHECK( b < c );
  52     BOOST_CHECK( !(c < d) );
  53     BOOST_CHECK( !(b < a) );
  54     BOOST_CHECK( !(c < a) );
  55     BOOST_CHECK( !(c < b) );
  56     BOOST_CHECK( !(d < c) );
  57     BOOST_CHECK( a < f );
  58     BOOST_CHECK( b < f );
  59     BOOST_CHECK( c < f );
  60     BOOST_CHECK( g < f );
  61     BOOST_CHECK( !(f < a) );
  62     BOOST_CHECK( !(f < b) );
  63     BOOST_CHECK( !(f < c) );
  64     BOOST_CHECK( !(f < g) );
  65     BOOST_CHECK( a < g );
  66     BOOST_CHECK( b < g );
  67     BOOST_CHECK( !(c < g) );
  68     BOOST_CHECK( !(g < a) );
  69     BOOST_CHECK( !(g < b) );
  70     BOOST_CHECK( g < c );
  71
  72     std::stringstream ss;
  73     ss << c;
  74     std::string s;
  75     ss >> s;
  76     BOOST_CHECK_EQUAL( s, "(5->3)" );
  77     BOOST_CHECK_EQUAL( c.toString(), s );
  78 }
  79
  80
  81 BOOST_AUTO_TEST_CASE( UEdgeTest ) {
  82     UEdge a;
  83     BOOST_CHECK_EQUAL( a.first, 0 );
  84     BOOST_CHECK_EQUAL( a.second, 0 );
  85     UEdge b( 3, 5 );
  86     BOOST_CHECK_EQUAL( b.first, 3 );
  87     BOOST_CHECK_EQUAL( b.second, 5 );
  88     UEdge c( 5, 3 );
  89     BOOST_CHECK_EQUAL( c.first, 5 );
  90     BOOST_CHECK_EQUAL( c.second, 3 );
  91     UEdge d( c );
  92     UEdge e = c;
  93     UEdge f( 5, 4 );
  94     UEdge g( 3, 6 );
  95
  96     UEdge h( DEdge( 5, 3 ) );
  97     BOOST_CHECK_EQUAL( h.first, 5 );
  98     BOOST_CHECK_EQUAL( h.second, 3 );
  99
 100     BOOST_CHECK( !(a == b) );
 101     BOOST_CHECK( !(a == c) );
 102     BOOST_CHECK( b == c );
 103     BOOST_CHECK( d == c );
 104     BOOST_CHECK( c == d );
 105     BOOST_CHECK( e == c );
 106     BOOST_CHECK( c == e );
 107     BOOST_CHECK( d == e );
 108     BOOST_CHECK( e == d );
 109
 110     BOOST_CHECK( a < b );
 111     BOOST_CHECK( a < c );
 112     BOOST_CHECK( !(b < c) );
 113     BOOST_CHECK( !(c < d) );
 114     BOOST_CHECK( !(b < a) );
 115     BOOST_CHECK( !(c < a) );
 116     BOOST_CHECK( !(c < b) );
 117     BOOST_CHECK( !(d < c) );
 118     BOOST_CHECK( a < f );
 119     BOOST_CHECK( b < f );
 120     BOOST_CHECK( c < f );
 121     BOOST_CHECK( g < f );
 122     BOOST_CHECK( !(f < a) );
 123     BOOST_CHECK( !(f < b) );
 124     BOOST_CHECK( !(f < c) );
 125     BOOST_CHECK( !(f < g) );
 126     BOOST_CHECK( a < g );
 127     BOOST_CHECK( b < g );
 128     BOOST_CHECK( c < g );
 129     BOOST_CHECK( !(g < a) );
 130     BOOST_CHECK( !(g < b) );
 131     BOOST_CHECK( !(g < c) );
 132
 133     std::stringstream ss;
 134     std::string s;
 135     ss << c;
 136     ss >> s;
 137     BOOST_CHECK_EQUAL( s, "{3--5}" );
 138     BOOST_CHECK_EQUAL( c.toString(), s );
 139     ss << b;
 140     ss >> s;
 141     BOOST_CHECK_EQUAL( s, "{3--5}" );
 142     BOOST_CHECK_EQUAL( b.toString(), s );
 143 }
 144
 145
 146 BOOST_AUTO_TEST_CASE( RootedTreeTest ) {
 147     typedef UEdge E;
 148     std::vector<E> edges;
 149     edges.push_back( E( 1, 2 ) );
 150     edges.push_back( E( 2, 3 ) );
 151     edges.push_back( E( 3, 1 ) );
 152     GraphEL G( edges.begin(), edges.end() );
 153
 154     BOOST_CHECK_THROW( RootedTree T( G, 0 ), Exception );
 155     BOOST_CHECK_THROW( RootedTree T( G, 1 ), Exception );
 156
 157     edges.back().second = 4;
 158     G = GraphEL( edges.begin(), edges.end() );
 159     RootedTree T;
 160     T = RootedTree( G, 1 );
 161     BOOST_CHECK_EQUAL( T.size(), 3 );
 162     BOOST_CHECK_EQUAL( T[0], DEdge( 1, 2 ) );
 163     BOOST_CHECK_EQUAL( T[1], DEdge( 2, 3 ) );
 164     BOOST_CHECK_EQUAL( T[2], DEdge( 3, 4 ) );
 165
 166     edges.push_back( E(5, 6) );
 167     G = GraphEL( edges.begin(), edges.end() );
 168     BOOST_CHECK_THROW( RootedTree T( G, 1 ), Exception );
 169
 170     GraphAL H( 3 );
 171     H.addEdge( 0, 1 );
 172     H.addEdge( 1, 2 );
 173     H.addEdge( 2, 1 );
 174     G = GraphEL( H );
 175     for( GraphEL::const_iterator e = G.begin(); e != G.end(); e++ )
 176         BOOST_CHECK( H.hasEdge( e->first, e->second ) );
 177 }
 178
 179
 180 BOOST_AUTO_TEST_CASE( SpanningTreeTest ) {
 181     RootedTree T;
 182     WeightedGraph<int> G;
 183     G[UEdge(0,1)] = 1;
 184     G[UEdge(0,2)] = 2;
 185     G[UEdge(1,2)] = 3;
 186     G[UEdge(1,3)] = 4;
 187     G[UEdge(2,3)] = 5;
 188
 189     RootedTree TMin;
 190     TMin.push_back( DEdge( 0,1 ) );
 191     TMin.push_back( DEdge( 0,2 ) );
 192     TMin.push_back( DEdge( 1,3 ) );
 193     RootedTree TMax;
 194     TMax.push_back( DEdge( 0,2 ) );
 195     TMax.push_back( DEdge( 2,3 ) );
 196     TMax.push_back( DEdge( 3,1 ) );
 197
 198     T = MinSpanningTree( G, true );
 199     BOOST_CHECK_EQUAL( T, TMin );
 200     T = MinSpanningTree( G, false );
 201     BOOST_CHECK_EQUAL( T, TMin );
 202
 203     T = MaxSpanningTree( G, true );
 204     BOOST_CHECK_EQUAL( T, TMax );
 205     T = MaxSpanningTree( G, false );
 206     BOOST_CHECK_EQUAL( T, TMax );
 207
 208     WeightedGraph<double> H;
 209     H[UEdge(1,2)] = 1;
 210     H[UEdge(1,3)] = 2;
 211     H[UEdge(2,3)] = 3;
 212     H[UEdge(2,4)] = 4;
 213     H[UEdge(3,4)] = 5;
 214     BOOST_CHECK_THROW( T = MinSpanningTree( H, true ), Exception );
 215 }