1 | // (C) Copyright 2007-2009 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 | |
9 | #include <boost/graph/undirected_graph.hpp> |
10 | #include <boost/graph/directed_graph.hpp> |
11 | #include <boost/graph/floyd_warshall_shortest.hpp> |
12 | #include <boost/graph/eccentricity.hpp> |
13 | #include <boost/graph/exterior_property.hpp> |
14 | #include <boost/graph/property_maps/constant_property_map.hpp> |
15 | |
16 | using namespace std; |
17 | using namespace boost; |
18 | |
19 | // number of vertices in the graph |
20 | static const unsigned N = 5; |
21 | |
22 | template < typename Graph > struct vertex_vector |
23 | { |
24 | typedef graph_traits< Graph > traits; |
25 | typedef vector< typename traits::vertex_descriptor > type; |
26 | }; |
27 | |
28 | template < typename Graph > |
29 | void build_graph(Graph& g, typename vertex_vector< Graph >::type& v) |
30 | { |
31 | // add vertices |
32 | for (size_t i = 0; i < N; ++i) |
33 | { |
34 | v[i] = add_vertex(g); |
35 | } |
36 | |
37 | // add edges |
38 | add_edge(v[0], v[1], g); |
39 | add_edge(v[1], v[2], g); |
40 | add_edge(v[2], v[0], g); |
41 | add_edge(v[3], v[4], g); |
42 | add_edge(v[4], v[0], g); |
43 | } |
44 | |
45 | template < typename Graph > void test_undirected() |
46 | { |
47 | typedef typename graph_traits< Graph >::vertex_descriptor Vertex; |
48 | typedef typename graph_traits< Graph >::edge_descriptor Edge; |
49 | |
50 | typedef exterior_vertex_property< Graph, int > EccentricityProperty; |
51 | typedef typename EccentricityProperty::container_type EccentricityContainer; |
52 | typedef typename EccentricityProperty::map_type EccentricityMap; |
53 | |
54 | typedef exterior_vertex_property< Graph, int > DistanceProperty; |
55 | typedef typename DistanceProperty::matrix_type DistanceMatrix; |
56 | typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap; |
57 | |
58 | typedef constant_property_map< Edge, int > WeightMap; |
59 | |
60 | Graph g; |
61 | vector< Vertex > v(N); |
62 | build_graph(g, v); |
63 | |
64 | EccentricityContainer eccs(num_vertices(g)); |
65 | DistanceMatrix distances(num_vertices(g)); |
66 | |
67 | EccentricityMap em(eccs, g); |
68 | DistanceMatrixMap dm(distances, g); |
69 | |
70 | WeightMap wm(1); |
71 | |
72 | floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm)); |
73 | all_eccentricities(g, dm, em); |
74 | int rad = radius(g, em); |
75 | int dia = diameter(g, em); |
76 | |
77 | BOOST_ASSERT(em[v[0]] == 2); |
78 | BOOST_ASSERT(em[v[1]] == 3); |
79 | BOOST_ASSERT(em[v[2]] == 3); |
80 | BOOST_ASSERT(em[v[3]] == 3); |
81 | BOOST_ASSERT(em[v[4]] == 2); |
82 | BOOST_ASSERT(rad == 2); |
83 | BOOST_ASSERT(dia == 3); |
84 | } |
85 | |
86 | template < typename Graph > void test_directed() |
87 | { |
88 | typedef typename graph_traits< Graph >::vertex_descriptor Vertex; |
89 | typedef typename graph_traits< Graph >::edge_descriptor Edge; |
90 | |
91 | typedef exterior_vertex_property< Graph, int > EccentricityProperty; |
92 | typedef typename EccentricityProperty::container_type EccentricityContainer; |
93 | typedef typename EccentricityProperty::map_type EccentricityMap; |
94 | |
95 | typedef exterior_vertex_property< Graph, int > DistanceProperty; |
96 | typedef typename DistanceProperty::matrix_type DistanceMatrix; |
97 | typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap; |
98 | |
99 | typedef constant_property_map< Edge, int > WeightMap; |
100 | |
101 | Graph g; |
102 | vector< Vertex > v(N); |
103 | build_graph(g, v); |
104 | |
105 | EccentricityContainer eccs(num_vertices(g)); |
106 | DistanceMatrix distances(num_vertices(g)); |
107 | |
108 | EccentricityMap em(eccs, g); |
109 | DistanceMatrixMap dm(distances, g); |
110 | |
111 | WeightMap wm(1); |
112 | |
113 | floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm)); |
114 | all_eccentricities(g, dm, em); |
115 | int rad = radius(g, em); |
116 | int dia = diameter(g, em); |
117 | |
118 | int inf = numeric_values< int >::infinity(); |
119 | BOOST_ASSERT(em[v[0]] == inf); |
120 | BOOST_ASSERT(em[v[1]] == inf); |
121 | BOOST_ASSERT(em[v[2]] == inf); |
122 | BOOST_ASSERT(em[v[3]] == 4); |
123 | BOOST_ASSERT(em[v[4]] == inf); |
124 | BOOST_ASSERT(rad == 4); |
125 | BOOST_ASSERT(dia == inf); |
126 | } |
127 | |
128 | int main(int, char*[]) |
129 | { |
130 | typedef undirected_graph<> Graph; |
131 | typedef directed_graph<> Digraph; |
132 | |
133 | test_undirected< Graph >(); |
134 | test_directed< Digraph >(); |
135 | } |
136 | |