]>
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 | ||
16 | ||
17 | using namespace std; | |
18 | using namespace boost; | |
19 | ||
20 | // number of vertices in the graph | |
21 | static const unsigned N = 5; | |
22 | ||
23 | template <typename Graph> | |
24 | struct vertex_vector | |
25 | { | |
26 | typedef graph_traits<Graph> traits; | |
27 | typedef vector<typename traits::vertex_descriptor> type; | |
28 | }; | |
29 | ||
30 | template <typename Graph> | |
31 | void build_graph(Graph& g, | |
32 | typename vertex_vector<Graph>::type& v) | |
33 | { | |
34 | // add vertices | |
35 | for(size_t i = 0; i < N; ++i) { | |
36 | v[i] = add_vertex(g); | |
37 | } | |
38 | ||
39 | // add edges | |
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); | |
45 | } | |
46 | ||
47 | ||
48 | template <typename Graph> | |
49 | void test_undirected() | |
50 | { | |
51 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; | |
52 | typedef typename graph_traits<Graph>::edge_descriptor Edge; | |
53 | ||
54 | typedef exterior_vertex_property<Graph, int> EccentricityProperty; | |
55 | typedef typename EccentricityProperty::container_type EccentricityContainer; | |
56 | typedef typename EccentricityProperty::map_type EccentricityMap; | |
57 | ||
58 | typedef exterior_vertex_property<Graph, int> DistanceProperty; | |
59 | typedef typename DistanceProperty::matrix_type DistanceMatrix; | |
60 | typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap; | |
61 | ||
62 | typedef constant_property_map<Edge, int> WeightMap; | |
63 | ||
64 | Graph g; | |
65 | vector<Vertex> v(N); | |
66 | build_graph(g, v); | |
67 | ||
68 | EccentricityContainer eccs(num_vertices(g)); | |
69 | DistanceMatrix distances(num_vertices(g)); | |
70 | ||
71 | EccentricityMap em(eccs, g); | |
72 | DistanceMatrixMap dm(distances, g); | |
73 | ||
74 | WeightMap wm(1); | |
75 | ||
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); | |
80 | ||
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); | |
88 | } | |
89 | ||
90 | template <typename Graph> | |
91 | void test_directed() | |
92 | { | |
93 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; | |
94 | typedef typename graph_traits<Graph>::edge_descriptor Edge; | |
95 | ||
96 | typedef exterior_vertex_property<Graph, int> EccentricityProperty; | |
97 | typedef typename EccentricityProperty::container_type EccentricityContainer; | |
98 | typedef typename EccentricityProperty::map_type EccentricityMap; | |
99 | ||
100 | typedef exterior_vertex_property<Graph, int> DistanceProperty; | |
101 | typedef typename DistanceProperty::matrix_type DistanceMatrix; | |
102 | typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap; | |
103 | ||
104 | typedef constant_property_map<Edge, int> WeightMap; | |
105 | ||
106 | Graph g; | |
107 | vector<Vertex> v(N); | |
108 | build_graph(g, v); | |
109 | ||
110 | EccentricityContainer eccs(num_vertices(g)); | |
111 | DistanceMatrix distances(num_vertices(g)); | |
112 | ||
113 | EccentricityMap em(eccs, g); | |
114 | DistanceMatrixMap dm(distances, g); | |
115 | ||
116 | WeightMap wm(1); | |
117 | ||
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); | |
122 | ||
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); | |
131 | } | |
132 | ||
133 | ||
134 | int | |
135 | main(int, char *[]) | |
136 | { | |
137 | typedef undirected_graph<> Graph; | |
138 | typedef directed_graph<> Digraph; | |
139 | ||
140 | test_undirected<Graph>(); | |
141 | test_directed<Digraph>(); | |
142 | } |