Skip to content

Commit 64e8515

Browse files
cirosantillicirosantilli
committed
Start boost properties, C++ improve capacity().
1 parent 2cd72da commit 64e8515

3 files changed

Lines changed: 175 additions & 61 deletions

File tree

‎Makefile_many‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -60,6 +60,7 @@ all: mkdir $(OUTS)
6060
@if [ -e "$(RUN_INPUT)" ] && [ ! -e "$(OUT_DIR)$(RUN_INPUT)" ]; then ln -s ../$(RUN_INPUT) "$(OUT_DIR)$(RUN_INPUT)"; fi
6161
@-$(MAKE) all-post
6262
ifneq ($(strip $(run)),)
63+
@echo
6364
cd $(OUT_DIR) && ./"$(run)"
6465
endif
6566

‎boost/graph.cpp‎

Lines changed: 104 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,12 @@
1+
/**
2+
Good tutorial: http://www.informit.com/articles/article.aspx?p=673259
3+
*/
4+
15
#include <algorithm>
2-
#include <iostream>
36
#include <fstream>
7+
#include <iostream>
8+
#include <set>
9+
#include <vector>
410

511
#include <boost/config.hpp>
612
//-lboost_graph
@@ -27,6 +33,48 @@ int main() {
2733
AdjacenyMatrix ---+
2834
*/
2935
{
36+
/*
37+
#properties
38+
39+
Properties are values associated to edges and vertices.
40+
*/
41+
{
42+
/*
43+
There are a few predefined properties which you should use whenever possible
44+
as they are already used in many algorithms, but you can also define your own properties.
45+
46+
Predefined properties include:
47+
48+
- `edge_weight_t`. Used for most algorithms that have a single value associated to each
49+
edge such as Dijikstra.
50+
51+
- `vertex_name_t`
52+
*/
53+
{
54+
typedef boost::property<boost::vertex_name_t, std::string> VertexProperties;
55+
typedef boost::property<boost::edge_weight_t, int> EdgeProperties;
56+
}
57+
58+
/*
59+
Multiple properties can be specified either by:
60+
61+
- using a custom class as the property type. TODO is there any limitation to this?
62+
- chaining multile properties
63+
*/
64+
{
65+
}
66+
67+
/*
68+
The absense of a property is speficied by boost::no_property.
69+
*/
70+
{
71+
typedef boost::no_property VertexProperties;
72+
}
73+
74+
}
75+
76+
typedef boost::property<boost::vertex_name_t, std::string> VertexProperties;
77+
typedef boost::property<boost::edge_weight_t, int> EdgeProperties;
3078
typedef boost::adjacency_list<
3179
// Data structure to represent the out edges for each vertex.
3280
// Possibilities:
@@ -48,18 +96,25 @@ int main() {
4896
// #bidirectionalS: directed graph with access to in and out edges
4997
// #directedS: directed graph with access only to out-edges
5098
// #undirectedS: undirected graph
51-
boost::bidirectionalS
99+
boost::bidirectionalS,
100+
101+
// Optional.
102+
VertexProperties,
103+
104+
// Optional.
105+
EdgeProperties
52106
> Graph;
107+
//typedef boost::graph_traits<Graph>::vertex_iterator VertexIter;
108+
//typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
109+
//typedef boost::property_map<Graph, boost::vertex_index_t>::type IndexMap;
53110

54-
// Fix number of vertexes, and add one edge at a time.
55-
{
56-
int num_vertices = 3;
57-
Graph g(num_vertices);
58-
boost::add_edge(0, 1, g);
59-
boost::add_edge(1, 2, g);
60-
}
111+
// Fix number of vertices, and add one edge at a time.
112+
int num_vertices = 3;
113+
Graph g(num_vertices);
114+
boost::add_edge(0, 1, g);
115+
boost::add_edge(1, 2, g);
61116

62-
// Fix number of vertexes, and add one edge array.
117+
// Fix number of vertices, and add one edge array.
63118
{
64119
int num_vertices = 3;
65120
typedef std::pair<int, int> Edge;
@@ -70,7 +125,44 @@ int main() {
70125
Graph g(edges.data(), edges.data() + edges.size(), num_vertices);
71126
}
72127

73-
// It is also possible to add vertices with add_vertex.
128+
// It is also possible to add vertices with #add_vertex.
129+
130+
//#vertices
131+
{
132+
// Number of vertices.
133+
boost::graph_traits<Graph>::vertices_size_type num_vertices = boost::num_vertices(g);
134+
assert(num_vertices == 3u);
135+
136+
//#vertices() Returns a begin() end() vertex iterator pair so we know where to stop.
137+
{
138+
typedef std::vector<boost::graph_traits<Graph>::vertex_descriptor> Vertices;
139+
Vertices vertices;
140+
vertices.reserve(num_vertices);
141+
//IndexMap
142+
auto index = boost::get(boost::vertex_index, g);
143+
//std::pair<vertex_iter, vertex_iter> vp
144+
for (auto vp = boost::vertices(g); vp.first != vp.second; ++vp.first) {
145+
// Vertex
146+
auto v = *vp.first;
147+
vertices.push_back(index[v]);
148+
}
149+
assert((vertices == Vertices{0, 1, 2}));
150+
}
151+
152+
// The iterator is a ranom access iterator.
153+
{
154+
auto index = boost::get(boost::vertex_index, g);
155+
auto it = boost::vertices(g).first;
156+
assert(index[it[2]] == 2);
157+
assert(index[it[1]] == 1);
158+
}
159+
}
160+
161+
//#edges
162+
{
163+
// It seems that only AdjencyMatrix has a method to get an edge given two vertices:
164+
//edge(u, v, g)
165+
}
74166
}
75167

76168
//#source is also a global function: <http://stackoverflow.com/questions/16114616/why-is-boost-graph-librarys-source-a-global-function>
@@ -130,7 +222,7 @@ int main() {
130222
dot_file << "digraph D {\n" << " rankdir=LR\n" << " size=\"4,3\"\n"
131223
<< " ratio=\"fill\"\n" << " edge[style=\"bold\"]\n" << " node[shape=\"circle\"]\n";
132224
boost::graph_traits <Graph>::edge_iterator ei, ei_end;
133-
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
225+
for (std::tie(ei, ei_end) = boost::edges(g); ei != ei_end; ++ei) {
134226
edge_descriptor e = *ei;
135227
boost::graph_traits<Graph>::vertex_descriptor
136228
u = boost::source(e, g), v = boost::target(e, g);

‎cpp.cpp‎

Lines changed: 70 additions & 49 deletions
Original file line numberDiff line numberDiff line change
@@ -7235,7 +7235,9 @@ int main(int argc, char **argv) {
72357235
// Get input out of streams into string.
72367236
// Overloaded for many different types of inputs: <http://www.cplusplus.com/reference/istream/istream/operator%3E%3E/>
72377237
{
7238-
// char*, std::string: reads until a whitespace character, as defined by `isspace`.
7238+
// char*, std::string
7239+
// - skip whitespace as defined by `isspace`.
7240+
// - read until first whitespace found
72397241
{
72407242
std::stringstream ss("ab cd\tef \t\ngh i.;)j");
72417243
std::string s;
@@ -7251,16 +7253,24 @@ int main(int argc, char **argv) {
72517253
assert(s == "i.;)j");
72527254
}
72537255

7254-
// Numeric types: int, float. Parse type until it cannot be part of the type anymore.
7256+
// Numeric types: int, float.
7257+
// - skip whitespace as defined by `isspace`.
7258+
// - read until cannot be part of the type anymore (TODO what does that mean exactly?)
72557259
{
7256-
std::stringstream ss("1.0 2 3.0f a");
7260+
std::stringstream ss("1.0 2 \n \t 3.0f 4a a");
72577261
float f;
7262+
std::string s;
72587263
ss >> f;
72597264
assert(f == 1.0f);
72607265
ss >> f;
72617266
assert(f == 2.0f);
72627267
ss >> f;
72637268
assert(f == 3.0f);
7269+
7270+
// f suffix is not part of floats
7271+
ss >> s;
7272+
assert(s == "f");
7273+
72647274
ss >> f;
72657275
// TODO what happens? Error checking.
72667276
}
@@ -7946,20 +7956,7 @@ int main(int argc, char **argv) {
79467956
assert(v.data()[1] == v[1]);
79477957
}
79487958

7949-
/*
7950-
Size related methods:
7951-
7952-
- size no of elements pushed back
7953-
- empty same as size() == 0
7954-
- max_size maximum size (estimtion of what could fit your computer ram)
7955-
7956-
Allocation related:
7957-
7958-
- reserve change how much memory is allocated but not actual size.
7959-
If smaller or less than current capacity, do nothing.
7960-
- shrink_to_fit shrink allocated array to size
7961-
- data get pointer to allocated array
7962-
*/
7959+
//size methods
79637960
{
79647961
/*
79657962
#size #size_type
@@ -7975,35 +7972,12 @@ int main(int argc, char **argv) {
79757972
assert(v.size() == 1);
79767973
}
79777974

7978-
/*
7979-
#capacity
7980-
7981-
Get currently allocated size.
7982-
7983-
Different from size, which is the number of elements in the std::vector!
7984-
7985-
At least as large as size.
7986-
*/
7987-
{
7988-
std::cout << "capacity:" << std::endl;
7989-
std::vector<int> v{};
7990-
std::cout << " " << v.capacity() << std::endl;
7991-
v.push_back(0);
7992-
std::cout << " " << v.capacity() << std::endl;
7993-
v.push_back(1);
7994-
std::cout << " " << v.capacity() << std::endl;
7995-
v.push_back(2);
7996-
std::cout << " " << v.capacity() << std::endl;
7997-
v.reserve(v.capacity() + 1);
7998-
std::cout << " " << v.capacity() << std::endl;
7999-
std::cout << std::endl;
8000-
}
8001-
80027975
/*
80037976
#resize
80047977
8005-
if larger than current size, append given element at end
8006-
if smaller than current size, remove elements from end
7978+
If larger than current size, append given element at end.
7979+
7980+
If smaller than current size, remove elements from end.
80077981
*/
80087982
{
80097983
// Reduce size
@@ -8033,13 +8007,60 @@ int main(int argc, char **argv) {
80338007
}
80348008
}
80358009

8010+
//capacity methods
8011+
{
8012+
/*
8013+
#capacity
8014+
8015+
Get currently allocated size.
8016+
8017+
Different from size, which is the number of elements in the std::vector!
8018+
8019+
At least as large as size.
8020+
8021+
Likely to be a power of 2 on most implementations.
8022+
*/
8023+
{
8024+
std::vector<int> v;
8025+
v.push_back(0);
8026+
v.push_back(1);
8027+
v.push_back(2);
8028+
assert(v.capacity() >= 3);
8029+
std::cout << "capacity = " << v.capacity() << std::endl;
8030+
}
8031+
8032+
//#max_size: estimative of what your OS allows you to allocate
8033+
{
8034+
std::cout << "max_size (MiB) = " << std::vector<int>().max_size() / (1 << 20) << std::endl;
8035+
}
8036+
8037+
//#reserve: increase allocated size if larger than current size.
8038+
{
8039+
std::vector<int> v;
8040+
v.reserve(3);
8041+
assert(v.capacity() >= 3);
8042+
// size() is untouched
8043+
assert(v.empty());
8044+
}
8045+
8046+
#if __cplusplus >= 201103L
8047+
//#shrink_to_fit
8048+
{
8049+
std::vector<int> v{0, 1};
8050+
v.reserve(4);
8051+
v.shrink_to_fit();
8052+
assert(v.capacity() == 2);
8053+
}
8054+
#endif
8055+
}
8056+
80368057
// `std::vector` stores copies of elements, not references.
80378058
{
80388059
std::string s = "abc";
80398060
std::vector<std::string> v{s};
80408061
v[0][0] = '0';
8041-
assert(v[0] == "0bc");
8042-
assert(s == "abc");
8062+
assert(v[0] == "0bc");
8063+
assert(s == "abc");
80438064
}
80448065

80458066
// Modify.
@@ -8414,7 +8435,7 @@ int main(int argc, char **argv) {
84148435
}
84158436

84168437
/*
8417-
insert
8438+
#insert
84188439
84198440
Like for std::vector, insert makes copies.
84208441
@@ -8723,21 +8744,21 @@ int main(int argc, char **argv) {
87238744
std::list<int> l{0, 1};
87248745
}
87258746

8726-
//emplace
8747+
//#emplace
87278748
{
87288749
std::list<int> l{0, 1};
87298750
l.emplace(++l.begin(), 2);
87308751
assert(l == std::list<int>({0, 2, 1}));
87318752
}
87328753

8733-
//remove: remove all elements with a given value from list
8754+
//#remove: remove all elements with a given value from list
87348755
{
87358756
std::list<int> l{0, 1, 0, 2};
87368757
l.remove(0);
87378758
assert(l == std::list<int>({1, 2}));
87388759
}
87398760

8740-
//splice: transfer elements from one list to another
8761+
//#splice: transfer elements from one list to another
87418762
{
87428763
std::list<int> l{0, 1};
87438764
std::list<int> l2{2, 3};

0 commit comments

Comments
 (0)