## root / latex / note_w12.tex @ b56a7ca2

History | View | Annotate | Download (13.6 KB)

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 |