1 | // (C) Copyright 2009-2010 Andrew Sutton |
2 | // |
3 | // Use, modification and distribution are subject to the |
4 | // Boost Software License, Version 1.0 (See accompanying file |
5 | // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt) |
6 | |
7 | #include <iostream> |
8 | #include "typestr.hpp" |
9 | |
10 | #include <boost/graph/adjacency_list.hpp> |
11 | #include <boost/graph/adjacency_matrix.hpp> |
12 | #include <boost/graph/undirected_graph.hpp> |
13 | #include <boost/graph/directed_graph.hpp> |
14 | #include <boost/graph/compressed_sparse_row_graph.hpp> |
15 | #include <boost/graph/labeled_graph.hpp> |
16 | #include <boost/graph/subgraph.hpp> |
17 | |
18 | #include "test_graph.hpp" |
19 | |
20 | // This test module is a testing ground to determine if graphs and graph |
21 | // adaptors actually implement the graph concepts correctly. |
22 | |
23 | using namespace boost; |
24 | |
25 | int main() |
26 | { |
27 | // Bootstrap all of the tests by declaring a kind graph and asserting some |
28 | // basic properties about it. |
29 | { |
30 | typedef undirected_graph< VertexBundle, EdgeBundle, GraphBundle > Graph; |
31 | BOOST_META_ASSERT(is_undirected_graph< Graph >); |
32 | BOOST_META_ASSERT(is_multigraph< Graph >); |
33 | BOOST_META_ASSERT(is_incidence_graph< Graph >); |
34 | BOOST_META_ASSERT(is_bidirectional_graph< Graph >); |
35 | BOOST_META_ASSERT(has_vertex_property< Graph >); |
36 | BOOST_META_ASSERT(has_bundled_vertex_property< Graph >); |
37 | BOOST_META_ASSERT(has_edge_property< Graph >); |
38 | BOOST_META_ASSERT(has_bundled_edge_property< Graph >); |
39 | BOOST_META_ASSERT(is_mutable_graph< Graph >); |
40 | BOOST_META_ASSERT(is_mutable_property_graph< Graph >); |
41 | Graph g; |
42 | test_graph(g); |
43 | } |
44 | { |
45 | typedef directed_graph< VertexBundle, EdgeBundle, GraphBundle > Graph; |
46 | BOOST_META_ASSERT(is_directed_graph< Graph >); |
47 | BOOST_META_ASSERT(is_multigraph< Graph >); |
48 | BOOST_META_ASSERT(is_incidence_graph< Graph >); |
49 | BOOST_META_ASSERT(is_bidirectional_graph< Graph >); |
50 | BOOST_META_ASSERT(is_directed_bidirectional_graph< Graph >); |
51 | BOOST_META_ASSERT(has_vertex_property< Graph >); |
52 | BOOST_META_ASSERT(has_bundled_vertex_property< Graph >); |
53 | BOOST_META_ASSERT(has_edge_property< Graph >); |
54 | BOOST_META_ASSERT(has_bundled_edge_property< Graph >); |
55 | BOOST_META_ASSERT(is_mutable_graph< Graph >); |
56 | BOOST_META_ASSERT(is_mutable_property_graph< Graph >); |
57 | Graph g; |
58 | test_graph(g); |
59 | } |
60 | { |
61 | typedef adjacency_list< vecS, vecS, undirectedS, VertexBundle, |
62 | EdgeBundle, GraphBundle > |
63 | Graph; |
64 | BOOST_META_ASSERT(is_undirected_graph< Graph >); |
65 | BOOST_META_ASSERT(is_multigraph< Graph >); |
66 | BOOST_META_ASSERT(is_incidence_graph< Graph >); |
67 | BOOST_META_ASSERT(is_bidirectional_graph< Graph >); |
68 | BOOST_META_ASSERT(has_vertex_property< Graph >); |
69 | BOOST_META_ASSERT(has_bundled_vertex_property< Graph >); |
70 | BOOST_META_ASSERT(has_edge_property< Graph >); |
71 | BOOST_META_ASSERT(has_bundled_edge_property< Graph >); |
72 | BOOST_META_ASSERT(is_add_only_property_graph< Graph >); |
73 | Graph g; |
74 | test_graph(g); |
75 | } |
76 | { |
77 | typedef adjacency_list< vecS, vecS, directedS, VertexBundle, EdgeBundle, |
78 | GraphBundle > |
79 | Graph; |
80 | Graph g; |
81 | BOOST_META_ASSERT(is_directed_graph< Graph >); |
82 | BOOST_META_ASSERT(is_multigraph< Graph >); |
83 | BOOST_META_ASSERT(is_incidence_graph< Graph >); |
84 | BOOST_META_ASSERT(!is_bidirectional_graph< Graph >); |
85 | BOOST_META_ASSERT(is_directed_unidirectional_graph< Graph >); |
86 | BOOST_META_ASSERT(has_vertex_property< Graph >); |
87 | BOOST_META_ASSERT(has_bundled_vertex_property< Graph >); |
88 | BOOST_META_ASSERT(has_edge_property< Graph >); |
89 | BOOST_META_ASSERT(has_bundled_edge_property< Graph >); |
90 | BOOST_META_ASSERT(is_add_only_property_graph< Graph >); |
91 | test_graph(g); |
92 | } |
93 | { |
94 | // Common bidi adjlist |
95 | typedef adjacency_list< vecS, vecS, bidirectionalS, VertexBundle, |
96 | EdgeBundle, GraphBundle > |
97 | Graph; |
98 | BOOST_META_ASSERT(is_directed_graph< Graph >); |
99 | BOOST_META_ASSERT(is_multigraph< Graph >); |
100 | BOOST_META_ASSERT(is_incidence_graph< Graph >); |
101 | BOOST_META_ASSERT(is_bidirectional_graph< Graph >); |
102 | BOOST_META_ASSERT(is_directed_bidirectional_graph< Graph >); |
103 | BOOST_META_ASSERT(has_vertex_property< Graph >); |
104 | BOOST_META_ASSERT(has_bundled_vertex_property< Graph >); |
105 | BOOST_META_ASSERT(has_edge_property< Graph >); |
106 | BOOST_META_ASSERT(has_bundled_edge_property< Graph >); |
107 | BOOST_META_ASSERT(is_add_only_property_graph< Graph >); |
108 | Graph g; |
109 | test_graph(g); |
110 | } |
111 | { |
112 | // Same as above, but testing VL==listS |
113 | typedef adjacency_list< vecS, listS, bidirectionalS, VertexBundle, |
114 | EdgeBundle, GraphBundle > |
115 | Graph; |
116 | BOOST_META_ASSERT(is_directed_graph< Graph >); |
117 | BOOST_META_ASSERT(is_multigraph< Graph >); |
118 | BOOST_META_ASSERT(is_incidence_graph< Graph >); |
119 | BOOST_META_ASSERT(is_bidirectional_graph< Graph >); |
120 | BOOST_META_ASSERT(is_directed_bidirectional_graph< Graph >); |
121 | BOOST_META_ASSERT(has_vertex_property< Graph >); |
122 | BOOST_META_ASSERT(has_bundled_vertex_property< Graph >); |
123 | BOOST_META_ASSERT(has_edge_property< Graph >); |
124 | BOOST_META_ASSERT(has_bundled_edge_property< Graph >); |
125 | BOOST_META_ASSERT(is_mutable_property_graph< Graph >); |
126 | Graph g; |
127 | test_graph(g); |
128 | } |
129 | { |
130 | typedef adjacency_matrix< directedS, VertexBundle, EdgeBundle, |
131 | GraphBundle > |
132 | Graph; |
133 | BOOST_META_ASSERT(is_directed_graph< Graph >); |
134 | BOOST_META_ASSERT(!is_multigraph< Graph >); |
135 | BOOST_META_ASSERT(has_vertex_property< Graph >); |
136 | BOOST_META_ASSERT(has_bundled_vertex_property< Graph >); |
137 | BOOST_META_ASSERT(has_edge_property< Graph >); |
138 | BOOST_META_ASSERT(has_bundled_edge_property< Graph >); |
139 | BOOST_META_ASSERT(is_mutable_edge_graph< Graph >); |
140 | BOOST_META_ASSERT(is_mutable_edge_property_graph< Graph >); |
141 | Graph g(N); |
142 | test_graph(g); |
143 | } |
144 | { |
145 | typedef adjacency_matrix< directedS, VertexBundle, EdgeBundle > Graph; |
146 | BOOST_META_ASSERT(is_directed_graph< Graph >); |
147 | BOOST_META_ASSERT(!is_multigraph< Graph >); |
148 | BOOST_META_ASSERT(has_vertex_property< Graph >); |
149 | BOOST_META_ASSERT(has_bundled_vertex_property< Graph >); |
150 | BOOST_META_ASSERT(has_edge_property< Graph >); |
151 | BOOST_META_ASSERT(has_bundled_edge_property< Graph >); |
152 | BOOST_META_ASSERT(is_mutable_edge_graph< Graph >); |
153 | BOOST_META_ASSERT(is_mutable_edge_property_graph< Graph >); |
154 | Graph g(N); |
155 | test_graph(g); |
156 | } |
157 | { |
158 | typedef labeled_graph< directed_graph<>, unsigned > Graph; |
159 | BOOST_META_ASSERT(is_directed_graph< Graph >); |
160 | BOOST_META_ASSERT(is_multigraph< Graph >); |
161 | BOOST_META_ASSERT(is_incidence_graph< Graph >); |
162 | BOOST_META_ASSERT(is_bidirectional_graph< Graph >); |
163 | BOOST_META_ASSERT(is_directed_bidirectional_graph< Graph >); |
164 | BOOST_META_ASSERT(is_labeled_mutable_property_graph< Graph >); |
165 | BOOST_META_ASSERT(is_labeled_graph< Graph >); |
166 | BOOST_META_ASSERT(!has_vertex_property< Graph >); |
167 | BOOST_META_ASSERT(!has_bundled_vertex_property< Graph >); |
168 | BOOST_META_ASSERT(!has_edge_property< Graph >); |
169 | BOOST_META_ASSERT(!has_bundled_edge_property< Graph >); |
170 | BOOST_META_ASSERT(is_labeled_mutable_graph< Graph >); |
171 | Graph g; |
172 | test_graph(g); |
173 | } |
174 | |
175 | // FIXME: CSR doesn't have mutability traits so we can't generalize the |
176 | // constructions of the required graph. Just assert the properties for now. |
177 | // NOTE: CSR graphs are also atypical in that they don't have "normal" |
178 | // vertex and edge properties. They're "abnormal" in the sense that they |
179 | // have a valid bundled type, but the property types are no_property. |
180 | { |
181 | typedef compressed_sparse_row_graph< directedS, VertexBundle, |
182 | EdgeBundle, GraphBundle > |
183 | Graph; |
184 | BOOST_META_ASSERT(is_directed_graph< Graph >); |
185 | BOOST_META_ASSERT(is_multigraph< Graph >); |
186 | BOOST_META_ASSERT(has_graph_property< Graph >); |
187 | BOOST_META_ASSERT(has_bundled_graph_property< Graph >); |
188 | BOOST_META_ASSERT(!has_vertex_property< Graph >); |
189 | BOOST_META_ASSERT(has_bundled_vertex_property< Graph >); |
190 | BOOST_META_ASSERT(!has_edge_property< Graph >); |
191 | BOOST_META_ASSERT(has_bundled_edge_property< Graph >); |
192 | } |
193 | { |
194 | typedef compressed_sparse_row_graph< bidirectionalS, VertexBundle, |
195 | EdgeBundle, GraphBundle > |
196 | Graph; |
197 | BOOST_META_ASSERT(is_directed_graph< Graph >); |
198 | BOOST_META_ASSERT(is_multigraph< Graph >); |
199 | BOOST_META_ASSERT(has_graph_property< Graph >); |
200 | BOOST_META_ASSERT(has_bundled_graph_property< Graph >); |
201 | BOOST_META_ASSERT(!has_vertex_property< Graph >); |
202 | BOOST_META_ASSERT(has_bundled_vertex_property< Graph >); |
203 | BOOST_META_ASSERT(!has_edge_property< Graph >); |
204 | BOOST_META_ASSERT(has_bundled_edge_property< Graph >); |
205 | } |
206 | |
207 | // TODO: What other kinds of graphs do we have here... |
208 | } |
209 | |