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