Statistics
| Branch: | Revision:

root / latex / note_w08.tex @ d1ed66aa

History | View | Annotate | Download (10.1 KB)

1
%!TEX root = note.tex
2

    
3
%%%%%%%%%%%%%%%%%%
4
% WEEK 8
5
%%%%%%%%%%%%%%%%%%
6
\section{Week 8}
7
\subsection{Read the file}
8
    \href{http://stackoverflow.com/questions/195323/what-is-the-most-elegant-way-to-read-a-text-file-with-c}{Few
9
    ways to read from a text file}
10

    
11
    \begin{lstlisting}
12
template<class InputIterator> string (InputIterator begin, InputIterator end);
13
std::vector<char> v;
14
std::string str(v.begin(),v.end());
15
    \end{lstlisting}
16

    
17
    \textbf{Split single line}
18

    
19
    \textbf{Tuple of exactly 3 elements and STL}
20
        Use \lstinline{array<string, 3>} instead
21

    
22

    
23
\subsection{Create graph for Simple Input}
24
    \subsubsection{Graph with weight}
25

    
26
    \subsubsection{What is it with the name of the vertex?}
27

    
28
        Should I create a set of vertices, then creating a whole set of vertices first, and then adding the edges.
29

    
30
        How to use PropertyMap?
31

    
32
        http://stackoverflow.com/questions/28780137/create-graphs-from-a-file-using-boost-library
33

    
34
        \begin{lstlisting}[caption="Graph with Customized Property", label="property-customized"]
35
//vertex
36
struct VertexProperties
37
{
38
    int id;
39
    int label;
40

    
41
    VertexProperties(){}
42
    VertexProperties(unsigned i, unsigned l) : id(i), label(l) {}
43
};
44

    
45
//edge
46
struct EdgeProperties
47
{
48
    unsigned id;
49
    unsigned label;
50
    EdgeProperties(){}
51
    EdgeProperties(unsigned i, unsigned l) : id(i), label(l) {}
52
};
53

    
54
//Graph
55
struct GraphProperties
56
{
57
    unsigned id;
58
    unsigned label;
59
    GraphProperties()  {}
60
    GraphProperties(unsigned i, unsigned l) : id(i), label(l) {}
61
};
62

    
63
//adjacency list
64
typedef boost::adjacency_list<
65
    boost::vecS, boost::vecS, boost::directedS,
66
    VertexProperties,
67
    EdgeProperties,
68
    GraphProperties
69
> Graph;
70

    
71
Graph g(GraphProperties(gid,gid));
72

    
73
boost::add_vertex(VertexProperties(vId, vLabel), g);
74
        \end{lstlisting}
75

    
76
        \begin{lstlisting}[caption="Graph with default property (== no\_property)", label="no-property"]
77
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS> Graph;
78
Graph g(3); // Create a graph with 3 vertices.
79

    
80

    
81
        \end{lstlisting}
82

    
83
        \begin{lstlisting}
84
// from http://programmingexamples.net/wiki/CPP/Boost/BGL/EdgeProperties
85
typedef boost::property<boost::edge_weight_t, double> EdgeWeightProperty;
86
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property, EdgeWeightProperty> Graph;
87

    
88
Graph g;
89
EdgeWeightProperty e1 = 5;
90
add_edge(0, 1, e1, g);
91
        \end{lstlisting}
92

    
93
        \subsubsection{Multiple properties for Edge/Vertex}
94
            According to \href{http://stackoverflow.com/questions/11277820/bgl-adding-an-edge-with-multiple-properties}{an answer in StackOverflow}, it's better to use \lstinline{Bundled Properties} instead of \lstinline{property chains} in \lstinline{boost}
95

    
96
            Read more in \href{http://www.boost.org/doc/libs/1_41_0/libs/graph/doc/bundles.html}{official doc}
97

    
98
        \subsubsection{Performance when creating graph}
99
            I think it doesn't matter much, but my mind is occupied by that small detail thing. So I'll write it down:
100

    
101
            \begin{itemize}
102
                \item Choosing \lstinline{listS} or \lstinline{vecS} for the VertexSet ==> I think \lstinline{listS} makes more sense. Since in the text file, we do not have any index to refer to. So the \lstinline{RandomAccessIterator} offered by \lstinline{vector} doesn't really contribute to anything here.
103
                \item I was thinking about using \lstinline{boost::vecS} for \lstinline{VertexList} template argument. However, \lstinline{vecS} doesn't model the \emph{Sequence Container}, so it's out of the question.
104
            \end{itemize}
105

    
106
        \subsubsection{Iterating over edges/vertices}
107

    
108
            http://stackoverflow.com/questions/15812663/iterating-over-edges-of-a-graph-using-range-based-for
109

    
110
        \subsubsection{Get vertex descriptor from the vertex iterator}
111

    
112
            Is \href{http://stackoverflow.com/questions/2244580/find-boost-bgl-vertex-by-a-key}{labelled graph} a solution?
113

    
114
            "I would prefer the way of having an additional map which maps the name of the data to the corresponding vertex. Further, you can encapsulate your algorithm in a class or a function, so that when adding a new vertex the map is filled automatically."
115

    
116
            \begin{lstlisting}
117
  typedef float Weight;
118
  typedef boost::property<boost::edge_weight_t, Weight> WeightProperty;
119
  typedef boost::property<boost::vertex_name_t, std::string> NameProperty;
120

    
121
  typedef boost::adjacency_list < boost::listS, boost::vecS, boost::directedS,
122
    NameProperty, WeightProperty > Graph;
123

    
124
  typedef boost::graph_traits < Graph >::vertex_descriptor Vertex;
125

    
126
  typedef boost::property_map < Graph, boost::vertex_index_t >::type IndexMap;
127
  typedef boost::property_map < Graph, boost::vertex_name_t >::type NameMap;
128

    
129

    
130
template <typename AddressMap>
131
void foo(AddressMap address)
132
{
133
typedef typename boost::property traits<AddressMap>::value type value type;
134
typedef typename boost::property traits<AddressMap>::key type key type;
135
value type old address, new address;
136
key type fred = "Fred";
137
old address = get(address, fred);
138
new address = "384 Fitzpatrick Street"
139
put(address, fred, new address);
140
key type joe = "Joe";
141
value type& joes address = address[joe];
142
joes address = "325 Cushing Avenue";
143
}
144

    
145
property<vertex name t, std::string>
146

    
147

    
148
typedef property map<Graph, vertex_name_t>::type actor name map t;
149
actor name map t actor name = get(vertex name, g);
150
typedef property map<Graph, edge name t>::type movie name map t;
151
movie name map t connecting movie = get(edge name, g);
152

    
153

    
154
typedef graph traits<Graph>::vertex descriptor Vertex;
155
typedef std::map<std::string, Vertex> NameVertexMap;
156
NameVertexMap actors;
157
            \end{lstlisting}
158

    
159

    
160
To ensure that each vertex is only added once to the graph, a map from actor
161
names to their vertices is used. As vertices are added to the graph, subsequent appearances of
162
the same vertex (as part of a different edge) can be linked with the correct vertex already in
163
the graph. This mapping is readily accomplished using std::map
164

    
165
        \subsubsection{Get type of Property Map}
166

    
167
            \textbf{Get type of default property map}
168

    
169
                \begin{lstlisting}
170
typedef adjacency list<vecS, vecS, undirectedS, property<vertex name t, std::string>,
171
property<edge name t, std::string> > Graph;
172
Graph g;
173
typedef property_map<Graph, vertex_name_t>::type actor_name_map_t;
174
actor_name_map_t actor name = get(vertex name, g);
175
                \end{lstlisting}
176

    
177

    
178
            \textbf{Get type of bundled properties}
179
            There is currently no support for creating property maps from the bundled properties of a graph.
180

    
181
            To get the type of the vertex or edge bundle for a given graph type Graph, you can use the trait classes vertex_bundle_type and edge_bundle_type. The type vertex_bundle_type<Graph>::type will be the type bundled with vertices (or no_vertex_bundle if the graph supports bundles but no vertex bundle exists). Likewise, edge_bundle_type<Graph>::type will be the type bundled with edges (or no_edge_bundle if no edge bundle exists).
182

    
183
            Then we can the type for one object in \lstinline{struct}
184
                \begin{lstlisting}
185
#include <boost/typeof/typeof.hpp>
186

    
187
struct Router {
188
    string id;
189
    string name;
190
    Router(){};
191
    Router(string id, string name) : id(id), name(name) {}
192
};
193

    
194
struct Link {
195
    double cost;
196
    Link(){};
197
    Link(double cost) : cost(cost) {};
198
};
199

    
200
typedef boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS,
201
        Router, Link> Graph;
202
Graph g;
203
typedef vertex_bundle_type<Graph>::type vertex_bundle_t;
204
typedef BOOST_TYPEOF(vertex_bundle_t.name) router_id_t;
205
router_id_t router_id = get(&vertex_bundle_t::id, g);
206
                \end{lstlisting}
207

    
208
        \subsubsection{How to update the value for bundled properties}
209
            \begin{lstlisting}
210
// Assume that `id` is in the bundled property of a vertex.
211
Vertex v; // vertex descriptor
212
g[v].id = "123"
213
            \end{lstlisting}
214

    
215
        \subsubsection{Overload ostream for a vertex with bundled properties}
216
            NOT WORKING YET
217

    
218
    \subsection{Create graph for OLSR Json Input}
219
        \subsubsection{Read Json with Boost}
220
            http://stackoverflow.com/questions/17124652/how-can-i-parse-json-arrays-with-c-boost
221

    
222
    \subsection{Applying the betweeness centrality}
223
        The graph object on which the algorithm will be applied. The type Graph must be a model of Vertex List Graph and Incidence Graph. When an edge centrality map is supplied, it must also model Edge List Graph.
224

    
225
        \href{http://programmingexamples.net/wiki/CPP/Boost/BGL/BetweennessCentralityClustering}{Example} on how to use Brandes Betweenness Centrality.
226

    
227
        \textbf{Is the \emph{Adjacency List} the same as \emph{Vertex List Graph}}
228

    
229
        \textbf{What is the differences between \emph{named parameter versions} and \emph{non-named parameter versions}}
230
            Answer can be found \href{http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/bgl_named_params.html}{here}
231

    
232
            A better solution is provided by bgl_named_params. This class allows users to provide parameters is any order, and matches arguments to parameters based on parameter names.
233

    
234
            Each of the named parameters is separated by a period, not a comma.
235

    
236
            \begin{lstlisting}
237
//Both of the callings below are the same
238

    
239
bool r = boost::bellman_ford_shortest_paths(g, int(N),
240
 boost::weight_map(weight).
241
 distance_map(&distance[0]).
242
 predecessor_map(&parent[0]));
243

    
244
bool r = boost::bellman_ford_shortest_paths(g, int(N),
245
 boost::predecessor_map(&parent[0]).
246
 distance_map(&distance[0]).
247
 weight_map(weight));
248
            \end{lstlisting}
249

    
250

    
251

    
252

    
253
    \subsection{Property Map}
254
        http://www.boost.org/doc/libs/1_52_0/libs/property_map/doc/ReadWritePropertyMap.html
255

    
256
        http://www.boost.org/doc/libs/1_52_0/libs/property_map/doc/property_map.html
257

    
258

    
259

    
260
    \subsection{Faster way to create Graph}
261
        \textbf{Vector as Graph}
262
            \href{http://ecee.colorado.edu/~siek/boostcon2010bgl.pdf}{Check out page 34}
263

    
264
            https://github.com/boostorg/graph/blob/master/example/vector-as-graph.cpp
265

    
266
            But I think that this way is not efficient.
267

    
268
    \subsection{To Do}
269
        http://www.ist.tugraz.at/_attach/Publish/Akswt04/BOOST_Werner_Trobin.pdf
270

    
271

    
272

    
273