Statistics
| Branch: | Revision:

## root / latex / note_w08.tex @ d1ed66aa

 1 %!TEX root = note.tex  %%%%%%%%%%%%%%%%%%  % WEEK 8  %%%%%%%%%%%%%%%%%%  \section{Week 8}  \subsection{Read the file}   \href{http://stackoverflow.com/questions/195323/what-is-the-most-elegant-way-to-read-a-text-file-with-c}{Few   ways to read from a text file}   \begin{lstlisting}  template string (InputIterator begin, InputIterator end);  std::vector v;  std::string str(v.begin(),v.end());   \end{lstlisting}   \textbf{Split single line}   \textbf{Tuple of exactly 3 elements and STL}   Use \lstinline{array} instead  \subsection{Create graph for Simple Input}   \subsubsection{Graph with weight}   \subsubsection{What is it with the name of the vertex?}   Should I create a set of vertices, then creating a whole set of vertices first, and then adding the edges.   How to use PropertyMap?   http://stackoverflow.com/questions/28780137/create-graphs-from-a-file-using-boost-library   \begin{lstlisting}[caption="Graph with Customized Property", label="property-customized"]  //vertex  struct VertexProperties  {   int id;   int label;   VertexProperties(){}   VertexProperties(unsigned i, unsigned l) : id(i), label(l) {}  };  //edge  struct EdgeProperties  {   unsigned id;   unsigned label;   EdgeProperties(){}   EdgeProperties(unsigned i, unsigned l) : id(i), label(l) {}  };  //Graph  struct GraphProperties  {   unsigned id;   unsigned label;   GraphProperties() {}   GraphProperties(unsigned i, unsigned l) : id(i), label(l) {}  };  //adjacency list  typedef boost::adjacency_list<   boost::vecS, boost::vecS, boost::directedS,   VertexProperties,   EdgeProperties,   GraphProperties  > Graph;  Graph g(GraphProperties(gid,gid));  boost::add_vertex(VertexProperties(vId, vLabel), g);   \end{lstlisting}   \begin{lstlisting}[caption="Graph with default property (== no\_property)", label="no-property"]  typedef boost::adjacency_list Graph;  Graph g(3); // Create a graph with 3 vertices.   \end{lstlisting}   \begin{lstlisting}  // from http://programmingexamples.net/wiki/CPP/Boost/BGL/EdgeProperties  typedef boost::property EdgeWeightProperty;  typedef boost::adjacency_list Graph;  Graph g;  EdgeWeightProperty e1 = 5;  add_edge(0, 1, e1, g);   \end{lstlisting}   \subsubsection{Multiple properties for Edge/Vertex}   According to \href{http://stackoverflow.com/questions/11277820/bgl-adding-an-edge-with-multiple-properties}{an answer in StackOverflow}, it's better to use \lstinline{Bundled Properties} instead of \lstinline{property chains} in \lstinline{boost}   Read more in \href{http://www.boost.org/doc/libs/1_41_0/libs/graph/doc/bundles.html}{official doc}   \subsubsection{Performance when creating graph}   I think it doesn't matter much, but my mind is occupied by that small detail thing. So I'll write it down:   \begin{itemize}   \item Choosing \lstinline{listS} or \lstinline{vecS} for the VertexSet ==> I think \lstinline{listS} makes more sense. Since in the text file, we do not have any index to refer to. So the \lstinline{RandomAccessIterator} offered by \lstinline{vector} doesn't really contribute to anything here.   \item I was thinking about using \lstinline{boost::vecS} for \lstinline{VertexList} template argument. However, \lstinline{vecS} doesn't model the \emph{Sequence Container}, so it's out of the question.   \end{itemize}   \subsubsection{Iterating over edges/vertices}   http://stackoverflow.com/questions/15812663/iterating-over-edges-of-a-graph-using-range-based-for   \subsubsection{Get vertex descriptor from the vertex iterator}   Is \href{http://stackoverflow.com/questions/2244580/find-boost-bgl-vertex-by-a-key}{labelled graph} a solution?   "I would prefer the way of having an additional map which maps the name of the data to the corresponding vertex. Further, you can encapsulate your algorithm in a class or a function, so that when adding a new vertex the map is filled automatically."   \begin{lstlisting}   typedef float Weight;   typedef boost::property WeightProperty;   typedef boost::property NameProperty;   typedef boost::adjacency_list < boost::listS, boost::vecS, boost::directedS,   NameProperty, WeightProperty > Graph;   typedef boost::graph_traits < Graph >::vertex_descriptor Vertex;   typedef boost::property_map < Graph, boost::vertex_index_t >::type IndexMap;   typedef boost::property_map < Graph, boost::vertex_name_t >::type NameMap;  template  void foo(AddressMap address)  {  typedef typename boost::property traits::value type value type;  typedef typename boost::property traits::key type key type;  value type old address, new address;  key type fred = "Fred";  old address = get(address, fred);  new address = "384 Fitzpatrick Street"  put(address, fred, new address);  key type joe = "Joe";  value type& joes address = address[joe];  joes address = "325 Cushing Avenue";  }  property  typedef property map::type actor name map t;  actor name map t actor name = get(vertex name, g);  typedef property map::type movie name map t;  movie name map t connecting movie = get(edge name, g);  typedef graph traits::vertex descriptor Vertex;  typedef std::map NameVertexMap;  NameVertexMap actors;   \end{lstlisting}  To ensure that each vertex is only added once to the graph, a map from actor  names to their vertices is used. As vertices are added to the graph, subsequent appearances of  the same vertex (as part of a different edge) can be linked with the correct vertex already in  the graph. This mapping is readily accomplished using std::map   \subsubsection{Get type of Property Map}   \textbf{Get type of default property map}   \begin{lstlisting}  typedef adjacency list,  property > Graph;  Graph g;  typedef property_map::type actor_name_map_t;  actor_name_map_t actor name = get(vertex name, g);   \end{lstlisting}   \textbf{Get type of bundled properties}   There is currently no support for creating property maps from the bundled properties of a graph.   To get the type of the vertex or edge bundle for a given graph type Graph, you can use the trait classes vertex_bundle_type and edge_bundle_type. The type vertex_bundle_type::type will be the type bundled with vertices (or no_vertex_bundle if the graph supports bundles but no vertex bundle exists). Likewise, edge_bundle_type::type will be the type bundled with edges (or no_edge_bundle if no edge bundle exists).   Then we can the type for one object in \lstinline{struct}   \begin{lstlisting}  #include  struct Router {   string id;   string name;   Router(){};   Router(string id, string name) : id(id), name(name) {}  };  struct Link {   double cost;   Link(){};   Link(double cost) : cost(cost) {};  };  typedef boost::adjacency_list Graph;  Graph g;  typedef vertex_bundle_type::type vertex_bundle_t;  typedef BOOST_TYPEOF(vertex_bundle_t.name) router_id_t;  router_id_t router_id = get(&vertex_bundle_t::id, g);   \end{lstlisting}   \subsubsection{How to update the value for bundled properties}   \begin{lstlisting}  // Assume that id is in the bundled property of a vertex.  Vertex v; // vertex descriptor  g[v].id = "123"   \end{lstlisting}   \subsubsection{Overload ostream for a vertex with bundled properties}   NOT WORKING YET   \subsection{Create graph for OLSR Json Input}   \subsubsection{Read Json with Boost}   http://stackoverflow.com/questions/17124652/how-can-i-parse-json-arrays-with-c-boost   \subsection{Applying the betweeness centrality}   The graph object on which the algorithm will be applied. The type Graph must be a model of Vertex List Graph and Incidence Graph. When an edge centrality map is supplied, it must also model Edge List Graph.   \href{http://programmingexamples.net/wiki/CPP/Boost/BGL/BetweennessCentralityClustering}{Example} on how to use Brandes Betweenness Centrality.   \textbf{Is the \emph{Adjacency List} the same as \emph{Vertex List Graph}}   \textbf{What is the differences between \emph{named parameter versions} and \emph{non-named parameter versions}}   Answer can be found \href{http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/bgl_named_params.html}{here}   A better solution is provided by bgl_named_params. This class allows users to provide parameters is any order, and matches arguments to parameters based on parameter names.   Each of the named parameters is separated by a period, not a comma.   \begin{lstlisting}  //Both of the callings below are the same  bool r = boost::bellman_ford_shortest_paths(g, int(N),   boost::weight_map(weight).   distance_map(&distance).   predecessor_map(&parent));  bool r = boost::bellman_ford_shortest_paths(g, int(N),   boost::predecessor_map(&parent).   distance_map(&distance).   weight_map(weight));   \end{lstlisting}   \subsection{Property Map}   http://www.boost.org/doc/libs/1_52_0/libs/property_map/doc/ReadWritePropertyMap.html   http://www.boost.org/doc/libs/1_52_0/libs/property_map/doc/property_map.html   \subsection{Faster way to create Graph}   \textbf{Vector as Graph}   \href{http://ecee.colorado.edu/~siek/boostcon2010bgl.pdf}{Check out page 34}   https://github.com/boostorg/graph/blob/master/example/vector-as-graph.cpp   But I think that this way is not efficient.   \subsection{To Do}   http://www.ist.tugraz.at/_attach/Publish/Akswt04/BOOST_Werner_Trobin.pdf