ceph/src/boost/libs/graph/example/ospf-example.cpp

   1 //=======================================================================
   2 // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
   3 //
   4 // Distributed under the Boost Software License, Version 1.0. (See
   5 // accompanying file LICENSE_1_0.txt or copy at
   6 // http://www.boost.org/LICENSE_1_0.txt)
   7 //=======================================================================
   8 #include <fstream> // for file I/O
   9 #include <boost/graph/graphviz.hpp> // for read/write_graphviz()
  10 #include <boost/graph/dijkstra_shortest_paths.hpp>
  11 #include <boost/lexical_cast.hpp>
  12
  13 namespace boost
  14 {
  15 enum graph_color_t
  16 {
  17     graph_color = 5556
  18 };
  19 BOOST_INSTALL_PROPERTY(graph, color);
  20 }
  21
  22 int main(int argc, const char** argv)
  23 {
  24     using namespace boost;
  25     typedef adjacency_list< vecS, vecS, directedS,
  26         property< vertex_name_t, std::string >,
  27         property< edge_color_t, std::string, property< edge_weight_t, int > >,
  28         property< graph_color_t, std::string > >
  29         g_dot_type;
  30     g_dot_type g_dot;
  31
  32     dynamic_properties dp(ignore_other_properties);
  33     dp.property("node_id", get(vertex_name, g_dot));
  34     dp.property("label", get(edge_weight, g_dot));
  35     dp.property("color", get(edge_color, g_dot));
  36     dp.property("color",
  37         ref_property_map< g_dot_type*, std::string >(
  38             get_property(g_dot, graph_color)));
  39     {
  40         std::ifstream infile(argc >= 2 ? argv[1] : "figs/ospf-graph.dot");
  41         read_graphviz(infile, g_dot, dp);
  42     }
  43
  44     typedef adjacency_list< vecS, vecS, directedS, no_property,
  45         property< edge_weight_t, int > >
  46         Graph;
  47     typedef graph_traits< Graph >::vertex_descriptor vertex_descriptor;
  48     Graph g(num_vertices(g_dot));
  49     graph_traits< g_dot_type >::edge_iterator ei, ei_end;
  50     for (boost::tie(ei, ei_end) = edges(g_dot); ei != ei_end; ++ei)
  51     {
  52         int weight = get(edge_weight, g_dot, *ei);
  53         property< edge_weight_t, int > edge_property(weight);
  54         add_edge(source(*ei, g_dot), target(*ei, g_dot), edge_property, g);
  55     }
  56
  57     vertex_descriptor router_six;
  58     graph_traits< g_dot_type >::vertex_iterator vi, vi_end;
  59     for (boost::tie(vi, vi_end) = vertices(g_dot); vi != vi_end; ++vi)
  60         if ("RT6" == get(vertex_name, g_dot, *vi))
  61         {
  62             router_six = *vi;
  63             break;
  64         }
  65
  66     std::vector< vertex_descriptor > parent(num_vertices(g));
  67     // All vertices start out as there own parent
  68     typedef graph_traits< Graph >::vertices_size_type size_type;
  69     for (size_type p = 0; p < num_vertices(g); ++p)
  70         parent[p] = p;
  71
  72 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
  73     std::vector< int > distance(num_vertices(g));
  74     property_map< Graph, edge_weight_t >::type weightmap = get(edge_weight, g);
  75     property_map< Graph, vertex_index_t >::type indexmap = get(vertex_index, g);
  76     dijkstra_shortest_paths(g, router_six, &parent[0], &distance[0], weightmap,
  77         indexmap, std::less< int >(), closed_plus< int >(),
  78         (std::numeric_limits< int >::max)(), 0, default_dijkstra_visitor());
  79 #else
  80     dijkstra_shortest_paths(g, router_six, predecessor_map(&parent[0]));
  81 #endif
  82
  83     graph_traits< g_dot_type >::edge_descriptor e;
  84     for (size_type i = 0; i < num_vertices(g); ++i)
  85         if (parent[i] != i)
  86         {
  87             e = edge(parent[i], i, g_dot).first;
  88             put(edge_color, g_dot, e, "black");
  89         }
  90
  91     get_property(g_dot, graph_color) = "grey";
  92     {
  93         std::ofstream outfile(argc >= 3 ? argv[2] : "figs/ospf-sptree.dot");
  94         write_graphviz_dp(outfile, g_dot, dp);
  95     }
  96
  97     std::ofstream rtable(argc >= 4 ? argv[3] : "routing-table.dat");
  98     rtable << "Dest    Next Hop    Total Cost" << std::endl;
  99     for (boost::tie(vi, vi_end) = vertices(g_dot); vi != vi_end; ++vi)
 100         if (parent[*vi] != *vi)
 101         {
 102             rtable << get(vertex_name, g_dot, *vi) << "    ";
 103             vertex_descriptor v = *vi, child;
 104             int path_cost = 0;
 105             property_map< Graph, edge_weight_t >::type weight_map
 106                 = get(edge_weight, g);
 107             do
 108             {
 109                 path_cost += get(weight_map, edge(parent[v], v, g).first);
 110                 child = v;
 111                 v = parent[v];
 112             } while (v != parent[v]);
 113             rtable << get(vertex_name, g_dot, child) << "     ";
 114             rtable << path_cost << std::endl;
 115         }
 116
 117     return EXIT_SUCCESS;
 118 }