]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
7c673cae FG |
16 | using namespace std; |
17 | using namespace boost; | |
18 | ||
19 | // number of vertices in the graph | |
20 | static const unsigned N = 5; | |
21 | ||
f67539c2 | 22 | template < typename Graph > struct vertex_vector |
7c673cae | 23 | { |
f67539c2 TL |
24 | typedef graph_traits< Graph > traits; |
25 | typedef vector< typename traits::vertex_descriptor > type; | |
7c673cae FG |
26 | }; |
27 | ||
f67539c2 TL |
28 | template < typename Graph > |
29 | void build_graph(Graph& g, typename vertex_vector< Graph >::type& v) | |
7c673cae FG |
30 | { |
31 | // add vertices | |
f67539c2 TL |
32 | for (size_t i = 0; i < N; ++i) |
33 | { | |
7c673cae FG |
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 | ||
f67539c2 | 45 | template < typename Graph > void test_undirected() |
7c673cae | 46 | { |
f67539c2 TL |
47 | typedef typename graph_traits< Graph >::vertex_descriptor Vertex; |
48 | typedef typename graph_traits< Graph >::edge_descriptor Edge; | |
7c673cae | 49 | |
f67539c2 | 50 | typedef exterior_vertex_property< Graph, int > EccentricityProperty; |
7c673cae FG |
51 | typedef typename EccentricityProperty::container_type EccentricityContainer; |
52 | typedef typename EccentricityProperty::map_type EccentricityMap; | |
53 | ||
f67539c2 | 54 | typedef exterior_vertex_property< Graph, int > DistanceProperty; |
7c673cae FG |
55 | typedef typename DistanceProperty::matrix_type DistanceMatrix; |
56 | typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap; | |
57 | ||
f67539c2 | 58 | typedef constant_property_map< Edge, int > WeightMap; |
7c673cae FG |
59 | |
60 | Graph g; | |
f67539c2 | 61 | vector< Vertex > v(N); |
7c673cae FG |
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 | ||
f67539c2 | 86 | template < typename Graph > void test_directed() |
7c673cae | 87 | { |
f67539c2 TL |
88 | typedef typename graph_traits< Graph >::vertex_descriptor Vertex; |
89 | typedef typename graph_traits< Graph >::edge_descriptor Edge; | |
7c673cae | 90 | |
f67539c2 | 91 | typedef exterior_vertex_property< Graph, int > EccentricityProperty; |
7c673cae FG |
92 | typedef typename EccentricityProperty::container_type EccentricityContainer; |
93 | typedef typename EccentricityProperty::map_type EccentricityMap; | |
94 | ||
f67539c2 | 95 | typedef exterior_vertex_property< Graph, int > DistanceProperty; |
7c673cae FG |
96 | typedef typename DistanceProperty::matrix_type DistanceMatrix; |
97 | typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap; | |
98 | ||
f67539c2 | 99 | typedef constant_property_map< Edge, int > WeightMap; |
7c673cae FG |
100 | |
101 | Graph g; | |
f67539c2 | 102 | vector< Vertex > v(N); |
7c673cae FG |
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 | ||
f67539c2 | 118 | int inf = numeric_values< int >::infinity(); |
7c673cae FG |
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 | ||
f67539c2 | 128 | int main(int, char*[]) |
7c673cae FG |
129 | { |
130 | typedef undirected_graph<> Graph; | |
131 | typedef directed_graph<> Digraph; | |
132 | ||
f67539c2 TL |
133 | test_undirected< Graph >(); |
134 | test_directed< Digraph >(); | |
7c673cae | 135 | } |