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
main()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