Initial support for route calculations with Boost.Graph library (BGL)
diff --git a/helper/boost-graph-ccnx-global-routing-helper.h b/helper/boost-graph-ccnx-global-routing-helper.h
new file mode 100644
index 0000000..3711278
--- /dev/null
+++ b/helper/boost-graph-ccnx-global-routing-helper.h
@@ -0,0 +1,307 @@
+/* -*-  Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+
+#ifndef BOOST_GRAPH_CCNX_GLOBAL_ROUTING_HELPER_H
+#define BOOST_GRAPH_CCNX_GLOBAL_ROUTING_HELPER_H
+
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/properties.hpp>
+
+#include "ns3/node-list.h"
+#include "ns3/channel-list.h"
+#include "../model/ccnx-global-router.h"
+#include <list>
+#include <map>
+
+namespace boost
+{
+
+class CcnxGlobalRouterGraph
+{
+public:
+  typedef ns3::Ptr< ns3::CcnxGlobalRouter > Vertice;
+  typedef uint16_t edge_property_type;
+  typedef uint32_t vertex_property_type;
+  
+  CcnxGlobalRouterGraph ()
+  {
+    for (ns3::NodeList::Iterator node = ns3::NodeList::Begin (); node != ns3::NodeList::End (); node++)
+      {
+        ns3::Ptr<ns3::CcnxGlobalRouter> gr = (*node)->GetObject<ns3::CcnxGlobalRouter> ();
+	if (gr != 0)
+	  m_vertices.push_back (gr);
+      }
+
+    for (ns3::ChannelList::Iterator channel = ns3::ChannelList::Begin (); channel != ns3::ChannelList::End (); channel++)
+      {
+        ns3::Ptr<ns3::CcnxGlobalRouter> gr = (*channel)->GetObject<ns3::CcnxGlobalRouter> ();
+	if (gr != 0)
+	  m_vertices.push_back (gr);
+      }
+  }
+
+  const std::list< Vertice > &
+  GetVertices () const
+  {
+    return m_vertices;
+  }
+  
+public:
+  std::list< Vertice > m_vertices;
+};
+
+
+class ccnx_global_router_graph_category :
+    public virtual vertex_list_graph_tag,
+    public virtual incidence_graph_tag
+{
+};
+
+
+template<>
+struct graph_traits< CcnxGlobalRouterGraph >
+{
+  // Graph concept
+  typedef CcnxGlobalRouterGraph::Vertice vertex_descriptor;
+  typedef ns3::CcnxGlobalRouter::Incidency edge_descriptor;
+  typedef directed_tag directed_category;
+  typedef disallow_parallel_edge_tag edge_parallel_category;
+  typedef ccnx_global_router_graph_category traversal_category;
+
+  // VertexList concept
+  typedef std::list< vertex_descriptor >::const_iterator vertex_iterator;
+  typedef size_t vertices_size_type;
+
+  // AdjacencyGraph concept
+  typedef ns3::CcnxGlobalRouter::IncidencyList::iterator out_edge_iterator;
+  typedef size_t degree_size_type;
+
+  // typedef size_t edges_size_type;
+};
+
+} // namespace boost
+
+namespace boost
+{
+
+inline
+graph_traits< CcnxGlobalRouterGraph >::vertex_descriptor
+source(
+       graph_traits< CcnxGlobalRouterGraph >::edge_descriptor e,
+       const CcnxGlobalRouterGraph& g)
+{
+  return e.get<0> ();
+}
+
+inline
+graph_traits< CcnxGlobalRouterGraph >::vertex_descriptor
+target(
+       graph_traits< CcnxGlobalRouterGraph >::edge_descriptor e,
+       const CcnxGlobalRouterGraph& g)
+{
+  return e.get<2> ();
+}
+
+inline
+std::pair< graph_traits< CcnxGlobalRouterGraph >::vertex_iterator,
+	   graph_traits< CcnxGlobalRouterGraph >::vertex_iterator >
+vertices (const CcnxGlobalRouterGraph&g)
+{
+  return make_pair (g.GetVertices ().begin (), g.GetVertices ().end ());
+}
+
+inline
+graph_traits< CcnxGlobalRouterGraph >::vertices_size_type
+num_vertices(const CcnxGlobalRouterGraph &g)
+{
+  return g.GetVertices ().size ();
+}
+  
+
+inline
+std::pair< graph_traits< CcnxGlobalRouterGraph >::out_edge_iterator,
+	   graph_traits< CcnxGlobalRouterGraph >::out_edge_iterator >  
+out_edges(
+	  graph_traits< CcnxGlobalRouterGraph >::vertex_descriptor u, 
+	  const CcnxGlobalRouterGraph& g)
+{
+  return std::make_pair(u->GetIncidencies ().begin (),
+			u->GetIncidencies ().end ());
+}
+
+inline
+graph_traits< CcnxGlobalRouterGraph >::degree_size_type
+out_degree(
+	  graph_traits< CcnxGlobalRouterGraph >::vertex_descriptor u, 
+	  const CcnxGlobalRouterGraph& g)
+{
+  return u->GetIncidencies ().size ();
+}
+
+
+//////////////////////////////////////////////////////////////
+// Property maps
+
+struct EdgeWeights
+{
+  EdgeWeights (const CcnxGlobalRouterGraph &graph)
+  : m_graph (graph)
+  { 
+  }
+
+private:
+  const CcnxGlobalRouterGraph &m_graph;
+};
+
+
+struct VertexIds
+{
+  VertexIds (const CcnxGlobalRouterGraph &graph)
+  : m_graph (graph)
+  { 
+  }
+
+private:
+  const CcnxGlobalRouterGraph &m_graph;
+};
+
+template<>
+struct property_map< CcnxGlobalRouterGraph, edge_weight_t >
+{
+  typedef const EdgeWeights const_type;
+  typedef EdgeWeights type;
+};
+
+template<>
+struct property_map< CcnxGlobalRouterGraph, vertex_index_t >
+{
+  typedef const VertexIds const_type;
+  typedef VertexIds type;
+};
+
+
+template<>
+struct property_traits< EdgeWeights >
+{
+  // Metric property map
+  typedef uint16_t value_type;
+  typedef uint16_t reference;
+  typedef ns3::CcnxGlobalRouter::Incidency key_type;
+  typedef readable_property_map_tag category;
+};
+
+template<>
+struct property_traits< VertexIds >
+{
+  // Metric property map
+  typedef uint32_t value_type;
+  typedef uint32_t reference;
+  typedef ns3::Ptr< ns3::CcnxGlobalRouter > key_type;
+  typedef readable_property_map_tag category;
+};
+
+
+inline EdgeWeights
+get(edge_weight_t,
+    const CcnxGlobalRouterGraph &g)
+{
+  return EdgeWeights (g);
+}
+
+
+inline VertexIds
+get(vertex_index_t,
+    const CcnxGlobalRouterGraph &g)
+{
+  return VertexIds (g);
+}
+
+template<class K, class V>
+inline void
+put (std::map<K,V> &mapp,
+     K a, V p)
+{
+  mapp[a] = p;
+}
+
+// void
+// put (cref< std::map< ns3::Ptr<ns3::CcnxGlobalRouter>, ns3::Ptr<ns3::CcnxGlobalRouter> > > map,
+
+uint32_t
+get (const boost::VertexIds&, ns3::Ptr<ns3::CcnxGlobalRouter> &gr)
+{
+  return gr->GetId ();
+}
+
+inline uint16_t
+get(const boost::EdgeWeights&, ns3::CcnxGlobalRouter::Incidency &edge)
+{
+  if (edge.get<1> () == 0)
+    return 0;
+  else
+    return edge.get<1> ()->GetMetric ();
+}
+
+
+struct PredecessorsMap :
+  public std::map< ns3::Ptr< ns3::CcnxGlobalRouter >, ns3::Ptr< ns3::CcnxGlobalRouter > >
+{
+};
+
+template<>
+struct property_traits< PredecessorsMap >
+{
+  // Metric property map
+  typedef ns3::Ptr< ns3::CcnxGlobalRouter > value_type;
+  typedef ns3::Ptr< ns3::CcnxGlobalRouter > reference;
+  typedef ns3::Ptr< ns3::CcnxGlobalRouter > key_type;
+  typedef read_write_property_map_tag category;
+};
+
+
+struct DistancesMap :
+  public std::map< ns3::Ptr< ns3::CcnxGlobalRouter >, uint32_t >
+{
+};
+
+template<>
+struct property_traits< DistancesMap >
+{
+  // Metric property map
+  typedef uint32_t value_type;
+  typedef uint32_t reference;
+  typedef ns3::Ptr< ns3::CcnxGlobalRouter > key_type;
+  typedef read_write_property_map_tag category;
+};
+
+inline uint32_t
+get (DistancesMap &map, ns3::Ptr<ns3::CcnxGlobalRouter> key)
+{
+  boost::DistancesMap::iterator i = map.find (key);
+  if (i == map.end ())
+    return std::numeric_limits<uint32_t>::max ();
+  else
+    return i->second;
+}
+
+} // namespace boost
+
+#endif // BOOST_GRAPH_CCNX_GLOBAL_ROUTING_HELPER_H
diff --git a/helper/ccnx-global-routing-helper.cc b/helper/ccnx-global-routing-helper.cc
new file mode 100644
index 0000000..63e202e
--- /dev/null
+++ b/helper/ccnx-global-routing-helper.cc
@@ -0,0 +1,258 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2011 UCLA
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author:  Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "ccnx-global-routing-helper.h"
+
+#include "ns3/ccnx.h"
+#include "../model/ccnx-net-device-face.h"
+#include "../model/ccnx-global-router.h"
+#include "ns3/ccnx-name-components.h"
+
+#include "ns3/node.h"
+#include "ns3/net-device.h"
+#include "ns3/channel.h"
+#include "ns3/log.h"
+#include "ns3/assert.h"
+#include "ns3/names.h"
+#include "ns3/node-list.h"
+#include "ns3/channel-list.h"
+
+#include <boost/lexical_cast.hpp>
+#include "boost-graph-ccnx-global-routing-helper.h"
+
+NS_LOG_COMPONENT_DEFINE ("CcnxGlobalRoutingHelper");
+
+using namespace std;
+using namespace boost;
+
+namespace ns3 {
+
+void
+CcnxGlobalRoutingHelper::Install (Ptr<Node> node)
+{
+  NS_LOG_LOGIC ("Node: " << node->GetId ());
+  
+  Ptr<Ccnx> ccnx = node->GetObject<Ccnx> ();
+  NS_ASSERT_MSG (ccnx != 0, "Cannot install CcnxGlobalRoutingHelper before Ccnx is installed on a node");
+
+  Ptr<CcnxGlobalRouter> gr = node->GetObject<CcnxGlobalRouter> ();
+  if (gr != 0)
+    {
+      NS_LOG_DEBUG ("CcnxGlobalRouter is already installed: " << gr);
+      return; // already installed
+    }
+  
+  gr = CreateObject<CcnxGlobalRouter> ();
+  node->AggregateObject (gr);
+  
+  for (uint32_t faceId = 0; faceId < ccnx->GetNFaces (); faceId++)
+    {
+      Ptr<CcnxNetDeviceFace> face = DynamicCast<CcnxNetDeviceFace> (ccnx->GetFace (faceId));
+      if (face == 0)
+	{
+	  NS_LOG_DEBUG ("Skipping non-netdevice face");
+	  continue;
+	}
+      
+      Ptr<NetDevice> nd = face->GetNetDevice ();
+      if (nd == 0)
+	{
+	  NS_LOG_DEBUG ("Not a NetDevice associated with CcnxNetDeviceFace");
+	  continue;
+	}
+      
+      Ptr<Channel> ch = nd->GetChannel ();
+
+      if (ch == 0)
+	{
+	  NS_LOG_DEBUG ("Channel is not associated with NetDevice");
+	  continue;
+	}
+
+      if (ch->GetNDevices () == 2) // e.g., point-to-point channel
+	{
+	  for (uint32_t deviceId = 0; deviceId < ch->GetNDevices (); deviceId ++)
+	    {
+	      Ptr<NetDevice> otherSide = ch->GetDevice (deviceId);
+	      if (nd == otherSide) continue;
+
+	      Ptr<Node> otherNode = otherSide->GetNode ();
+	      NS_ASSERT (otherNode != 0);
+	      
+	      Ptr<CcnxGlobalRouter> otherGr = otherNode->GetObject<CcnxGlobalRouter> ();
+	      if (otherGr == 0)
+		{
+		  Install (otherNode);
+		}
+	      otherGr = otherNode->GetObject<CcnxGlobalRouter> ();
+	      NS_ASSERT (otherGr != 0);
+	      gr->AddIncidency (face, otherGr);
+	    }
+	}
+      else
+	{
+	  Ptr<CcnxGlobalRouter> grChannel = ch->GetObject<CcnxGlobalRouter> ();
+	  if (grChannel == 0)
+	    {
+	      Install (ch);
+	    }
+	  grChannel = ch->GetObject<CcnxGlobalRouter> ();
+	  
+	  gr->AddIncidency (0, grChannel);
+	}
+    }
+}
+
+void
+CcnxGlobalRoutingHelper::Install (Ptr<Channel> channel)
+{
+  NS_LOG_LOGIC ("Channel: " << channel->GetId ());
+
+  Ptr<CcnxGlobalRouter> gr = channel->GetObject<CcnxGlobalRouter> ();
+  if (gr != 0)
+    return;
+
+  gr = CreateObject<CcnxGlobalRouter> ();
+  channel->AggregateObject (gr);
+  
+  for (uint32_t deviceId = 0; deviceId < channel->GetNDevices (); deviceId ++)
+    {
+      Ptr<NetDevice> dev = channel->GetDevice (deviceId);
+
+      Ptr<Node> node = dev->GetNode ();
+      NS_ASSERT (node != 0);
+
+      Ptr<CcnxGlobalRouter> grOther = node->GetObject<CcnxGlobalRouter> ();
+      if (grOther == 0)
+	{
+	  Install (node);
+	}
+      grOther = node->GetObject<CcnxGlobalRouter> ();
+      NS_ASSERT (grOther != 0);
+
+      gr->AddIncidency (0, grOther);
+    }
+}
+
+void
+CcnxGlobalRoutingHelper::AddOrigin (const std::string &prefix, Ptr<Node> node)
+{
+  Ptr<CcnxGlobalRouter> gr = node->GetObject<CcnxGlobalRouter> ();
+  NS_ASSERT_MSG (gr != 0,
+		 "CcnxGlobalRouter is not installed on the node");
+
+  Ptr<CcnxNameComponents> name = Create<CcnxNameComponents> (boost::lexical_cast<CcnxNameComponents> (prefix));
+  gr->AddLocalPrefix (name);  
+}
+
+void
+CcnxGlobalRoutingHelper::AddOrigin (const std::string &prefix, const std::string &nodeName)
+{
+  Ptr<Node> node = Names::Find<Node> (nodeName);
+  NS_ASSERT_MSG (node != 0, nodeName << "is not a Node");
+
+  AddOrigin (prefix, node);
+}
+
+} // namespace ns3
+
+
+
+#include <boost/concept/assert.hpp>
+#include <boost/graph/graph_concepts.hpp>
+// #include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/dijkstra_shortest_paths.hpp>
+
+namespace ns3 {
+
+void
+CcnxGlobalRoutingHelper::CalculateRoutes ()
+{
+  BOOST_CONCEPT_ASSERT(( VertexListGraphConcept< CcnxGlobalRouterGraph > ));
+  BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept< CcnxGlobalRouterGraph > ));
+  // BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept< CcnxGlobalRouterGraph,
+  // 						     graph_traits < CcnxGlobalRouterGraph >::edge_descriptor > ));
+  // BOOST_CONCEPT_ASSERT(( PropertyGraphConcept< CcnxGlobalRouterGraph,
+  // 					       graph_traits < CcnxGlobalRouterGraph >::edge_descriptor,
+  // 					       edge_weight_t> ));
+  // BOOST_CONCEPT_ASSERT(( PropertyMapConcept< CcnxGlobalRouterGraph, edge_weight_t,
+  // 					     graph_traits < CcnxGlobalRouterGraph >::edge_descriptor> ));
+
+  
+  CcnxGlobalRouterGraph graph;
+  Ptr<CcnxGlobalRouter> source = (*NodeList::Begin ())->GetObject<CcnxGlobalRouter> ();
+  
+  typedef graph_traits < CcnxGlobalRouterGraph >::vertex_descriptor vertex_descriptor;
+
+  PredecessorsMap predecessors;
+  DistancesMap    distances;
+  // std::map< vertex_descriptor, int > distances;
+  // std::vector<uint32_t> d (num_vertices (graph));
+  // std::vector<int> distances;
+  // std::map< vertex_descriptor, std::
+
+  dijkstra_shortest_paths (graph, source,
+  			   predecessor_map (predecessors)
+			   .
+  			   distance_map (distances)
+  			   );
+
+  // BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<CcnxGlobalRouterGraph> ));
+  // BOOST_CONCEPT_ASSERT(( MutableGraphConcept<CcnxGlobalRouterGraph> ));
+
+  // typedef adjacency_list < listS, vecS, undirectedS, no_property, property < edge_weight_t, uint16_t > > Graph;
+  // typedef Graph::vertex_descriptor Vertex;
+
+  // class Graph
+  // {
+  // public:
+  //   typedef Ptr<CcnxGlobalRouter> vertex_descriptor;
+  //   typedef pair< Ptr<CcnxGlobalRouter>, Ptr<CcnxGlobalRouter> > edge_descriptor;
+  //   typedef directed_tag directed_category;
+  //   typedef disallow_parallel_edge_tag edge_parallel_category;
+  //   typedef adjacency_graph_tag traversal_category;
+
+  //   typedef CcnxGlobalRouter::Incidency adjacency_iterator;
+
+  //   // null_vertex() ???
+  //   // adjacent_vertices(v, g) ???
+  // };
+  
+  // Graph graph;
+
+  // for (NodeList::Iterator node = NodeList::Begin (); node != NodeList::End (); node++)
+  //   {
+  //     Ptr<CcnxGlobalRouter> gr = (*node)->GetObject<CcnxGlobalRouter> ();
+  //     if (gr == 0)
+  // 	continue;
+
+  //     for (CcnxGlobalRouter::IncidencyList::const_iterator i = gr->GetIncidencies ().begin ();
+  // 	   i != gr->GetIncidencies ().end ();
+  // 	   i++)
+  // 	{
+  // 	  add_edge (gr, i->get<1> (), 10, graph);
+  // 	}
+  //     break;
+  //   }
+  
+}
+
+
+}
diff --git a/helper/ccnx-global-routing-helper.h b/helper/ccnx-global-routing-helper.h
new file mode 100644
index 0000000..0012d25
--- /dev/null
+++ b/helper/ccnx-global-routing-helper.h
@@ -0,0 +1,52 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2011 UCLA
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author:  Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef CCNX_GLOBAL_ROUTING_HELPER_H
+#define CCNX_GLOBAL_ROUTING_HELPER_H
+
+#include "ns3/ptr.h"
+
+namespace ns3 {
+
+class Node;
+class Channel;
+
+class CcnxGlobalRoutingHelper
+{
+public:
+  void
+  Install (Ptr<Node> node);
+  
+  void
+  Install (Ptr<Channel> channel);
+
+  void
+  AddOrigin (const std::string &prefix, Ptr<Node> node);
+
+  void
+  AddOrigin (const std::string &prefix, const std::string &nodeName);
+
+  void
+  CalculateRoutes ();
+};
+
+}
+
+#endif // CCNX_GLOBAL_ROUTING_HELPER_H