NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
boost-graph-ndn-global-routing-helper.hpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
20 #ifndef BOOST_GRAPH_NDN_GLOBAL_ROUTING_HELPER_H
21 #define BOOST_GRAPH_NDN_GLOBAL_ROUTING_HELPER_H
22 
24 
25 #include "ns3/ndnSIM/model/ndn-common.hpp"
26 
27 #include <boost/graph/graph_traits.hpp>
28 #include <boost/graph/properties.hpp>
29 #include <boost/ref.hpp>
30 
31 #include "ns3/ndnSIM/model/ndn-global-router.hpp"
32 
33 #include "ns3/node-list.h"
34 #include "ns3/channel-list.h"
35 
36 #include <list>
37 #include <map>
38 
39 namespace boost {
40 
41 class NdnGlobalRouterGraph {
42 public:
43  typedef ns3::Ptr<ns3::ndn::GlobalRouter> Vertice;
44  typedef uint16_t edge_property_type;
45  typedef uint32_t vertex_property_type;
46 
47  NdnGlobalRouterGraph()
48  {
49  for (ns3::NodeList::Iterator node = ns3::NodeList::Begin(); node != ns3::NodeList::End();
50  node++) {
51  ns3::Ptr<ns3::ndn::GlobalRouter> gr = (*node)->GetObject<ns3::ndn::GlobalRouter>();
52  if (gr != 0)
53  m_vertices.push_back(gr);
54  }
55 
56  for (ns3::ChannelList::Iterator channel = ns3::ChannelList::Begin();
57  channel != ns3::ChannelList::End(); channel++) {
58  ns3::Ptr<ns3::ndn::GlobalRouter> gr = (*channel)->GetObject<ns3::ndn::GlobalRouter>();
59  if (gr != 0)
60  m_vertices.push_back(gr);
61  }
62  }
63 
64  const std::list<Vertice>&
65  GetVertices() const
66  {
67  return m_vertices;
68  }
69 
70 public:
71  std::list<Vertice> m_vertices;
72 };
73 
74 class ndn_global_router_graph_category : public virtual vertex_list_graph_tag,
75  public virtual incidence_graph_tag {
76 };
77 
78 template<>
79 struct graph_traits<NdnGlobalRouterGraph> {
80  // Graph concept
81  typedef NdnGlobalRouterGraph::Vertice vertex_descriptor;
82  typedef ns3::ndn::GlobalRouter::Incidency edge_descriptor;
83  typedef directed_tag directed_category;
84  typedef disallow_parallel_edge_tag edge_parallel_category;
85  typedef ndn_global_router_graph_category traversal_category;
86 
87  // VertexList concept
88  typedef std::list<vertex_descriptor>::const_iterator vertex_iterator;
89  typedef size_t vertices_size_type;
90 
91  // AdjacencyGraph concept
92  typedef ns3::ndn::GlobalRouter::IncidencyList::iterator out_edge_iterator;
93  typedef size_t degree_size_type;
94 
95  // typedef size_t edges_size_type;
96 };
97 
98 } // namespace boost
99 
100 namespace boost {
101 
102 inline graph_traits<NdnGlobalRouterGraph>::vertex_descriptor
103 source(graph_traits<NdnGlobalRouterGraph>::edge_descriptor e, const NdnGlobalRouterGraph& g)
104 {
105  return std::get<0>(e);
106 }
107 
108 inline graph_traits<NdnGlobalRouterGraph>::vertex_descriptor
109 target(graph_traits<NdnGlobalRouterGraph>::edge_descriptor e, const NdnGlobalRouterGraph& g)
110 {
111  return std::get<2>(e);
112 }
113 
114 inline std::pair<graph_traits<NdnGlobalRouterGraph>::vertex_iterator,
115  graph_traits<NdnGlobalRouterGraph>::vertex_iterator>
116 vertices(const NdnGlobalRouterGraph& g)
117 {
118  return make_pair(g.GetVertices().begin(), g.GetVertices().end());
119 }
120 
121 inline graph_traits<NdnGlobalRouterGraph>::vertices_size_type
122 num_vertices(const NdnGlobalRouterGraph& g)
123 {
124  return g.GetVertices().size();
125 }
126 
127 inline std::pair<graph_traits<NdnGlobalRouterGraph>::out_edge_iterator,
128  graph_traits<NdnGlobalRouterGraph>::out_edge_iterator>
129 out_edges(graph_traits<NdnGlobalRouterGraph>::vertex_descriptor u, const NdnGlobalRouterGraph& g)
130 {
131  return std::make_pair(u->GetIncidencies().begin(), u->GetIncidencies().end());
132 }
133 
134 inline graph_traits<NdnGlobalRouterGraph>::degree_size_type
135 out_degree(graph_traits<NdnGlobalRouterGraph>::vertex_descriptor u, const NdnGlobalRouterGraph& g)
136 {
137  return u->GetIncidencies().size();
138 }
139 
141 // Property maps
142 
143 struct EdgeWeights {
144  EdgeWeights(const NdnGlobalRouterGraph& graph)
145  : m_graph(graph)
146  {
147  }
148 
149 private:
150  const NdnGlobalRouterGraph& m_graph;
151 };
152 
153 struct VertexIds {
154  VertexIds(const NdnGlobalRouterGraph& graph)
155  : m_graph(graph)
156  {
157  }
158 
159 private:
160  const NdnGlobalRouterGraph& m_graph;
161 };
162 
163 template<>
164 struct property_map<NdnGlobalRouterGraph, edge_weight_t> {
165  typedef const EdgeWeights const_type;
166  typedef EdgeWeights type;
167 };
168 
169 template<>
170 struct property_map<NdnGlobalRouterGraph, vertex_index_t> {
171  typedef const VertexIds const_type;
172  typedef VertexIds type;
173 };
174 
175 template<>
176 struct property_traits<EdgeWeights> {
177  // Metric property map
178  typedef std::tuple<std::shared_ptr<nfd::Face>, uint16_t, double> value_type;
179  typedef std::tuple<std::shared_ptr<nfd::Face>, uint16_t, double> reference;
180  typedef ns3::ndn::GlobalRouter::Incidency key_type;
181  typedef readable_property_map_tag category;
182 };
183 
184 const property_traits<EdgeWeights>::value_type WeightZero(nullptr, 0, 0.0);
185 const property_traits<EdgeWeights>::value_type
186  WeightInf(nullptr, std::numeric_limits<uint16_t>::max(), 0.0);
187 
188 struct WeightCompare : public std::binary_function<property_traits<EdgeWeights>::reference,
189  property_traits<EdgeWeights>::reference, bool> {
190  bool
191  operator()(std::tuple<std::shared_ptr<nfd::Face>, uint32_t, double> a,
192  std::tuple<std::shared_ptr<nfd::Face>, uint32_t, double> b) const
193  {
194  return std::get<1>(a) < std::get<1>(b);
195  }
196 
197  bool
198  operator()(property_traits<EdgeWeights>::reference a, uint32_t b) const
199  {
200  return std::get<1>(a) < b;
201  }
202 
203  bool
204  operator()(uint32_t a, uint32_t b) const
205  {
206  return a < b;
207  }
208 };
209 
210 struct WeightCombine
211  : public std::binary_function<uint32_t, property_traits<EdgeWeights>::reference, uint32_t> {
212  uint32_t
213  operator()(uint32_t a, property_traits<EdgeWeights>::reference b) const
214  {
215  return a + std::get<1>(b);
216  }
217 
218  std::tuple<std::shared_ptr<nfd::Face>, uint32_t, double>
219  operator()(std::tuple<std::shared_ptr<nfd::Face>, uint32_t, double> a,
220  property_traits<EdgeWeights>::reference b) const
221  {
222  if (std::get<0>(a) == nullptr)
223  return std::make_tuple(std::get<0>(b), std::get<1>(a) + std::get<1>(b),
224  std::get<2>(a) + std::get<2>(b));
225  else
226  return std::make_tuple(std::get<0>(a), std::get<1>(a) + std::get<1>(b),
227  std::get<2>(a) + std::get<2>(b));
228  }
229 };
230 
231 template<>
232 struct property_traits<VertexIds> {
233  // Metric property map
234  typedef uint32_t value_type;
235  typedef uint32_t reference;
236  typedef ns3::Ptr<ns3::ndn::GlobalRouter> key_type;
237  typedef readable_property_map_tag category;
238 };
239 
240 inline EdgeWeights
241 get(edge_weight_t, const NdnGlobalRouterGraph& g)
242 {
243  return EdgeWeights(g);
244 }
245 
246 inline VertexIds
247 get(vertex_index_t, const NdnGlobalRouterGraph& g)
248 {
249  return VertexIds(g);
250 }
251 
252 template<class M, class K, class V>
253 inline void
254 put(reference_wrapper<M> mapp, K a, V p)
255 {
256  mapp.get()[a] = p;
257 }
258 
259 // void
260 // put (cref< std::map< ns3::Ptr<ns3::ndn::GlobalRouter>, ns3::Ptr<ns3::ndn::GlobalRouter> > > map,
261 
262 inline uint32_t
263 get(const boost::VertexIds&, ns3::Ptr<ns3::ndn::GlobalRouter>& gr)
264 {
265  return gr->GetId();
266 }
267 
268 inline property_traits<EdgeWeights>::reference
269 get(const boost::EdgeWeights&, ns3::ndn::GlobalRouter::Incidency& edge)
270 {
271  if (std::get<1>(edge) == 0)
272  return property_traits<EdgeWeights>::reference(nullptr, 0, 0.0);
273  else {
274  return property_traits<EdgeWeights>::reference(std::get<1>(edge),
275  static_cast<uint16_t>(
276  std::get<1>(edge)->getMetric()),
277  0.0);
278  }
279 }
280 
281 struct PredecessorsMap
282  : public std::map<ns3::Ptr<ns3::ndn::GlobalRouter>, ns3::Ptr<ns3::ndn::GlobalRouter>> {
283 };
284 
285 template<>
286 struct property_traits<reference_wrapper<PredecessorsMap>> {
287  // Metric property map
288  typedef ns3::Ptr<ns3::ndn::GlobalRouter> value_type;
289  typedef ns3::Ptr<ns3::ndn::GlobalRouter> reference;
290  typedef ns3::Ptr<ns3::ndn::GlobalRouter> key_type;
291  typedef read_write_property_map_tag category;
292 };
293 
294 struct DistancesMap : public std::map<ns3::Ptr<ns3::ndn::GlobalRouter>,
295  std::tuple<std::shared_ptr<nfd::Face>, uint32_t, double>> {
296 };
297 
298 template<>
299 struct property_traits<reference_wrapper<DistancesMap>> {
300  // Metric property map
301  typedef std::tuple<std::shared_ptr<nfd::Face>, uint32_t, double> value_type;
302  typedef std::tuple<std::shared_ptr<nfd::Face>, uint32_t, double> reference;
303  typedef ns3::Ptr<ns3::ndn::GlobalRouter> key_type;
304  typedef read_write_property_map_tag category;
305 };
306 
307 } // boost
308 
309 namespace std {
310 template<>
311 class numeric_limits<std::tuple<std::shared_ptr<nfd::Face>, uint32_t, double>>
312 {
313 public:
314  typedef std::tuple<std::shared_ptr<nfd::Face>, uint32_t, double> value;
315  static value
316  max()
317  {
318  return boost::WeightInf;
319  }
320 };
321 }
322 
323 namespace boost {
324 
325 inline std::tuple<std::shared_ptr<nfd::Face>, uint32_t, double>
326 get(DistancesMap& map, ns3::Ptr<ns3::ndn::GlobalRouter> key)
327 {
328  boost::DistancesMap::iterator i = map.find(key);
329  if (i == map.end())
330  return std::tuple<std::shared_ptr<nfd::Face>, uint32_t,
331  double>(nullptr, std::numeric_limits<uint32_t>::max(), 0.0);
332  else
333  return i->second;
334 }
335 
336 } // namespace boost
337 
339 
340 #endif // BOOST_GRAPH_NDN_GLOBAL_ROUTING_HELPER_H
Class representing global router interface for ndnSIM.
std::tuple< Ptr< GlobalRouter >, shared_ptr< Face >, Ptr< GlobalRouter > > Incidency
Graph edge.
STL namespace.
Table::const_iterator iterator
Definition: cs-internal.hpp:41