blob: ab619c6a5c897c07d89bbd409d2d73ce7fd97f88 [file] [log] [blame]
Alexander Afanasyevad3757f2012-04-17 10:27:59 -07001/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
2/*
3 * Copyright (c) 2012 University of California, Los Angeles
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License version 2 as
7 * published by the Free Software Foundation;
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 *
18 * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
19 */
20
21
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070022#ifndef BOOST_GRAPH_NDN_GLOBAL_ROUTING_HELPER_H
23#define BOOST_GRAPH_NDN_GLOBAL_ROUTING_HELPER_H
Alexander Afanasyevad3757f2012-04-17 10:27:59 -070024
Alexander Afanasyev6315ef72012-06-01 20:56:31 -070025/// @cond include_hidden
26
Alexander Afanasyevad3757f2012-04-17 10:27:59 -070027#include <boost/graph/graph_traits.hpp>
28#include <boost/graph/properties.hpp>
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -070029#include <boost/ref.hpp>
Alexander Afanasyevad3757f2012-04-17 10:27:59 -070030
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070031#include "ns3/ndn-face.h"
Alexander Afanasyevad3757f2012-04-17 10:27:59 -070032#include "ns3/node-list.h"
33#include "ns3/channel-list.h"
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070034#include "../model/ndn-global-router.h"
Alexander Afanasyevad3757f2012-04-17 10:27:59 -070035#include <list>
36#include <map>
37
38namespace boost
39{
40
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070041class NdnGlobalRouterGraph
Alexander Afanasyevad3757f2012-04-17 10:27:59 -070042{
43public:
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070044 typedef ns3::Ptr< ns3::NdnGlobalRouter > Vertice;
Alexander Afanasyevad3757f2012-04-17 10:27:59 -070045 typedef uint16_t edge_property_type;
46 typedef uint32_t vertex_property_type;
47
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070048 NdnGlobalRouterGraph ()
Alexander Afanasyevad3757f2012-04-17 10:27:59 -070049 {
50 for (ns3::NodeList::Iterator node = ns3::NodeList::Begin (); node != ns3::NodeList::End (); node++)
51 {
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070052 ns3::Ptr<ns3::NdnGlobalRouter> gr = (*node)->GetObject<ns3::NdnGlobalRouter> ();
Alexander Afanasyevad3757f2012-04-17 10:27:59 -070053 if (gr != 0)
54 m_vertices.push_back (gr);
55 }
56
57 for (ns3::ChannelList::Iterator channel = ns3::ChannelList::Begin (); channel != ns3::ChannelList::End (); channel++)
58 {
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070059 ns3::Ptr<ns3::NdnGlobalRouter> gr = (*channel)->GetObject<ns3::NdnGlobalRouter> ();
Alexander Afanasyevad3757f2012-04-17 10:27:59 -070060 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
71public:
72 std::list< Vertice > m_vertices;
73};
74
75
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070076class ndn_global_router_graph_category :
Alexander Afanasyevad3757f2012-04-17 10:27:59 -070077 public virtual vertex_list_graph_tag,
78 public virtual incidence_graph_tag
79{
80};
81
82
83template<>
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070084struct graph_traits< NdnGlobalRouterGraph >
Alexander Afanasyevad3757f2012-04-17 10:27:59 -070085{
86 // Graph concept
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070087 typedef NdnGlobalRouterGraph::Vertice vertex_descriptor;
88 typedef ns3::NdnGlobalRouter::Incidency edge_descriptor;
Alexander Afanasyevad3757f2012-04-17 10:27:59 -070089 typedef directed_tag directed_category;
90 typedef disallow_parallel_edge_tag edge_parallel_category;
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070091 typedef ndn_global_router_graph_category traversal_category;
Alexander Afanasyevad3757f2012-04-17 10:27:59 -070092
93 // VertexList concept
94 typedef std::list< vertex_descriptor >::const_iterator vertex_iterator;
95 typedef size_t vertices_size_type;
96
97 // AdjacencyGraph concept
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070098 typedef ns3::NdnGlobalRouter::IncidencyList::iterator out_edge_iterator;
Alexander Afanasyevad3757f2012-04-17 10:27:59 -070099 typedef size_t degree_size_type;
100
101 // typedef size_t edges_size_type;
102};
103
104} // namespace boost
105
106namespace boost
107{
108
109inline
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700110graph_traits< NdnGlobalRouterGraph >::vertex_descriptor
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700111source(
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700112 graph_traits< NdnGlobalRouterGraph >::edge_descriptor e,
113 const NdnGlobalRouterGraph& g)
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700114{
115 return e.get<0> ();
116}
117
118inline
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700119graph_traits< NdnGlobalRouterGraph >::vertex_descriptor
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700120target(
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700121 graph_traits< NdnGlobalRouterGraph >::edge_descriptor e,
122 const NdnGlobalRouterGraph& g)
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700123{
124 return e.get<2> ();
125}
126
127inline
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700128std::pair< graph_traits< NdnGlobalRouterGraph >::vertex_iterator,
129 graph_traits< NdnGlobalRouterGraph >::vertex_iterator >
130vertices (const NdnGlobalRouterGraph&g)
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700131{
132 return make_pair (g.GetVertices ().begin (), g.GetVertices ().end ());
133}
134
135inline
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700136graph_traits< NdnGlobalRouterGraph >::vertices_size_type
137num_vertices(const NdnGlobalRouterGraph &g)
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700138{
139 return g.GetVertices ().size ();
140}
141
142
143inline
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700144std::pair< graph_traits< NdnGlobalRouterGraph >::out_edge_iterator,
145 graph_traits< NdnGlobalRouterGraph >::out_edge_iterator >
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700146out_edges(
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700147 graph_traits< NdnGlobalRouterGraph >::vertex_descriptor u,
148 const NdnGlobalRouterGraph& g)
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700149{
150 return std::make_pair(u->GetIncidencies ().begin (),
151 u->GetIncidencies ().end ());
152}
153
154inline
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700155graph_traits< NdnGlobalRouterGraph >::degree_size_type
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700156out_degree(
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700157 graph_traits< NdnGlobalRouterGraph >::vertex_descriptor u,
158 const NdnGlobalRouterGraph& g)
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700159{
160 return u->GetIncidencies ().size ();
161}
162
163
164//////////////////////////////////////////////////////////////
165// Property maps
166
167struct EdgeWeights
168{
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700169 EdgeWeights (const NdnGlobalRouterGraph &graph)
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700170 : m_graph (graph)
171 {
172 }
173
174private:
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700175 const NdnGlobalRouterGraph &m_graph;
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700176};
177
178
179struct VertexIds
180{
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700181 VertexIds (const NdnGlobalRouterGraph &graph)
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700182 : m_graph (graph)
183 {
184 }
185
186private:
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700187 const NdnGlobalRouterGraph &m_graph;
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700188};
189
190template<>
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700191struct property_map< NdnGlobalRouterGraph, edge_weight_t >
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700192{
193 typedef const EdgeWeights const_type;
194 typedef EdgeWeights type;
195};
196
197template<>
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700198struct property_map< NdnGlobalRouterGraph, vertex_index_t >
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700199{
200 typedef const VertexIds const_type;
201 typedef VertexIds type;
202};
203
204
205template<>
206struct property_traits< EdgeWeights >
207{
208 // Metric property map
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700209 typedef tuple< ns3::Ptr<ns3::NdnFace>, uint16_t > value_type;
210 typedef tuple< ns3::Ptr<ns3::NdnFace>, uint16_t > reference;
211 typedef ns3::NdnGlobalRouter::Incidency key_type;
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700212 typedef readable_property_map_tag category;
213};
214
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -0700215const property_traits< EdgeWeights >::value_type WeightZero (0, 0);
216const property_traits< EdgeWeights >::value_type WeightInf (0, std::numeric_limits<uint16_t>::max ());
217
218struct WeightCompare :
219 public std::binary_function<property_traits< EdgeWeights >::reference,
220 property_traits< EdgeWeights >::reference,
221 bool>
222{
223 bool
224 operator () (property_traits< EdgeWeights >::reference a,
225 property_traits< EdgeWeights >::reference b) const
226 {
227 return a.get<1> () < b.get<1> ();
228 }
229
230 bool
231 operator () (property_traits< EdgeWeights >::reference a,
232 uint32_t b) const
233 {
234 return a.get<1> () < b;
235 }
236
237 bool
238 operator () (uint32_t a,
239 uint32_t b) const
240 {
241 return a < b;
242 }
243
244};
245
246struct WeightCombine :
247 public std::binary_function<uint32_t,
248 property_traits< EdgeWeights >::reference,
249 uint32_t>
250{
251 uint32_t
252 operator () (uint32_t a, property_traits< EdgeWeights >::reference b) const
253 {
254 return a + b.get<1> ();
255 }
256
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700257 tuple< ns3::Ptr<ns3::NdnFace>, uint32_t >
258 operator () (tuple< ns3::Ptr<ns3::NdnFace>, uint32_t > a,
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -0700259 property_traits< EdgeWeights >::reference b) const
260 {
261 if (a.get<0> () == 0)
262 return make_tuple (b.get<0> (), a.get<1> () + b.get<1> ());
263 else
264 return make_tuple (a.get<0> (), a.get<1> () + b.get<1> ());
265 }
266};
267
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700268template<>
269struct property_traits< VertexIds >
270{
271 // Metric property map
272 typedef uint32_t value_type;
273 typedef uint32_t reference;
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700274 typedef ns3::Ptr< ns3::NdnGlobalRouter > key_type;
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700275 typedef readable_property_map_tag category;
276};
277
278
279inline EdgeWeights
280get(edge_weight_t,
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700281 const NdnGlobalRouterGraph &g)
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700282{
283 return EdgeWeights (g);
284}
285
286
287inline VertexIds
288get(vertex_index_t,
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700289 const NdnGlobalRouterGraph &g)
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700290{
291 return VertexIds (g);
292}
293
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -0700294template<class M, class K, class V>
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700295inline void
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -0700296put (reference_wrapper< M > mapp,
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700297 K a, V p)
298{
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -0700299 mapp.get ()[a] = p;
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700300}
301
302// void
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700303// put (cref< std::map< ns3::Ptr<ns3::NdnGlobalRouter>, ns3::Ptr<ns3::NdnGlobalRouter> > > map,
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700304
305uint32_t
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700306get (const boost::VertexIds&, ns3::Ptr<ns3::NdnGlobalRouter> &gr)
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700307{
308 return gr->GetId ();
309}
310
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -0700311inline property_traits< EdgeWeights >::reference
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700312get(const boost::EdgeWeights&, ns3::NdnGlobalRouter::Incidency &edge)
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700313{
314 if (edge.get<1> () == 0)
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -0700315 return property_traits< EdgeWeights >::reference (0, 0);
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700316 else
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -0700317 return property_traits< EdgeWeights >::reference (edge.get<1> (), edge.get<1> ()->GetMetric ());
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700318}
319
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700320struct PredecessorsMap :
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700321 public std::map< ns3::Ptr< ns3::NdnGlobalRouter >, ns3::Ptr< ns3::NdnGlobalRouter > >
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700322{
323};
324
325template<>
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -0700326struct property_traits< reference_wrapper<PredecessorsMap> >
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700327{
328 // Metric property map
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700329 typedef ns3::Ptr< ns3::NdnGlobalRouter > value_type;
330 typedef ns3::Ptr< ns3::NdnGlobalRouter > reference;
331 typedef ns3::Ptr< ns3::NdnGlobalRouter > key_type;
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700332 typedef read_write_property_map_tag category;
333};
334
335
336struct DistancesMap :
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700337 public std::map< ns3::Ptr< ns3::NdnGlobalRouter >, tuple< ns3::Ptr<ns3::NdnFace>, uint32_t > >
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700338{
339};
340
341template<>
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -0700342struct property_traits< reference_wrapper<DistancesMap> >
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700343{
344 // Metric property map
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700345 typedef tuple< ns3::Ptr<ns3::NdnFace>, uint32_t > value_type;
346 typedef tuple< ns3::Ptr<ns3::NdnFace>, uint32_t > reference;
347 typedef ns3::Ptr< ns3::NdnGlobalRouter > key_type;
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700348 typedef read_write_property_map_tag category;
349};
350
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700351inline tuple< ns3::Ptr<ns3::NdnFace>, uint32_t >
352get (DistancesMap &map, ns3::Ptr<ns3::NdnGlobalRouter> key)
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700353{
354 boost::DistancesMap::iterator i = map.find (key);
355 if (i == map.end ())
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700356 return tuple< ns3::Ptr<ns3::NdnFace>, uint32_t > (0, std::numeric_limits<uint32_t>::max ());
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700357 else
358 return i->second;
359}
360
361} // namespace boost
362
Alexander Afanasyev6315ef72012-06-01 20:56:31 -0700363/// @endcond
364
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700365#endif // BOOST_GRAPH_NDN_GLOBAL_ROUTING_HELPER_H