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 | int |
---|
13 | main() |
---|
14 | { |
---|
15 | using namespace boost; |
---|
16 | GraphvizDigraph g_dot; |
---|
17 | read_graphviz("figs/ospf-graph.dot", g_dot); |
---|
18 | |
---|
19 | typedef adjacency_list < vecS, vecS, directedS, no_property, |
---|
20 | property < edge_weight_t, int > > Graph; |
---|
21 | typedef graph_traits < Graph >::vertex_descriptor vertex_descriptor; |
---|
22 | Graph g(num_vertices(g_dot)); |
---|
23 | property_map < GraphvizDigraph, edge_attribute_t >::type |
---|
24 | edge_attr_map = get(edge_attribute, g_dot); |
---|
25 | graph_traits < GraphvizDigraph >::edge_iterator ei, ei_end; |
---|
26 | for (tie(ei, ei_end) = edges(g_dot); ei != ei_end; ++ei) { |
---|
27 | int weight = lexical_cast < int >(edge_attr_map[*ei]["label"]); |
---|
28 | property < edge_weight_t, int >edge_property(weight); |
---|
29 | add_edge(source(*ei, g_dot), target(*ei, g_dot), edge_property, g); |
---|
30 | } |
---|
31 | |
---|
32 | vertex_descriptor router_six; |
---|
33 | property_map < GraphvizDigraph, vertex_attribute_t >::type |
---|
34 | vertex_attr_map = get(vertex_attribute, g_dot); |
---|
35 | graph_traits < GraphvizDigraph >::vertex_iterator vi, vi_end; |
---|
36 | for (tie(vi, vi_end) = vertices(g_dot); vi != vi_end; ++vi) |
---|
37 | if ("RT6" == vertex_attr_map[*vi]["label"]) { |
---|
38 | router_six = *vi; |
---|
39 | break; |
---|
40 | } |
---|
41 | |
---|
42 | std::vector < vertex_descriptor > parent(num_vertices(g)); |
---|
43 | // All vertices start out as there own parent |
---|
44 | typedef graph_traits < Graph >::vertices_size_type size_type; |
---|
45 | for (size_type p = 0; p < num_vertices(g); ++p) |
---|
46 | parent[p] = p; |
---|
47 | |
---|
48 | #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 |
---|
49 | std::vector<int> distance(num_vertices(g)); |
---|
50 | property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, g); |
---|
51 | property_map<Graph, vertex_index_t>::type indexmap = get(vertex_index, g); |
---|
52 | dijkstra_shortest_paths |
---|
53 | (g, router_six, &parent[0], &distance[0], weightmap, |
---|
54 | indexmap, std::less<int>(), closed_plus<int>(), |
---|
55 | (std::numeric_limits<int>::max)(), 0, default_dijkstra_visitor()); |
---|
56 | #else |
---|
57 | dijkstra_shortest_paths(g, router_six, predecessor_map(&parent[0])); |
---|
58 | #endif |
---|
59 | |
---|
60 | graph_traits < GraphvizDigraph >::edge_descriptor e; |
---|
61 | for (size_type i = 0; i < num_vertices(g); ++i) |
---|
62 | if (parent[i] != i) { |
---|
63 | e = edge(parent[i], i, g_dot).first; |
---|
64 | edge_attr_map[e]["color"] = "black"; |
---|
65 | } |
---|
66 | |
---|
67 | #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 |
---|
68 | // VC++ can't handle write_graphviz :( |
---|
69 | { |
---|
70 | std::ofstream out("figs/ospf-sptree.dot"); |
---|
71 | out << "digraph loops {\n" |
---|
72 | << "size=\"3,3\"\n" |
---|
73 | << "ratio=\"fill\"\n" |
---|
74 | << "shape=\"box\"\n"; |
---|
75 | graph_traits<Graph>::vertex_iterator vi, vi_end; |
---|
76 | for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) { |
---|
77 | out << *vi << "["; |
---|
78 | for (std::map<std::string,std::string>::iterator ai = vattr_map[*vi].begin(); |
---|
79 | ai != vattr_map[*vi].end(); ++ai) { |
---|
80 | out << ai->first << "=" << ai->second; |
---|
81 | if (next(ai) != vattr_map[*vi].end()) |
---|
82 | out << ", "; |
---|
83 | } |
---|
84 | out<< "]"; |
---|
85 | } |
---|
86 | |
---|
87 | for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) { |
---|
88 | out << source(*ei, g) << " -> " << target(*ei, g) << "["; |
---|
89 | std::map<std::string,std::string>& attr_map = eattr_map[*ei]; |
---|
90 | for (std::map<std::string,std::string>::iterator eai = attr_map.begin(); |
---|
91 | eai != attr_map.end(); ++eai) { |
---|
92 | out << eai->first << "=" << eai->second; |
---|
93 | if (next(eai) != attr_map.end()) |
---|
94 | out << ", "; |
---|
95 | } |
---|
96 | out<< "]"; |
---|
97 | } |
---|
98 | out << "}\n"; |
---|
99 | } |
---|
100 | #else |
---|
101 | graph_property < GraphvizDigraph, graph_edge_attribute_t >::type & |
---|
102 | graph_edge_attr_map = get_property(g_dot, graph_edge_attribute); |
---|
103 | graph_edge_attr_map["color"] = "grey"; |
---|
104 | write_graphviz("figs/ospf-sptree.dot", g_dot); |
---|
105 | #endif |
---|
106 | |
---|
107 | std::ofstream rtable("routing-table.dat"); |
---|
108 | rtable << "Dest Next Hop Total Cost" << std::endl; |
---|
109 | for (tie(vi, vi_end) = vertices(g_dot); vi != vi_end; ++vi) |
---|
110 | if (parent[*vi] != *vi) { |
---|
111 | rtable << vertex_attr_map[*vi]["label"] << " "; |
---|
112 | vertex_descriptor v = *vi, child; |
---|
113 | int path_cost = 0; |
---|
114 | property_map < Graph, edge_weight_t >::type |
---|
115 | weight_map = get(edge_weight, g); |
---|
116 | do { |
---|
117 | path_cost += get(weight_map, edge(parent[v], v, g).first); |
---|
118 | child = v; |
---|
119 | v = parent[v]; |
---|
120 | } while (v != parent[v]); |
---|
121 | rtable << vertex_attr_map[child]["label"] << " "; |
---|
122 | rtable << path_cost << std::endl; |
---|
123 | |
---|
124 | } |
---|
125 | |
---|
126 | return EXIT_SUCCESS; |
---|
127 | } |
---|