Statistics
| Branch: | Revision:

root / latex / note_w14.tex @ 4ca27bae

History | View | Annotate | Download (4.67 KB)

1 46d9d2ec Quynh PX Nguyen
2
%!TEX root = note.tex
3
4
%%%%%%%%%%%%%%%%%%
5
% WEEK 14
6
%%%%%%%%%%%%%%%%%%
7
\section{Week 14}
8
    \subsection{C++ Heuristic BC - CHBC}
9
    \subsection{Pattern}
10
11
    Out put graph
12
\begin{lstlisting}
13
Graph g;
14
...
15
16
// 1st way
17
outops::operator<<(cout, g);
18
19
// 2nd way
20
using namespace outops;
21
cout << g;
22
\end{lstlisting}
23
24
25
\href{http://stackoverflow.com/questions/8175933/to-compare-two-boost-graph-having-same-vertices}{Using boost::spirit::karma to format the output}
26
27
\href{http://stackoverflow.com/questions/17595949/boostgraph-add-vertex-compilation-error}{Use graph_manager.h to manage the graph}
28
29
    \subsection{Bug: in copy constructor of GraphManger for v_index_std_map}
30
31
        I don't know why the size of v_index_std_map got double?!
32
33
        Read for explaination: \href{http://stackoverflow.com/questions/1639544/why-does-stdmap-operator-create-an-object-if-the-key-doesnt-exist}{stdmap create an object if the key doesn't exist}
34
35
        \lstinline{boost::get()}: when the key doesn't exist, then it automatically create a default value for that key.
36
37
        \begin{lstlisting}
38
    Vertex Index Std Map:
39
[
40
  0
41
  0
42
  0
43
  0
44
  0
45
  1
46
  0
47
  2
48
  3
49
  4
50
  5
51
  6
52
  7
53
  0
54
  10
55
  8
56
  9
57
  0
58
  0
59
  0
60
  0
61
  0
62
]
63
        \end{lstlisting}
64
65
    \subsection{SubComponent}
66
        How to store \lstinline{art_points_id} for each SubComponent?
67
68
    \subsection{Cannot overload cout operator<< for std::map}
69
70
        \begin{lstlisting}
71
// Code
72
    template <typename T1, typename T2>
73
    std::ostream& operator<<(std::ostream& os, const std::map<T1, T2>& m)
74
    {
75
        cout << "utility << map\n";
76
77
        // using namespace boost::spirit::karma;
78
        // os << format("(" << (auto_ % "\n  ") << ")", m);
79
        // os << endl;
80
81
        // return os;
82
    }
83
84
// Error
85
sub_component.o: In function `operator<<(std::ostream&, SubComponent const&)':
86
sub_component.cpp:(.text+0x715): undefined reference to `outops::operator<<(std::ostream&, std::map<std::string, int, std::less<std::string>, std::allocator<std::pair<std::string const, int> > >)'
87
        \end{lstlisting}
88
89
90
    \subsection{Boost Test}
91
92
        https://github.com/jsankey/boost.test-examples
93
        http://www.ibm.com/developerworks/aix/library/au-ctools1_boost/
94
95
    \subsection{const KEYWORD}
96
        http://stackoverflow.com/questions/15604127/do-a-getter-for-an-object
97
98
        http://stackoverflow.com/questions/6299967/what-are-the-use-cases-for-having-a-function-return-by-const-value-for-non-built
99
100
    \subsection{boost/betweenness_centrality.hpp}
101
        The structure
102
103
        \begin{lstlisting}
104
namespace detail { namespace graph {
105
    struct brandes_dijkstra_visitor : public bfs_visitor<> {};
106
    struct brandes_dijkstra_shortest_paths {};
107
    struct brandes_unweighted_shortest_paths {};
108
109
    void init_centrality_map(std::pair<Iter, Iter>, dummy_property_map);
110
    void init_centrality_map(std::pair<Iter, Iter> keys, Centrality centrality_map);
111
112
    void update_centrality(dummy_property_map, const Key&, const T&);
113
    void update_centrality(CentralityMap centrality_map, Key k, const T& x);
114
    void divide_centrality_by_two(std::pair<Iter, Iter>, dummy_property_map);
115
    void divide_centrality_by_two(std::pair<Iter, Iter> keys,
116
                           CentralityMap centrality_map);
117
118
    void brandes_betweenness_centrality_impl(const Graph& g,
119
                                      CentralityMap centrality,     // C_B
120
                                      EdgeCentralityMap edge_centrality_map,
121
                                      IncomingMap incoming, // P
122
                                      DistanceMap distance,         // d
123
                                      DependencyMap dependency,     // delta
124
                                      PathCountMap path_count,      // sigma
125
                                      VertexIndexMap vertex_index,
126
                                      ShortestPaths shortest_paths);
127
} } // end namespace detail::graph
128
129
// For unweighted graph
130
void brandes_betweenness_centrality(...) {
131
    detail::graph::brandes_unweighted_shortest_paths shortest_paths;
132
    detail::graph::brandes_betweenness_centrality_impl(...);
133
};
134
135
// For weighted graph
136
void brandes_betweenness_centrality(...) {
137
    detail::graph::brandes_dijkstra_shortest_paths<WeightMap>
138
    shortest_paths(weight_map);
139
    detail::graph::brandes_betweenness_centrality_impl(...);
140
}
141
142
namespace detail { namespace graph {
143
    void brandes_betweenness_centrality_dispatch2(...);
144
    void brandes_betweenness_centrality_dispatch2(...);
145
146
    struct brandes_betweenness_centrality_dispatch1 {};
147
    struct brandes_betweenness_centrality_dispatch1<param_not_found> {};
148
    struct is_bgl_named_params {};
149
    struct is_bgl_named_params {};
150
151
} } // end namespace detail::graph
152
153
154
        \end{lstlisting}