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