Changed license from GPL v2+ to FreeBSD (aka BSD 2-clause) license
[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 }
78
79
80 BOOST_AUTO_TEST_CASE( UEdgeTest ) {
81 UEdge a;
82 BOOST_CHECK_EQUAL( a.first, 0 );
83 BOOST_CHECK_EQUAL( a.second, 0 );
84 UEdge b( 3, 5 );
85 BOOST_CHECK_EQUAL( b.first, 3 );
86 BOOST_CHECK_EQUAL( b.second, 5 );
87 UEdge c( 5, 3 );
88 BOOST_CHECK_EQUAL( c.first, 5 );
89 BOOST_CHECK_EQUAL( c.second, 3 );
90 UEdge d( c );
91 UEdge e = c;
92 UEdge f( 5, 4 );
93 UEdge g( 3, 6 );
94
95 UEdge h( DEdge( 5, 3 ) );
96 BOOST_CHECK_EQUAL( h.first, 5 );
97 BOOST_CHECK_EQUAL( h.second, 3 );
98
99 BOOST_CHECK( !(a == b) );
100 BOOST_CHECK( !(a == c) );
101 BOOST_CHECK( b == c );
102 BOOST_CHECK( d == c );
103 BOOST_CHECK( c == d );
104 BOOST_CHECK( e == c );
105 BOOST_CHECK( c == e );
106 BOOST_CHECK( d == e );
107 BOOST_CHECK( e == d );
108
109 BOOST_CHECK( a < b );
110 BOOST_CHECK( a < c );
111 BOOST_CHECK( !(b < c) );
112 BOOST_CHECK( !(c < d) );
113 BOOST_CHECK( !(b < a) );
114 BOOST_CHECK( !(c < a) );
115 BOOST_CHECK( !(c < b) );
116 BOOST_CHECK( !(d < c) );
117 BOOST_CHECK( a < f );
118 BOOST_CHECK( b < f );
119 BOOST_CHECK( c < f );
120 BOOST_CHECK( g < f );
121 BOOST_CHECK( !(f < a) );
122 BOOST_CHECK( !(f < b) );
123 BOOST_CHECK( !(f < c) );
124 BOOST_CHECK( !(f < g) );
125 BOOST_CHECK( a < g );
126 BOOST_CHECK( b < g );
127 BOOST_CHECK( c < g );
128 BOOST_CHECK( !(g < a) );
129 BOOST_CHECK( !(g < b) );
130 BOOST_CHECK( !(g < c) );
131
132 std::stringstream ss;
133 std::string s;
134 ss << c;
135 ss >> s;
136 BOOST_CHECK_EQUAL( s, "{3--5}" );
137 ss << b;
138 ss >> s;
139 BOOST_CHECK_EQUAL( s, "{3--5}" );
140 }
141
142
143 BOOST_AUTO_TEST_CASE( RootedTreeTest ) {
144 typedef UEdge E;
145 std::vector<E> edges;
146 edges.push_back( E( 1, 2 ) );
147 edges.push_back( E( 2, 3 ) );
148 edges.push_back( E( 3, 1 ) );
149 GraphEL G( edges.begin(), edges.end() );
150
151 BOOST_CHECK_THROW( RootedTree T( G, 0 ), Exception );
152 BOOST_CHECK_THROW( RootedTree T( G, 1 ), Exception );
153
154 edges.back().second = 4;
155 G = GraphEL( edges.begin(), edges.end() );
156 RootedTree T;
157 T = RootedTree( G, 1 );
158 BOOST_CHECK_EQUAL( T.size(), 3 );
159 BOOST_CHECK_EQUAL( T[0], DEdge( 1, 2 ) );
160 BOOST_CHECK_EQUAL( T[1], DEdge( 2, 3 ) );
161 BOOST_CHECK_EQUAL( T[2], DEdge( 3, 4 ) );
162
163 edges.push_back( E(5, 6) );
164 G = GraphEL( edges.begin(), edges.end() );
165 BOOST_CHECK_THROW( RootedTree T( G, 1 ), Exception );
166
167 GraphAL H( 3 );
168 H.addEdge( 0, 1 );
169 H.addEdge( 1, 2 );
170 H.addEdge( 2, 1 );
171 G = GraphEL( H );
172 for( GraphEL::const_iterator e = G.begin(); e != G.end(); e++ )
173 BOOST_CHECK( H.hasEdge( e->first, e->second ) );
174 }
175
176
177 BOOST_AUTO_TEST_CASE( SpanningTreeTest ) {
178 RootedTree T;
179 WeightedGraph<int> G;
180 G[UEdge(0,1)] = 1;
181 G[UEdge(0,2)] = 2;
182 G[UEdge(1,2)] = 3;
183 G[UEdge(1,3)] = 4;
184 G[UEdge(2,3)] = 5;
185
186 RootedTree TMin;
187 TMin.push_back( DEdge( 0,1 ) );
188 TMin.push_back( DEdge( 0,2 ) );
189 TMin.push_back( DEdge( 1,3 ) );
190 RootedTree TMax;
191 TMax.push_back( DEdge( 0,2 ) );
192 TMax.push_back( DEdge( 2,3 ) );
193 TMax.push_back( DEdge( 3,1 ) );
194
195 T = MinSpanningTree( G, true );
196 BOOST_CHECK_EQUAL( T, TMin );
197 T = MinSpanningTree( G, false );
198 BOOST_CHECK_EQUAL( T, TMin );
199
200 T = MaxSpanningTree( G, true );
201 BOOST_CHECK_EQUAL( T, TMax );
202 T = MaxSpanningTree( G, false );
203 BOOST_CHECK_EQUAL( T, TMax );
204
205 WeightedGraph<double> H;
206 H[UEdge(1,2)] = 1;
207 H[UEdge(1,3)] = 2;
208 H[UEdge(2,3)] = 3;
209 H[UEdge(2,4)] = 4;
210 H[UEdge(3,4)] = 5;
211 BOOST_CHECK_THROW( T = MinSpanningTree( H, true ), Exception );
212 }