ceph/src/boost/libs/graph/test/mean_geodesic.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/exterior_property.hpp>
  12 #include <boost/graph/property_maps/constant_property_map.hpp>
  13
  14 #include <boost/graph/floyd_warshall_shortest.hpp>
  15 #include <boost/graph/geodesic_distance.hpp>
  16
  17 using namespace std;
  18 using namespace boost;
  19
  20 // useful types
  21 // number of vertices in the graph
  22 static const unsigned N = 5;
  23
  24 template <typename Graph>
  25 struct vertex_vector
  26 {
  27     typedef graph_traits<Graph> traits;
  28     typedef vector<typename traits::vertex_descriptor> type;
  29 };
  30
  31 template <typename Graph>
  32 void build_graph(Graph& g, 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, double> CentralityProperty;
  55     typedef typename CentralityProperty::container_type CentralityContainer;
  56     typedef typename CentralityProperty::map_type CentralityMap;
  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     CentralityContainer centralities(num_vertices(g));
  69     DistanceMatrix distances(num_vertices(g));
  70
  71     CentralityMap cm(centralities, 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     double geo1 = all_mean_geodesics(g, dm, cm);
  78     double geo2 = small_world_distance(g, cm);
  79
  80     BOOST_ASSERT(cm[v[0]] == double(5)/4);
  81     BOOST_ASSERT(cm[v[1]] == double(7)/4);
  82     BOOST_ASSERT(cm[v[2]] == double(7)/4);
  83     BOOST_ASSERT(cm[v[3]] == double(9)/4);
  84     BOOST_ASSERT(cm[v[4]] == double(6)/4);
  85     BOOST_ASSERT(geo1 == double(34)/20);
  86     BOOST_ASSERT(geo1 == geo2);
  87 }
  88
  89 template <typename Graph>
  90 void test_directed()
  91 {
  92     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  93     typedef typename graph_traits<Graph>::edge_descriptor Edge;
  94
  95     typedef exterior_vertex_property<Graph, double> CentralityProperty;
  96     typedef typename CentralityProperty::container_type CentralityContainer;
  97     typedef typename CentralityProperty::map_type CentralityMap;
  98
  99     typedef exterior_vertex_property<Graph, int> DistanceProperty;
 100     typedef typename DistanceProperty::matrix_type DistanceMatrix;
 101     typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
 102
 103     typedef constant_property_map<Edge, int> WeightMap;
 104
 105     Graph g;
 106     vector<Vertex> v(N);
 107     build_graph(g, v);
 108
 109     CentralityContainer centralities(num_vertices(g));
 110     DistanceMatrix distances(num_vertices(g));
 111
 112     CentralityMap cm(centralities, g);
 113     DistanceMatrixMap dm(distances, g);
 114
 115     WeightMap wm(1);
 116
 117     floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
 118     double geo1 = all_mean_geodesics(g, dm, cm);
 119     double geo2 = small_world_distance(g, cm);
 120
 121     double inf = numeric_values<double>::infinity();
 122     BOOST_ASSERT(cm[v[0]] == inf);
 123     BOOST_ASSERT(cm[v[1]] == inf);
 124     BOOST_ASSERT(cm[v[2]] == inf);
 125     BOOST_ASSERT(cm[v[3]] == double(10)/4);
 126     BOOST_ASSERT(cm[v[4]] == inf);
 127     BOOST_ASSERT(geo1 == inf);
 128     BOOST_ASSERT(geo1 == geo2);
 129 }
 130
 131
 132 int
 133 main(int, char *[])
 134 {
 135     typedef undirected_graph<> Graph;
 136     typedef directed_graph<> Digraph;
 137
 138     test_undirected<Graph>();
 139     test_directed<Digraph>();
 140 }