cf3ca4cdff6428f1b9f7fb19dd8aca3dbee7169c
1 /* This file is part of libDAI - http://www.libdai.org/
3 * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
5 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
9 #include <dai/weightedgraph.h>
10 #include <dai/exceptions.h>
18 #define BOOST_TEST_MODULE WeighedGraphTest
21 #include <boost/test/unit_test.hpp>
24 BOOST_AUTO_TEST_CASE( DEdgeTest
) {
26 BOOST_CHECK_EQUAL( a
.first
, 0 );
27 BOOST_CHECK_EQUAL( a
.second
, 0 );
29 BOOST_CHECK_EQUAL( b
.first
, 3 );
30 BOOST_CHECK_EQUAL( b
.second
, 5 );
32 BOOST_CHECK_EQUAL( c
.first
, 5 );
33 BOOST_CHECK_EQUAL( c
.second
, 3 );
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
);
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
) );
61 BOOST_CHECK( !(f
< a
) );
62 BOOST_CHECK( !(f
< b
) );
63 BOOST_CHECK( !(f
< c
) );
64 BOOST_CHECK( !(f
< g
) );
67 BOOST_CHECK( !(c
< g
) );
68 BOOST_CHECK( !(g
< a
) );
69 BOOST_CHECK( !(g
< b
) );
76 BOOST_CHECK_EQUAL( s
, "(5->3)" );
77 BOOST_CHECK_EQUAL( c
.toString(), s
);
81 BOOST_AUTO_TEST_CASE( UEdgeTest
) {
83 BOOST_CHECK_EQUAL( a
.first
, 0 );
84 BOOST_CHECK_EQUAL( a
.second
, 0 );
86 BOOST_CHECK_EQUAL( b
.first
, 3 );
87 BOOST_CHECK_EQUAL( b
.second
, 5 );
89 BOOST_CHECK_EQUAL( c
.first
, 5 );
90 BOOST_CHECK_EQUAL( c
.second
, 3 );
96 UEdge
h( DEdge( 5, 3 ) );
97 BOOST_CHECK_EQUAL( h
.first
, 5 );
98 BOOST_CHECK_EQUAL( h
.second
, 3 );
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
);
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
) );
133 std::stringstream ss
;
137 BOOST_CHECK_EQUAL( s
, "{3--5}" );
138 BOOST_CHECK_EQUAL( c
.toString(), s
);
141 BOOST_CHECK_EQUAL( s
, "{3--5}" );
142 BOOST_CHECK_EQUAL( b
.toString(), s
);
146 BOOST_AUTO_TEST_CASE( RootedTreeTest
) {
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() );
154 BOOST_CHECK_THROW( RootedTree
T( G
, 0 ), Exception
);
155 BOOST_CHECK_THROW( RootedTree
T( G
, 1 ), Exception
);
157 edges
.back().second
= 4;
158 G
= GraphEL( edges
.begin(), edges
.end() );
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 ) );
166 edges
.push_back( E(5, 6) );
167 G
= GraphEL( edges
.begin(), edges
.end() );
168 BOOST_CHECK_THROW( RootedTree
T( G
, 1 ), Exception
);
175 for( GraphEL::const_iterator e
= G
.begin(); e
!= G
.end(); e
++ )
176 BOOST_CHECK( H
.hasEdge( e
->first
, e
->second
) );
180 BOOST_AUTO_TEST_CASE( SpanningTreeTest
) {
182 WeightedGraph
<int> G
;
190 TMin
.push_back( DEdge( 0,1 ) );
191 TMin
.push_back( DEdge( 0,2 ) );
192 TMin
.push_back( DEdge( 1,3 ) );
194 TMax
.push_back( DEdge( 0,2 ) );
195 TMax
.push_back( DEdge( 2,3 ) );
196 TMax
.push_back( DEdge( 3,1 ) );
198 T
= MinSpanningTree( G
, true );
199 BOOST_CHECK_EQUAL( T
, TMin
);
200 T
= MinSpanningTree( G
, false );
201 BOOST_CHECK_EQUAL( T
, TMin
);
203 T
= MaxSpanningTree( G
, true );
204 BOOST_CHECK_EQUAL( T
, TMax
);
205 T
= MaxSpanningTree( G
, false );
206 BOOST_CHECK_EQUAL( T
, TMax
);
208 WeightedGraph
<double> H
;
214 BOOST_CHECK_THROW( T
= MinSpanningTree( H
, true ), Exception
);