libs/graph/test/eccentricity.cpp

   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 }