Revision b56a7ca2

View differences:

latex/note.tex
65 65
  \catcode`_=12
66 66
}
67 67

  
68
\usepackage{booktabs} % To thicken table lines
69

  
68 70
\begin{document}
69 71

  
70 72
\title{Thesis - Note Taking}
......
86 88
    \include{note_w07}
87 89
    \include{note_w08}
88 90
    \include{note_w09}
91
    \include{note_w10}
92
    \include{note_w11}
93
    \include{note_w12}
89 94
    \include{tips}
90 95
    \include{important_commands}
91 96

  
latex/note_w01.tex
15 15

  
16 16
            Line 116
17 17
            \begin{itemize}
18
            \item S
19
            \item P
20
            \item sigma
18
                \item S: all nodes belonging to some shortest path from \lstinline{s}
19
                \item P: predecessors. \lstinline{P[w]} is the list of predecessors of vertex w, when starting from source \lstinline{s}
20
                \item sigma: the number of shortest paths. \lstinline{sigma[w]} is the number of shortest paths from \lstinline{s} to \lstinline{w}
21 21
            \end{itemize}
22 22

  
23 23
            $c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\sigma(s, t)}$
24 24

  
25
            \textbf{How accumulate_basic works?}
26
            \begin{lstlisting}
27
# accumulate_basic()
28
delta = dict.fromkeys(S, 0)
29
while S:
30
    w = S.pop()
31
    coeff = (1.0 + delta[w]) / sigma[w]
32
    for v in P[w]:
33
        delta[v] += sigma[v] * coeff
34
            \end{lstlisting}
35

  
36
            \begin{table}[h]
37
                \label{paper_networkx_variable_mapping}
38
                \caption{Mapping variables between the paper and the networkx code}
39
                \begin{tabular}{c|c|p{11cm}}
40
                    \toprule
41
                    Paper & Networkx & Meaning \\
42
                    \hline
43
                    $s$ & s & the \texttt{source vertex} \\
44

  
45
                    $t$ & ... & the \texttt{target vertex}. \textbf{???} Maybe it doesn't have the equivalent variable in the code. Since we only need to calculate the dependency of vertex $s$ on a single vertex $v$, rather than the \texttt{pair-dependency} of a pair $s, t$ on an intermediary $v$ \\
46

  
47
                    ... & {\lstinline!S!} & a list of vertex $w$ that satisfies $w$ is any vertex with $v \in P_s(w)$ \\
48

  
49
                    ??? & w & a vertex from a list $S$ \\
50

  
51
                    $P_s(w)$ &  & the predecessor of a \texttt{middle vertex} on the shortest path from \texttt{source vertex} \\
52

  
53
                    $\delta_{s.}(v)$ & {\lstinline!delta[v]!} & the \texttt{dependency} of a source vertex $s$ on a single vertex $v$ \\
54

  
55
                    $\delta_{s.}(w)$ & {\lstinline!delta[w]!} & the \texttt{dependency} of a source vertex $s$ on a single vertex \\
56

  
57
                    $\sigma_{sv}$ & {\lstinline!sigma[v]!} & the number of shortest paths from $s$ to $v$ \\
58

  
59
                    $\sigma_{sw}$ & {\lstinline!sigma[w]!} & the number of shortest paths from $s$ to $w$ \\
60

  
61
                    .. & {\lstinline!betweenness[w]!} & \textbf{???} It's not really match with $\delta_{s.}(v)$ \\
62

  
63
                \end{tabular}
64
            \end{table}
65

  
66
        \subsubsection{Output of Brandes from networkx}
67
            \begin{lstlisting}
68
vertices = [u'5', u'u', u'6']
69

  
70
xxx _single_source_shortest_path
71
5
72
[u'5', u'u', u'6']
73
{u'u': [u'5'], u'5': [], u'6': [u'5']}
74
{u'u': 1.0, u'5': 1.0, u'6': 1.0}
75
w = 6
76
delta = {u'u': 0, u'5': 1.0, u'6': 0}
77
betweenness = {u'u': 0.0, u'5': 0.0, u'6': 0.0}
78
w = u
79
delta = {u'u': 0, u'5': 2.0, u'6': 0}
80
betweenness = {u'u': 0.0, u'5': 0.0, u'6': 0.0}
81
w = 5
82
delta = {u'u': 0, u'5': 2.0, u'6': 0}
83

  
84
xxx _single_source_shortest_path
85
u
86
[u'u', u'5', u'6']
87
{u'u': [], u'5': [u'u'], u'6': [u'u']}
88
{u'u': 1.0, u'5': 1.0, u'6': 1.0}
89
w = 6
90
delta = {u'5': 0, u'u': 1.0, u'6': 0}
91
betweenness = {u'u': 0.0, u'5': 0.0, u'6': 0.0}
92
w = 5
93
delta = {u'5': 0, u'u': 2.0, u'6': 0}
94
betweenness = {u'u': 0.0, u'5': 0.0, u'6': 0.0}
95
w = u
96
delta = {u'5': 0, u'u': 2.0, u'6': 0}
97

  
98
xxx _single_source_shortest_path
99
6
100
[u'6', u'u', u'5']
101
{u'u': [u'6'], u'5': [u'6'], u'6': []}
102
{u'u': 1.0, u'5': 1.0, u'6': 1.0}
103
w = 5
104
delta = {u'5': 0, u'u': 0, u'6': 1.0}
105
betweenness = {u'u': 0.0, u'5': 0.0, u'6': 0.0}
106
w = u
107
delta = {u'5': 0, u'u': 0, u'6': 2.0}
108
betweenness = {u'u': 0.0, u'5': 0.0, u'6': 0.0}
109
w = 6
110
delta = {u'5': 0, u'u': 0, u'6': 2.0}
111
nodes =
112
vertices = [u'1', u'3', u'2', u'u', u'4', u'v']
113

  
114

  
115
vertices = [u'1', u'3', u'2', u'u', u'4', u'v']
116

  
117
xxx _single_source_shortest_path
118
1
119
[u'1', u'3', u'2', u'u', u'4', u'v']
120
{u'1': [], u'3': [u'1'], u'2': [u'1'], u'u': [u'1'], u'4': [u'3', u'2'], u'v': [u'3', u'2']}
121
{u'1': 1.0, u'3': 1.0, u'2': 1.0, u'u': 1.0, u'4': 2.0, u'v': 2.0}
122
w = v
123
delta = {u'1': 0, u'3': 0.5, u'2': 0.5, u'u': 0, u'4': 0, u'v': 0}
124
betweenness = {u'1': 0.0, u'3': 0.0, u'2': 0.0, u'u': 0.0, u'4': 0.0, u'v': 0.0}
125
w = 4
126
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}
127
betweenness = {u'1': 0.0, u'3': 0.0, u'2': 0.0, u'u': 0.0, u'4': 0.0, u'v': 0.0}
128
w = u
129
delta = {u'1': 1.0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}
130
betweenness = {u'1': 0.0, u'3': 0.0, u'2': 0.0, u'u': 0.0, u'4': 0.0, u'v': 0.0}
131
w = 2
132
delta = {u'1': 3.0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}
133
betweenness = {u'1': 0.0, u'3': 0.0, u'2': 1.0, u'u': 0.0, u'4': 0.0, u'v': 0.0}
134
w = 3
135
delta = {u'1': 5.0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}
136
betweenness = {u'1': 0.0, u'3': 1.0, u'2': 1.0, u'u': 0.0, u'4': 0.0, u'v': 0.0}
137
w = 1
138
delta = {u'1': 5.0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}
139

  
140
xxx _single_source_shortest_path
141
3
142
[u'3', u'1', u'u', u'4', u'v', u'2']
143
{u'1': [u'3'], u'3': [], u'2': [u'1', u'u', u'4', u'v'], u'u': [u'3'], u'4': [u'3'], u'v': [u'3']}
144
{u'1': 1.0, u'3': 1.0, u'2': 4.0, u'u': 1.0, u'4': 1.0, u'v': 1.0}
145
w = 2
146
delta = {u'1': 0.25, u'3': 0, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
147
betweenness = {u'1': 0.0, u'3': 1.0, u'2': 1.0, u'u': 0.0, u'4': 0.0, u'v': 0.0}
148
w = v
149
delta = {u'1': 0.25, u'3': 1.25, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
150
betweenness = {u'1': 0.0, u'3': 1.0, u'2': 1.0, u'u': 0.0, u'4': 0.0, u'v': 0.25}
151
w = 4
152
delta = {u'1': 0.25, u'3': 2.5, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
153
betweenness = {u'1': 0.0, u'3': 1.0, u'2': 1.0, u'u': 0.0, u'4': 0.25, u'v': 0.25}
154
w = u
155
delta = {u'1': 0.25, u'3': 3.75, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
156
betweenness = {u'1': 0.0, u'3': 1.0, u'2': 1.0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
157
w = 1
158
delta = {u'1': 0.25, u'3': 5.0, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
159
betweenness = {u'1': 0.25, u'3': 1.0, u'2': 1.0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
160
w = 3
161
delta = {u'1': 0.25, u'3': 5.0, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
162

  
163
xxx _single_source_shortest_path
164
2
165
[u'2', u'1', u'u', u'4', u'v', u'3']
166
{u'1': [u'2'], u'3': [u'1', u'u', u'4', u'v'], u'2': [], u'u': [u'2'], u'4': [u'2'], u'v': [u'2']}
167
{u'1': 1.0, u'3': 4.0, u'2': 1.0, u'u': 1.0, u'4': 1.0, u'v': 1.0}
168
w = 3
169
delta = {u'1': 0.25, u'3': 0, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
170
betweenness = {u'1': 0.25, u'3': 1.0, u'2': 1.0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
171
w = v
172
delta = {u'1': 0.25, u'3': 0, u'2': 1.25, u'u': 0.25, u'4': 0.25, u'v': 0.25}
173
betweenness = {u'1': 0.25, u'3': 1.0, u'2': 1.0, u'u': 0.25, u'4': 0.25, u'v': 0.5}
174
w = 4
175
delta = {u'1': 0.25, u'3': 0, u'2': 2.5, u'u': 0.25, u'4': 0.25, u'v': 0.25}
176
betweenness = {u'1': 0.25, u'3': 1.0, u'2': 1.0, u'u': 0.25, u'4': 0.5, u'v': 0.5}
177
w = u
178
delta = {u'1': 0.25, u'3': 0, u'2': 3.75, u'u': 0.25, u'4': 0.25, u'v': 0.25}
179
betweenness = {u'1': 0.25, u'3': 1.0, u'2': 1.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
180
w = 1
181
delta = {u'1': 0.25, u'3': 0, u'2': 5.0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
182
betweenness = {u'1': 0.5, u'3': 1.0, u'2': 1.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
183
w = 2
184
delta = {u'1': 0.25, u'3': 0, u'2': 5.0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
185

  
186
xxx _single_source_shortest_path
187
u
188
[u'u', u'1', u'3', u'2', u'4', u'v']
189
{u'1': [u'u'], u'3': [u'u'], u'2': [u'u'], u'u': [], u'4': [u'3', u'2'], u'v': [u'3', u'2']}
190
{u'1': 1.0, u'3': 1.0, u'2': 1.0, u'u': 1.0, u'4': 2.0, u'v': 2.0}
191
w = v
192
delta = {u'1': 0, u'3': 0.5, u'2': 0.5, u'u': 0, u'4': 0, u'v': 0}
193
betweenness = {u'1': 0.5, u'3': 1.0, u'2': 1.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
194
w = 4
195
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}
196
betweenness = {u'1': 0.5, u'3': 1.0, u'2': 1.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
197
w = 2
198
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 2.0, u'4': 0, u'v': 0}
199
betweenness = {u'1': 0.5, u'3': 1.0, u'2': 2.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
200
w = 3
201
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 4.0, u'4': 0, u'v': 0}
202
betweenness = {u'1': 0.5, u'3': 2.0, u'2': 2.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
203
w = 1
204
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 5.0, u'4': 0, u'v': 0}
205
betweenness = {u'1': 0.5, u'3': 2.0, u'2': 2.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
206
w = u
207
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 5.0, u'4': 0, u'v': 0}
208

  
209
xxx _single_source_shortest_path
210
4
211
[u'4', u'3', u'2', u'v', u'1', u'u']
212
{u'1': [u'3', u'2'], u'3': [u'4'], u'2': [u'4'], u'u': [u'3', u'2'], u'4': [], u'v': [u'4']}
213
{u'1': 2.0, u'3': 1.0, u'2': 1.0, u'u': 2.0, u'4': 1.0, u'v': 1.0}
214
w = u
215
delta = {u'1': 0, u'3': 0.5, u'2': 0.5, u'u': 0, u'4': 0, u'v': 0}
216
betweenness = {u'1': 0.5, u'3': 2.0, u'2': 2.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
217
w = 1
218
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}
219
betweenness = {u'1': 0.5, u'3': 2.0, u'2': 2.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
220
w = v
221
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 1.0, u'v': 0}
222
betweenness = {u'1': 0.5, u'3': 2.0, u'2': 2.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
223
w = 2
224
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 3.0, u'v': 0}
225
betweenness = {u'1': 0.5, u'3': 2.0, u'2': 3.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
226
w = 3
227
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 5.0, u'v': 0}
228
betweenness = {u'1': 0.5, u'3': 3.0, u'2': 3.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
229
w = 4
230
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 5.0, u'v': 0}
231

  
232
xxx _single_source_shortest_path
233
v
234
[u'v', u'3', u'2', u'4', u'1', u'u']
235
{u'1': [u'3', u'2'], u'3': [u'v'], u'2': [u'v'], u'u': [u'3', u'2'], u'4': [u'v'], u'v': []}
236
{u'1': 2.0, u'3': 1.0, u'2': 1.0, u'u': 2.0, u'4': 1.0, u'v': 1.0}
237
w = u
238
delta = {u'1': 0, u'3': 0.5, u'2': 0.5, u'u': 0, u'4': 0, u'v': 0}
239
betweenness = {u'1': 0.5, u'3': 3.0, u'2': 3.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
240
w = 1
241
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}
242
betweenness = {u'1': 0.5, u'3': 3.0, u'2': 3.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
243
w = 4
244
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 1.0}
245
betweenness = {u'1': 0.5, u'3': 3.0, u'2': 3.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
246
w = 2
247
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 3.0}
248
betweenness = {u'1': 0.5, u'3': 3.0, u'2': 4.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
249
w = 3
250
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 5.0}
251
betweenness = {u'1': 0.5, u'3': 4.0, u'2': 4.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
252
w = v
253
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 5.0}
254

  
255
            \end{lstlisting}
256

  
257

  
258

  
259

  
latex/note_w11.tex
5 5
%%%%%%%%%%%%%%%%%%
6 6
\section{Week 11}
7 7
\subsection{ipkg = Itsy Package Management System}
8
    ipkg, or the Itsy Package Management System, is a lightweight package management system designed for embedded devices that resembles Debian's dpkg.
9

  
10
    opkg is the fork of ipkg
11

  
12
    http://lists.openmoko.org/pipermail/devel/2008-July/000496.html
13

  
14
\subsection{Shortest Path Problems}
15

  
16
    Single-source Shortest-Paths
17
    \begin{itemize}
18
        \item Dijkstra
19
            \begin{itemize}
20
                \item priority queue: $O(|V|^2)$
21
                \item binary heap: $O(|E| log|V|)$
22
                \item fibonacci heap: $O(|V| log|V| + |E|)$
23
            \end{itemize}
24
        \item Bellman-Ford: $O(|V|\times|E|)$, worst case: $O(|V|^3)$
25
    \end{itemize}
26

  
27
    Algorithms for the All-Pairs Problem
28
    \begin{itemize}
29
        \item Iteration $O(|V|^4)$
30
        \item Iteration with Doubling Up $O(|V|^3 \times log|V|$
31
        \item Floyd-Warshall Algorithm: $O(|V|^3)$
32
    \end{itemize}
33

  
34
\subsection{Matrix}
35
    \textbf{Multiplication} of $n \times n$-matrices
36

  
37
    $A \otimes B = (c_{ij})$ where $c_{ij} = \oplus_{k=1}^{n} a_{ik} \otimes b_{kj}$
38

  
39
    $k$-th \textbf{power} of matrix A:
40

  
41
    $A^k = (d_{ij}$ where $d_{ij} = \oplus_{r = 0}^{k - 1} a_{ir} \otimes a_{rj}, A^0 = I$
42

  
43
    \textbf{XXX} I have the feeling that the definition from the \href{https://www.iam.unibe.ch/~run/talks/2008-06-05-Bern-Jonczy.pdf}{slide} is wrong. Wolfram gave a different definition \href{http://mathworld.wolfram.com/MatrixPower.html}{here}
44

  
45
    The \textbf{closure} of the matrix A: $A^{*} = \oplus_{k >= 0} A^k$
46

  
47
    \subsubsection{Other materials}
48
        Check out slide for ICS 6D in \texttt{reading/w11 - MatrixMultiplication}. It details how the matrix multiplication works
49

  
50
\subsection{Algebraic Path Problem (APP)}
51
    https://www.iam.unibe.ch/~run/talks/2008-06-05-Bern-Jonczy.pdf
52

  
53
    The Algebraic Path Problem consists in performing a special unary operation, called the closure , over a square matrix with entries in a semiring [Fink, 1992]
54

  
55

  
56
    For example, Problem of computing the length of the shortest path (for all pairs): APP over graph \texttt{G} and tropical semiring \texttt{Trop}.
57

  
58
    \textbf{XXX But I don't really understand...}
latex/note_w12.tex
1
%!TEX root = note.tex
2

  
3
%%%%%%%%%%%%%%%%%%
4
% WEEK 12
5
%%%%%%%%%%%%%%%%%%
6
\section{Week 12}
7
\subsection{C++}
8
    \subsubsection{Free standing functions}
9
        \href{http://stackoverflow.com/questions/11780259/class-functionsc-call-function-that-does-not-belong-to-any-class}{Function that does not belong to any class}
10

  
11
    \subsubsection{Where should typedef be}
12
        Should it be in .cpp or .h file?
13

  
14
        \href{http://stackoverflow.com/questions/2356548/header-file-best-practices-for-typedefs}{Header File Best Practice for typedef}
15

  
16
        for starters, i recommend using good design structures for scoping (e.g., namespaces) as well as descriptive, non-abbreviated names for typedefs. FooListPtr is terribly short, imo. nobody wants to guess what an abbreviation means (or be surprised to find Foo is const, shared, etc.), and nobody wants to alter their code simply because of scope collisions
17

  
18
    \subsubsection{What is Forward Definition}
19
        \href{http://stackoverflow.com/questions/15827921/include-in-header-file-vs-forward-declare-and-include-in-cpp}{Forward Declare and Include}
20
        \begin{lstlisting}
21
//a.h
22
class B;
23
class A
24
{
25
private:
26
B* m_p;
27
};
28

  
29
//a.cpp
30
#include b.h
31
        \end{lstlisting}
32

  
33
        And below is the normal wayto declare and include in a header file.
34

  
35
        \begin{lstlisting}
36
// a.h
37
#include <B.h>
38

  
39
class A
40
{
41
private:
42
B * impl_;
43
};
44
        \end{lstlisting}
45

  
46
    \subsubsection{\#include <> vs. \#include ""}
47
        \href{http://www.cplusplus.com/forum/beginner/43444/}{Answer here}
48

  
49
        <> tells the compiler to look in predefined header directories only (generally where the STL is kept).
50
        "" tells to compiler to look in the local directory, and usually the predefined header directories as well
51

  
52

  
53
    \subsubsection{Pass by reference-to-const, and pointer-to-const}
54
        https://isocpp.org/wiki/faq/const-correctness
55

  
56
        \begin{lstlisting}
57
int foo(BigStruct a);         // Pass by value
58
int foo (const BigStruct &a); // Pass by reference-to-const
59
int foo (const BigStruct *a); // Pass by pointer-to-const
60
        \end{lstlisting}
61

  
62
\subsection{Meeting Dec 15, 2015}
63
    \subsubsection{Modification in \lstinline{accummulate_endpoints}}
64
        \begin{lstlisting}
65
// https://github.com/networkx/networkx/blob/master/networkx/algorithms/centrality/betweenness.py
66
def _accumulate_endpoints(betweenness, S, P, sigma, s):
67
    betweenness[s] += len(S) - 1
68
    delta = dict.fromkeys(S, 0)
69
    while S:
70
        w = S.pop()
71
        coeff = (1.0 + delta[w]) / sigma[w]
72
        for v in P[w]:
73
            delta[v] += sigma[v] * coeff
74
        if w != s:
75
            betweenness[w] += delta[w] + 1
76
    return betweenness
77
        \end{lstlisting}
78

  
79
        Modified version:
80
        \begin{lstlisting}
81
def _accumulate_endpoints(betweenness, S, P, sigma, s, traffic_matrix, nodes):
82
    betweenness[s] += len(S) - 1
83
    delta = dict.fromkeys(S, 0)
84
    while S:
85
        w = S.pop()
86
        coeff = (1.0 + delta[w]) / sigma[w]
87
        for v in P[w]:
88
            h = _get_value_from_traffic_matrix(nodes, traffic_matrix, s, v)
89
            delta[v] += sigma[v] * coeff + h
90
        if w != s:
91
            betweenness[w] += delta[w] + 1
92
            print 'betweenness = %s' % betweenness
93
    return betweenness
94

  
95
        \end{lstlisting}
96

  
97
    \subsubsection{Recale}
98
        Rescale only 1 time, after finishing calculating the centrality score for all nodes in the original graph G.
99

  
100
\subsection{Understanding C++ code}
101
    \subsubsection{Why do we need both \lstinline{StdVertexIndexMap} and \lstinline{VertexIndexMap}}
102

  
103
        \begin{lstlisting}
104
typedef map<Vertex, size_t> StdVertexIndexMap;
105
typedef boost::associative_property_map<StdVertexIndexMap> VertexIndexMap;
106
        \end{lstlisting}
107

  
108
        \href{http://www.boost.org/doc/libs/1_38_0/libs/property_map/property_map.html}{Boost Property Map Library - Doc}
109

  
110
        Because \lstinline{VertexIndexMap} must be a model of \texttt{Readable Property Map}. And the \lstinline{associative_property_map} will convert any type that is a model of \texttt{Pair Associative Container} such as \texttt{map} or \href{http://www.sgi.com/tech/stl/UniqueAssociativeContainer.html}{\texttt{Unique Associative Container}}
111

  
112
    \subsubsection{Some conventions}
113
        \lstinline{vertex_t} or \lstinline{Vertex} are the same. It's a matter of convention. For now (Dec 15), I'm choosing \lstinline{Vertex}
114

  
115
        \begin{lstlisting}
116
# vertex_t ==> means the type of vertex
117
typedef adjacency_list < vecS, vecS, undirectedS,
118
    no_property, property < edge_component_t, std::size_t > >graph_t;
119
typedef graph_traits < graph_t >::vertex_descriptor vertex_t;
120

  
121

  
122
# Vertex ==> also means the type of vertex.
123
typedef boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS,
124
        Router, Link> Graph;
125
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
126
        \end{lstlisting}
127

  
128
\subsection{Finding biconnected components}
129
    \href{http://www.boost.org/doc/libs/1_44_0/libs/graph/example/biconnected_components.cpp}{Code example}
130

  
131

  
132
    \subsubsection{ComponentMap}
133
        \href{http://www.cs.fsu.edu/~lacher/boost_1_32_0/libs/graph/doc/using_property_maps.html}{Detailed tutorial on how to use Property Map}
134

  
135
        \textbf{Interior Properties}
136

  
137
        \begin{lstlisting}
138
// property<PropertyTag, T, NextProperty>
139
// This class can be used with the adjacency_list and the adjacency_matrix classes to specify what kind of properties should be attached to the vertices and edges of the graph, and to the graph object itself.
140
property < edge_component_t, std::size_t >
141

  
142
//o btain the property map for the distance and weight properties of some graph type.
143
property_map<Graph, vertex_distance_t>::type d
144
    = get(vertex_distance, g);
145
property_map<Graph, edge_weight_t>::type w
146
    = get(edge_weight, g);
147

  
148
// This one access the interior properties of the object with type graph_t
149
property_map < graph_t, edge_component_t >::type component = get(edge_component, g);
150
        \end{lstlisting}
151

  
152
        \textbf{Exterior Properties}
153

  
154
        1. Use \lstinline{random_access_iterator_property_map}
155

  
156
        2. Use a pointer type
157

  
158
    \subsubsection{edges() for Adjacency List}
159

  
160
        The set of edges for a graph can be accessed with the \lstinline{edges()} function of the \lstinline{EdgeListGraph} interface. Similar to the vertices() function, this returns a pair of iterators, but in this case the iterators are edge iterators. Dereferencing an edge iterator gives an edge object.
161

  
162
        This works perfectly fine for Adjacency List
163

  
164
    \subsubsection{Creating an edge_index_map}
165
        The piece of code below doesn't work
166

  
167
        \begin{lstlisting}
168
for(boost::tie(ei, ei_end) = boost::edges(g); ei != ei_end; ++ei) {
169
    cout << *ei;
170
    boost::put(e_index_map, *ei, i);
171
    ++i;
172
}
173

  
174
// One sample from cout
175
(0x89f320,0x89f2f0)
176
        \end{lstlisting}
177

  
178
        So this is a pair of 2 vertices.
179

  
180
        The \textbf{solution} can be found here: \href{http://liuweipingblog.cn/cpp/an-example-of-boost-betweenness-centrality/}{Example of creating edge_index_map}
181

  
182
        \begin{lstlisting}
183
BGL_FORALL_EDGES(edge, g, Graph) {
184
    e_index_std_map.insert(pair< Edge, size_t >(edge, i));
185
    ++i;
186
}
187
        \end{lstlisting}
188

  
189
        \textbf{getting an edge_descriptor from edge iterator}: If this can be done, then I could use the same code to populate the \lstinline{e_index_map}, instead of populating the \lstinline{e_index_std_map}
190

  
191
        There are 2 ways that we can change value of \lstinline{e_index_std_map}:
192

  
193
        \begin{itemize}
194
            \item through the associative_propert_map \lstinline{e_index_map}
195
            \item change the value directly
196
        \end{itemize}
197

  
198
        The \lstinline{e_index_map} provides the common interface with \lstinline{put(), get()} so that a generic algorithm can retrieve/update the value of the original \lstinline{e_index_std_map}. However, \lstinline{e_index_map} does not store any value, all the value are stored in the original data structure (map, vector...) \lstinline{e_index_std_map}
199

  
200
        \textbf{Why can't we use put(e_index_map, *ei, i)?}: I have no idea how. The cout from both the pieces of code are the same.
201

  
202
    \subsubsection{biconnected_components is not yet working}
203
        I followed the official example
204

  
205
        And I also check out this \href{http://boost.2283326.n4.nabble.com/BGL-graph-library-biconnected-components-td2565983.html}{forum post}, but still I couldn't figure out what is wrong with my implementation.
206

  
207
        From the forum, it use the \texttt{interior properties}.
208

  
209
        \begin{lstlisting}
210
iterator_property_map< std::vector< int >::iterator,
211
property_map<Graph, edge_index_t>::type > mapEdgeComponent(
212
vec_bcc_nums.begin() , get(edge_index,g));
213
        \end{lstlisting}
214

  
215
        And this is my code:
216
        \begin{lstlisting}
217
StdEdgeIndexMap e_index_std_map;
218
EdgeIndexMap e_index_map;
219
    BGL_FORALL_EDGES(edge, g, Graph) {
220
    cout << edge << endl;
221
    e_index_std_map.insert(pair< Edge, size_t >(edge, i));
222
    ++i;
223
}
224
ComponentVec component_vec(boost::num_edges(g), 0);
225
ComponentMap component_map(component_vec.begin(), e_index_map);
226
        \end{lstlisting}
227

  
228
        \textbf{Hahaha, I know why}, the code should be:
229

  
230
        \begin{lstlisting}
231
EdgeIndexMap e_index_map(e_index_std_map);
232
        \end{lstlisting}
233

  
234
        And now, the code should words, with \lstinline{boost::put} as well.
235

  
236
\subsection{Heuristic - Fix bug}
237
    The code below produces correct result for rectangle with 1 or 2 diagonals. However, it's not produce the correct result for the "house" graph.
238

  
239
    \begin{lstlisting}
240
# ENDPOINT - Version 1
241

  
242
def _accumulate_endpoints(betweenness, S, P, sigma, s, traffic_matrix, nodes):
243
    betweenness[s] += len(S) - 1
244
    delta = dict.fromkeys(S, 0)
245
    while S:
246
        w = S.pop()
247
        coeff = delta[w] / sigma[w] # code changed here
248
        for v in P[w]:
249
            print "  v = %s" % v
250
            h = _get_value_from_traffic_matrix(nodes, traffic_matrix, s, v)
251
            delta[v] += sigma[v] * coeff + h # code changed here
252
        if w != s:
253
            betweenness[w] += delta[w] + 1
254
            print 'betweenness = %s' % betweenness
255
    return betweenness
256
    \end{lstlisting}
257

  
258

  
259
    \textbf{Still pretty clueless about it}
260

  
261
    \subsubsection{get_link_weight() vs compute_component_tree_weight()}
262
        This is my interpretation on how the component tree weights are calculated. But it's wrong, as can be show with the input
263
        \begin{itemize}
264
            \item \textbf{v1} the generate_link_weight() function
265
            \item \textbf{v2} the original Compute Component Tree Weights, as writen in Puzis 2012, Algorithm 1.
266
            \item \textbf{v3} modify the original Compute Component Tree Weights in 2 locations:
267
            \begin{itemize}
268
                \item line 9: minus 1 more
269
                \item line 15: size <= 0
270
            \end{itemize}
271

  
272
        \end{itemize}
273

  
274
        \textbf{Summary:}
275

  
276
            I used 3 different ways to calculate BC:
277
                \begin{itemize}
278
                    \item The score from networkx function
279
                    \item The modified version from networkx, where the score is multiplied by h(x,y) - representing the intensity of communication between vertex x, and vertex y
280
                    \item The Heuristic version, where graph G is partioned into biconnected components
281
                \end{itemize}
282

  
283
            I found the for the simple input, the difference between 3 algorithms are homogeneous. While for the more complex input of \textbf{Ninux} graph, the results from 3 algorithms above do not follow any conceivable pattern.
284

  
285

  
286
            \begin{figure}[h]
287
                \label{fig:bc_comparison_simple}
288
                \caption{The input is in /input/simple5.edges}
289
                \includegraphics[scale=0.4]{bc_comparison_simple_5}
290
            \end{figure}
291

  
292
            \begin{figure}[h]
293
                \label{fig:bc_comparison_ninux}
294
                \caption{The input is in /input/simple5.edges}
295
                \includegraphics[scale=0.4]{bc_comparison_ninux}
296
            \end{figure}
297

  
298
        \begin{lstlisting}
299
# input
300
1 2 1
301
2 3 1
302
3 4 1
303
4 5 1
304
4 6 1
305
5 6 1
306

  
307
# correct result should be
308
[{u'4': 2}, {u'3': 3, u'4': 3}, {u'3': 2, u'2': 4}, {u'2': 1}]
309

  
310
# get_component_tree_weight() - v3
311
[{u'4': 2}, {u'3': 3, u'4': 3}, {u'3': 2, u'2': 4}, {u'2': 1}]
312

  
313
# generate_link_weight() - v1 - WRONG RESULT
314
[{u'4': 2}, {u'3': 5, u'4': 3}, {u'3': 0, u'2': 4}, {u'2': 1}]
315
        \end{lstlisting}
316

  
317
    \subsubsection{Maybe the code has bugs in (i) Traffic Matrix or (ii) accumulate() function}
318

  
319
        \begin{lstlisting}
320
# For the accumulate_weight() - with Traffic Matrix
321
*** betweenness = {u'62': 31.0, u'64': 31.0, u'112': 31.0, u'82': 31.0, u'26': 31.0, u'21': 31.0, u'44': 31.0, u'43': 91.0,
322
u'41': 31.0, u'1': 353.0, u'0': 31.0, u'3': 91.0, u'2': 1.0, u'5': 31.0, u'4': 451.0, u'7': 33.0, u'6': 2.0, u'9': 31.0, u'8': 31.0, u'75': 31.0, u'122': 1.0, u'124': 31.0, u'90': 267.0, u'93': 1.0, u'104': 31.0, u'10': 31.0, u'59': 31.0, u'16': 31.0, u'19': 1.0, u'117': 12.0, u'53': 31.0, u'52': 91.0}
323

  
324
# For the accumulate_weight() - basic version - without Traffic Matrix
325
@@@ betweenness = {u'62': 12.0, u'117': 12.0, u'64': 12.0, u'112': 12.0, u'82': 12.0, u'26': 11.0, u'21': 12.0, u'44': 11.0, u'43': 31.0,
326
u'41': 12.0, u'1': 144.0, u'0': 11.0, u'3': 31.0, u'2': 1.0, u'5': 11.0, u'4': 111.0, u'7': 4.0, u'6': 2.0, u'9': 12.0, u'8': 12.0, u'75': 2.0, u'124': 12.0, u'90': 47.0, u'93': 1.0, u'104': 12.0, u'10': 11.0, u'59': 12.0, u'16': 11.0, u'19': 1.0, u'122': 1.0, u'53': 11.0, u'52': 31.0}
327

  
328
        \end{lstlisting}
329

  
330

  
331

  
332
\section{Todo}
333
http://www.gamedev.net/page/resources/_/technical/general-programming/organizing-code-files-in-c-and-c-r1798
334

  
335
The \texttt{biconnected_components} works for \textbf{undirected graph} only. What if we have the directed graph?
336

  
latex/note_w13.tex
1
%!TEX root = note.tex
2

  
3
%%%%%%%%%%%%%%%%%%
4
% WEEK 13
5
%%%%%%%%%%%%%%%%%%
6
\section{Week 13}
7
    \subsection{Heuristic BC - biconnected components}
8
        Check out \textbf{report_dec_20.pdf} for more information.
9

  
10
        \subsubsection{Acronym}
11
            \textbf{NBC} = the BC from the library networkx
12

  
13
            \textbf{WBBC} = accummulate BC with the simplest \emph{Traffic Matrix} (1 for connected vertices, and 0 otherwise)
14

  
15
            \textbf{HBC} = accummulate BC with the Traffic Matrix described in the paper.
16

  
17
        \subsubsection{Result}
18
            There was a bug in Traffic Matrix. It has to do with the sorting.  I should not assume that the list of vertices were sorted in the same way.
19

  
20
            \begin{lstlisting}
21
                sorted(biconnected_components[0])
22

  
23
                sorted(G.nodes())
24
            \end{lstlisting}
25

  
26
            Now the WBBC = HBC. (But I did not minus the BC_iter from the total sum of BC for cutpoint vertices.)
27

  
28
            And we have WBBC ~ NBC.
29

  
30
    \subsection{C++ Heuristic BC - CHBC}
31

  
latex/tips.tex
15 15
        \subsubsection{Escape the underscore \_ effectively}
16 16
            Help from \href{http://tex.stackexchange.com/questions/62705/underscore-in-textmode-vs-mathmode}{here}
17 17
            \begin{lstlisting}
18

  
19

  
18 20
\usepackage[T1]{fontenc}
19 21
\AtBeginDocument{%
20 22
  \begingroup\lccode`~=`_%
......
22 24
  \catcode`_=12
23 25
}            \end{lstlisting}
24 26

  
27
        \subsubsection{Multiline in table}
28
            Solution from \href{http://tex.stackexchange.com/questions/2441/how-to-add-a-forced-line-break-inside-a-table-cell}{here}
29

  
30
            \begin{lstlisting}
31
\begin{tabular}{c|c|p{10cm}}
32
            \end{lstlisting}
33

  
25 34

  
26 35

  
27 36
    \subsection{Shell}

Also available in: Unified diff