1 // (C) Copyright 2007-2009 Andrew Sutton
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)
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>
18 using namespace boost
;
20 // number of vertices in the graph
21 static const unsigned N
= 5;
23 template <typename Graph
>
26 typedef graph_traits
<Graph
> traits
;
27 typedef vector
<typename
traits::vertex_descriptor
> type
;
30 template <typename Graph
>
31 void build_graph(Graph
& g
,
32 typename vertex_vector
<Graph
>::type
& v
)
35 for(size_t i
= 0; i
< N
; ++i
) {
40 add_edge(v
[0], v
[1], g
);
41 add_edge(v
[1], v
[2], g
);
42 add_edge(v
[2], v
[0], g
);
43 add_edge(v
[3], v
[4], g
);
44 add_edge(v
[4], v
[0], g
);
48 template <typename Graph
>
49 void test_undirected()
51 typedef typename graph_traits
<Graph
>::vertex_descriptor Vertex
;
52 typedef typename graph_traits
<Graph
>::edge_descriptor Edge
;
54 typedef exterior_vertex_property
<Graph
, int> EccentricityProperty
;
55 typedef typename
EccentricityProperty::container_type EccentricityContainer
;
56 typedef typename
EccentricityProperty::map_type EccentricityMap
;
58 typedef exterior_vertex_property
<Graph
, int> DistanceProperty
;
59 typedef typename
DistanceProperty::matrix_type DistanceMatrix
;
60 typedef typename
DistanceProperty::matrix_map_type DistanceMatrixMap
;
62 typedef constant_property_map
<Edge
, int> WeightMap
;
68 EccentricityContainer
eccs(num_vertices(g
));
69 DistanceMatrix
distances(num_vertices(g
));
71 EccentricityMap
em(eccs
, g
);
72 DistanceMatrixMap
dm(distances
, g
);
76 floyd_warshall_all_pairs_shortest_paths(g
, dm
, weight_map(wm
));
77 all_eccentricities(g
, dm
, em
);
78 int rad
= radius(g
, em
);
79 int dia
= diameter(g
, em
);
81 BOOST_ASSERT(em
[v
[0]] == 2);
82 BOOST_ASSERT(em
[v
[1]] == 3);
83 BOOST_ASSERT(em
[v
[2]] == 3);
84 BOOST_ASSERT(em
[v
[3]] == 3);
85 BOOST_ASSERT(em
[v
[4]] == 2);
86 BOOST_ASSERT(rad
== 2);
87 BOOST_ASSERT(dia
== 3);
90 template <typename Graph
>
93 typedef typename graph_traits
<Graph
>::vertex_descriptor Vertex
;
94 typedef typename graph_traits
<Graph
>::edge_descriptor Edge
;
96 typedef exterior_vertex_property
<Graph
, int> EccentricityProperty
;
97 typedef typename
EccentricityProperty::container_type EccentricityContainer
;
98 typedef typename
EccentricityProperty::map_type EccentricityMap
;
100 typedef exterior_vertex_property
<Graph
, int> DistanceProperty
;
101 typedef typename
DistanceProperty::matrix_type DistanceMatrix
;
102 typedef typename
DistanceProperty::matrix_map_type DistanceMatrixMap
;
104 typedef constant_property_map
<Edge
, int> WeightMap
;
110 EccentricityContainer
eccs(num_vertices(g
));
111 DistanceMatrix
distances(num_vertices(g
));
113 EccentricityMap
em(eccs
, g
);
114 DistanceMatrixMap
dm(distances
, g
);
118 floyd_warshall_all_pairs_shortest_paths(g
, dm
, weight_map(wm
));
119 all_eccentricities(g
, dm
, em
);
120 int rad
= radius(g
, em
);
121 int dia
= diameter(g
, em
);
123 int inf
= numeric_values
<int>::infinity();
124 BOOST_ASSERT(em
[v
[0]] == inf
);
125 BOOST_ASSERT(em
[v
[1]] == inf
);
126 BOOST_ASSERT(em
[v
[2]] == inf
);
127 BOOST_ASSERT(em
[v
[3]] == 4);
128 BOOST_ASSERT(em
[v
[4]] == inf
);
129 BOOST_ASSERT(rad
== 4);
130 BOOST_ASSERT(dia
== inf
);
137 typedef undirected_graph
<> Graph
;
138 typedef directed_graph
<> Digraph
;
140 test_undirected
<Graph
>();
141 test_directed
<Digraph
>();