## 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