cf3ca4cdff6428f1b9f7fb19dd8aca3dbee7169c
[libdai.git] / 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 }