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