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
main(int argc,const char ** argv)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 }
119