Statistics
| Branch: | Revision:

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