Statistics
| Branch: | Revision:

root / latex / note_w09.tex @ 46d9d2ec

History | View | Annotate | Download (6.17 KB)

1
%!TEX root = note.tex
2

    
3
%%%%%%%%%%%%%%%%%%
4
% WEEK 9
5
%%%%%%%%%%%%%%%%%%
6
\section{Week 9}
7
\subsection{Betweenness Centrality}
8
    \href{http://www.boost.org/doc/libs/1_32_0/libs/graph/doc/betweenness_centrality.html}{Official doc}
9

    
10
    \textbf{How to create Read/Write Property Map}
11

    
12
        The type CentralityMap must be a model of Read/Write Property Map,
13
        with the graph's vertex descriptor type as its key type.
14
        The value type of this property map should be a floating-point or rational type.
15

    
16
    \textbf{listS vs vectorS}
17

    
18
        I use \lstinline{listS}, how can I refer to a single vertex.
19

    
20
    \textbf{iterator_property_map}
21

    
22
        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.
23

    
24
        \href{http://ci.boost.org/svn-trac/browser/boost%20SVN/sandbox/graph-v2/boost/property_map/iterator_property_map.hpp?rev=39140}{Source code}
25

    
26
        \begin{lstlisting}
27
// The iterator property map povides get() and put() functions for random
28
// access containers such that their random access iterators act as the
29
// key type for access.
30

    
31
// Iterator property maps rely on a index map (which is also a property map)
32
// that provides, via its get() function, an offset from the iterator supplied
33
// during construction of this property map. The index map generally gives
34
// a value who's type is convertible to the iterator's difference_type.
35

    
36
iterator_property_map<
37
    RandomAccessIterator,
38
    IndexMap,
39
    Type,
40
    Reference
41
>
42
        \end{lstlisting}
43

    
44
    \textbf{associative_property_map}
45

    
46
        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.
47

    
48
        \href{http://ci.boost.org/svn-trac/browser/boost%20SVN/sandbox/graph-v2/boost/property_map/associative_property_map.hpp}{Source code}
49

    
50
        \begin{lstlisting}
51
associative_property_map<Container>
52
        \end{lstlisting}
53

    
54
    \lstinline{num_vertices}
55
        n = num_vertices(A) returns the number of vertices in graph A.
56

    
57
    \textbf{Property Map for Graph using listS}
58

    
59
        \href{http://stackoverflow.com/questions/15432104/how-to-create-a-propertymap-for-a-boost-graph-using-lists-as-vertex-container}{Answers on Stack Overflow}
60

    
61
        http://stackoverflow.com/questions/7156880/dijkstra-shortest-path-with-vertexlist-lists-in-boost-graph
62

    
63
        http://stackoverflow.com/questions/30263594/adding-a-vertex-index-to-lists-graph-on-the-fly-for-betweenness-centrality
64

    
65

    
66
    \begin{lstlisting}
67
// (2) fill constructor
68
// Constructs a container with n elements. Each element is a copy of val.
69
std::vector< double > v_centrality_vec(boost::num_vertices(g), 0.0);
70
    \end{lstlisting}
71

    
72

    
73
    \subsubsection{Calculating Centrality - Code Explanation}
74

    
75
        \begin{lstlisting}
76
    // http://stackoverflow.com/questions/15432104/how-to-create-a-propertymap-for-a-boost-graph-using-lists-as-vertex-container
77
    typedef std::map<Vertex, size_t> StdVertexIndexMap;
78
    StdVertexIndexMap idxMap;
79

    
80
    typedef boost::associative_property_map<StdVertexIndexMap> VertexIndexMap;
81
    VertexIndexMap v_index(idxMap);
82
        \end{lstlisting}
83

    
84
        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()}
85

    
86
        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.
87

    
88
        \begin{lstlisting}
89
typedef std::vector<double> CentralityVec;
90
CentralityVec v_centrality_vec(boost::num_vertices(g), 0);
91
        \end{lstlisting}
92

    
93
        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.
94

    
95
        \begin{lstlisting}
96
# iterator_property_map<
97
    RandomAccessIterator,
98
    IndexMap,
99
    Type,
100
    Reference
101
>
102

    
103
typedef boost::iterator_property_map< CentralityVec::iterator, VertexIndexMap, double> CentralityMap;
104
CentralityMap v_centrality_map(v_centrality_vec.begin(), v_index);
105
        \end{lstlisting}
106

    
107
        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.
108

    
109
        \begin{lstlisting}
110
template<typename CentralityMap, typename Key, typename T>
111
inline void
112
update_centrality(CentralityMap centrality_map, Key k, const T& x)
113
{ put(centrality_map, k, get(centrality_map, k) + x); }
114

    
115
# Usage example
116
std::vector<centrality_type> dependency(V);
117
update_centrality(centrality, w, get(dependency, w));
118
        \end{lstlisting}
119

    
120
        Piece of code used by \lstinline{brandes_betweenness_centrality()} to change value of centrality.
121

    
122
        \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.
123

    
124
        \subsubsection{AHAHAA SOLUTION!!!!}
125
            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.
126

    
127
            Now everything is working, and it \textbf{COSTS} me 2 days for the problem arising with Copy and Paste.
128

    
129
            \begin{lstlisting}
130
// Wrong version
131
brandes_betweenness_centrality( g, boost::centrality_map(v_centrality_map)
132

    
133
// Right version
134
relative_betweenness_centrality( g, v_centrality_map);
135
            \end{lstlisting}