Statistics
| Branch: | Revision:

## root / latex / note_w09.tex @ 46d9d2ec

 1 %!TEX root = note.tex  %%%%%%%%%%%%%%%%%%  % WEEK 9  %%%%%%%%%%%%%%%%%%  \section{Week 9}  \subsection{Betweenness Centrality}   \href{http://www.boost.org/doc/libs/1_32_0/libs/graph/doc/betweenness_centrality.html}{Official doc}   \textbf{How to create Read/Write Property Map}   The type CentralityMap must be a model of Read/Write Property Map,   with the graph's vertex descriptor type as its key type.   The value type of this property map should be a floating-point or rational type.   \textbf{listS vs vectorS}   I use \lstinline{listS}, how can I refer to a single vertex.   \textbf{iterator_property_map}   This property map is an adaptor that converts any Random Access Iterator into a Lvalue Property Map. The OffsetMap type is responsible for converting key objects to integers that can be used as offsets with the random access iterator.   \href{http://ci.boost.org/svn-trac/browser/boost%20SVN/sandbox/graph-v2/boost/property_map/iterator_property_map.hpp?rev=39140}{Source code}   \begin{lstlisting}  // The iterator property map povides get() and put() functions for random  // access containers such that their random access iterators act as the  // key type for access.  // Iterator property maps rely on a index map (which is also a property map)  // that provides, via its get() function, an offset from the iterator supplied  // during construction of this property map. The index map generally gives  // a value who's type is convertible to the iterator's difference_type.  iterator_property_map<   RandomAccessIterator,   IndexMap,   Type,   Reference  >   \end{lstlisting}   \textbf{associative_property_map}   This property map is an adaptor that converts any type that is a model of both Pair Associative Container and Unique Associative Container such as std::map into a mutable Lvalue Property Map. Note that the adaptor only retains a reference to the container, so the lifetime of the container must encompass the use of the adaptor.   \href{http://ci.boost.org/svn-trac/browser/boost%20SVN/sandbox/graph-v2/boost/property_map/associative_property_map.hpp}{Source code}   \begin{lstlisting}  associative_property_map   \end{lstlisting}   \lstinline{num_vertices}   n = num_vertices(A) returns the number of vertices in graph A.   \textbf{Property Map for Graph using listS}   \href{http://stackoverflow.com/questions/15432104/how-to-create-a-propertymap-for-a-boost-graph-using-lists-as-vertex-container}{Answers on Stack Overflow}   http://stackoverflow.com/questions/7156880/dijkstra-shortest-path-with-vertexlist-lists-in-boost-graph   http://stackoverflow.com/questions/30263594/adding-a-vertex-index-to-lists-graph-on-the-fly-for-betweenness-centrality   \begin{lstlisting}  // (2) fill constructor  // Constructs a container with n elements. Each element is a copy of val.  std::vector< double > v_centrality_vec(boost::num_vertices(g), 0.0);   \end{lstlisting}   \subsubsection{Calculating Centrality - Code Explanation}   \begin{lstlisting}   // http://stackoverflow.com/questions/15432104/how-to-create-a-propertymap-for-a-boost-graph-using-lists-as-vertex-container   typedef std::map StdVertexIndexMap;   StdVertexIndexMap idxMap;   typedef boost::associative_property_map VertexIndexMap;   VertexIndexMap v_index(idxMap);   \end{lstlisting}   The \lstinline{v_index} is an \emph{Associative Property Map}, it's used to retrieve the \lstinline{associated_vertex_index} from the \lstinline{vertex_iterator}. With a list, we cannot retrieve the \lstinline{vertex_descriptor} with an integer. With \lstinline{v_index}, we can retrieve the appropriate integer associated with each vertex. This will be used later for \lstinline{brandes_betweenness_centrality()}   We also need to create a \lstinline{std::map<> idxMap}, since the Associative Property Map needs a real data structure (in this case, an \lstinline{std::map}) to \lstinline{put, get} value.   \begin{lstlisting}  typedef std::vector CentralityVec;  CentralityVec v_centrality_vec(boost::num_vertices(g), 0);   \end{lstlisting}   This one is one of the most important variable. This one is used to \textbf{save the centrality score} for each vertex. Notice that here, we use \lstinline{std::vector}. This vector has a length equal to the number of vertices. And each vertex, through the \lstinline{v_index} map, can retrieve its centrality score.   \begin{lstlisting}  # iterator_property_map<   RandomAccessIterator,   IndexMap,   Type,   Reference  >  typedef boost::iterator_property_map< CentralityVec::iterator, VertexIndexMap, double> CentralityMap;  CentralityMap v_centrality_map(v_centrality_vec.begin(), v_index);   \end{lstlisting}   The \lstinline{v_centrality_vec} is an \emph{Iterator Property Map}, this one is used to retrieve the value of the centrality score with some integer index.   \begin{lstlisting}  template  inline void  update_centrality(CentralityMap centrality_map, Key k, const T& x)  { put(centrality_map, k, get(centrality_map, k) + x); }  # Usage example  std::vector dependency(V);  update_centrality(centrality, w, get(dependency, w));   \end{lstlisting}   Piece of code used by \lstinline{brandes_betweenness_centrality()} to change value of centrality.   \textbf{MANTRA:} I still GOT STUCK. But I guess it's enough for today. Let myself have a peaceful sleep tonight. I deserve every bit of it. And I believe that sooner or later, I'll have it figured out.   \subsubsection{AHAHAA SOLUTION!!!!}   It turns out that I called the function \lstinline{relative_betweenness_centrality} in the wrong way. I should not use the prefix \lstinline{boost::centrality_map} before.   Now everything is working, and it \textbf{COSTS} me 2 days for the problem arising with Copy and Paste.   \begin{lstlisting}  // Wrong version  brandes_betweenness_centrality( g, boost::centrality_map(v_centrality_map)  // Right version  relative_betweenness_centrality( g, v_centrality_map);   \end{lstlisting}