Skip to content

Commit 2cd72da

Browse files
cirosantillicirosantilli
committed
Improve graph cheat.
1 parent 3b3305a commit 2cd72da

2 files changed

Lines changed: 121 additions & 20 deletions

File tree

‎boost/graph.cpp‎

Lines changed: 75 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -11,27 +11,88 @@
1111

1212
int main() {
1313

14-
//#source
15-
//
16-
// Source is also a global function: <http://stackoverflow.com/questions/16114616/why-is-boost-graph-librarys-source-a-global-function>
14+
/*
15+
#Graph
1716
18-
// #dijikstra
17+
The following class hierarchy exists:
18+
19+
BidirectionalGraph -------- Incience ---------+
20+
|
21+
Adjacency --------+
22+
|
23+
VertexAndEdgeList ----+---- VertexList -------+---- Graph
24+
| |
25+
+---- EdgeList ---------+
26+
|
27+
AdjacenyMatrix ---+
28+
*/
29+
{
30+
typedef boost::adjacency_list<
31+
// Data structure to represent the out edges for each vertex.
32+
// Possibilities:
33+
//
34+
// #vecS selects std::vector.
35+
// #listS selects std::list.
36+
// #slistS selects std::slist.
37+
// #setS selects std::set.
38+
// #multisetS selects std::multiset.
39+
// #hash_setS selects std::hash_set.
40+
//
41+
// `S` standas for Selector.
42+
boost::vecS,
43+
44+
// Data structure to represent the vertex set.
45+
boost::vecS,
46+
47+
// Directed type.
48+
// #bidirectionalS: directed graph with access to in and out edges
49+
// #directedS: directed graph with access only to out-edges
50+
// #undirectedS: undirected graph
51+
boost::bidirectionalS
52+
> Graph;
53+
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+
}
61+
62+
// Fix number of vertexes, and add one edge array.
63+
{
64+
int num_vertices = 3;
65+
typedef std::pair<int, int> Edge;
66+
std::vector<Edge> edges{
67+
{0, 1},
68+
{1, 2},
69+
};
70+
Graph g(edges.data(), edges.data() + edges.size(), num_vertices);
71+
}
72+
73+
// It is also possible to add vertices with add_vertex.
74+
}
75+
76+
//#source is also a global function: <http://stackoverflow.com/questions/16114616/why-is-boost-graph-librarys-source-a-global-function>
77+
78+
//#dijikstra
79+
std::cout << "#dijkstra" << std::endl;
1980
{
2081
typedef boost::adjacency_list<
2182
boost::listS,
2283
boost::vecS,
2384
boost::directedS,
2485
boost::no_property,
2586
boost::property<boost::edge_weight_t, int>
26-
> graph_t;
27-
typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_descriptor;
28-
typedef boost::graph_traits<graph_t>::edge_descriptor edge_descriptor;
29-
typedef std::pair<int, int> edge_t;
87+
> Graph;
88+
typedef boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
89+
typedef boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
90+
typedef std::pair<int, int> Edge;
3091

3192
// Model inputs.
3293
const int num_nodes = 5;
3394
const int sorce = 0;
34-
std::vector<edge_t> edge_array{
95+
std::vector<Edge> edges{
3596
{0, 2}, {1, 1}, {1, 3}, {1, 4}, {2, 1},
3697
{2, 3}, {3, 4}, {4, 0}, {4, 1}
3798
};
@@ -41,7 +102,7 @@ int main() {
41102
};
42103

43104
// Solve.
44-
graph_t g(edge_array.data(), edge_array.data() + edge_array.size(), weights.data(), num_nodes);
105+
Graph g(edges.data(), edges.data() + edges.size(), weights.data(), num_nodes);
45106
std::vector<vertex_descriptor> p(num_vertices(g));
46107
std::vector<int> d(num_vertices(g));
47108
vertex_descriptor s = vertex(sorce, g);
@@ -57,21 +118,21 @@ int main() {
57118

58119
// Print solution to stdout.
59120
std::cout << "node | distance from source | parent" << std::endl;
60-
boost::graph_traits<graph_t>::vertex_iterator vi, vend;
121+
boost::graph_traits<Graph>::vertex_iterator vi, vend;
61122
for (boost::tie(vi, vend) = vertices(g); vi != vend; ++vi)
62123
std::cout << *vi << " " << d[*vi] << " " << p[*vi] << std::endl;
63124
std::cout <<std::endl;
64125

65126
// Generate a .dot graph file with shortest path highlighted.
66127
// To PNG with: dot -Tpng -o outfile.png input.dot
67-
boost::property_map<graph_t, boost::edge_weight_t>::type weightmap = boost::get(boost::edge_weight, g);
128+
boost::property_map<Graph, boost::edge_weight_t>::type weightmap = boost::get(boost::edge_weight, g);
68129
std::ofstream dot_file("dijkstra.dot");
69130
dot_file << "digraph D {\n" << " rankdir=LR\n" << " size=\"4,3\"\n"
70131
<< " ratio=\"fill\"\n" << " edge[style=\"bold\"]\n" << " node[shape=\"circle\"]\n";
71-
boost::graph_traits <graph_t>::edge_iterator ei, ei_end;
132+
boost::graph_traits <Graph>::edge_iterator ei, ei_end;
72133
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
73134
edge_descriptor e = *ei;
74-
boost::graph_traits<graph_t>::vertex_descriptor
135+
boost::graph_traits<Graph>::vertex_descriptor
75136
u = boost::source(e, g), v = boost::target(e, g);
76137
dot_file << u << " -> " << v << "[label=\"" << boost::get(weightmap, e) << "\"";
77138
if (p[v] == u)

‎cpp.cpp‎

Lines changed: 46 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1220,6 +1220,26 @@ void printCallStack() {
12201220
virtual int b() { return 10; }
12211221
};
12221222

1223+
class VirtualFromCtor2PhaseBase {
1224+
public:
1225+
int i;
1226+
int j;
1227+
VirtualFromCtor2PhaseBase() {}
1228+
void init() {
1229+
this->i = a();
1230+
this->j = b();
1231+
}
1232+
virtual int a() { return 0; }
1233+
virtual int b() = 0;
1234+
};
1235+
1236+
class VirtualFromCtor2PhaseDerived : public VirtualFromCtor2PhaseBase {
1237+
public:
1238+
VirtualFromCtor2PhaseDerived() { init(); }
1239+
virtual int a() { return 1; }
1240+
virtual int b() { return 10; }
1241+
};
1242+
12231243
class MultipleInheritanceConflictBase1 {
12241244
public:
12251245
const static int is = 1;
@@ -6214,10 +6234,19 @@ int main(int argc, char **argv) {
62146234
// Call virtual method from base constructor: http://stackoverflow.com/questions/496440/c-virtual-function-from-constructor?lq=1
62156235
// Not possible because derived class has not yet been initialized.
62166236
// Workaround? http://www.parashift.com/c%2B%2B-faq-lite/calling-virtuals-from-ctor-idiom.html
6217-
// THe simplest thing to do seems to be to define a separate init function.
62186237
{
6219-
VirtualFromCtorDerived c;
6220-
assert(c.i == 0);
6238+
{
6239+
VirtualFromCtorDerived c;
6240+
assert(c.i == 0);
6241+
}
6242+
6243+
// The simplest thing to do seems to be to define a separate init function.
6244+
// Downside: requires you to write a new constructor on the derived, and forward all argments.
6245+
{
6246+
VirtualFromCtor2PhaseDerived c;
6247+
assert(c.i == 1);
6248+
assert(c.j == 10);
6249+
}
62216250
}
62226251
}
62236252

@@ -7235,6 +7264,17 @@ int main(int argc, char **argv) {
72357264
ss >> f;
72367265
// TODO what happens? Error checking.
72377266
}
7267+
7268+
// Since `>>` returns the istream, it is possible to chain calls:
7269+
{
7270+
std::stringstream ss("1 1.5 2");
7271+
int i, j;
7272+
float f;
7273+
ss >> i >> f >> j;
7274+
assert(i == 1);
7275+
assert(f == 1.5);
7276+
assert(j == 2);
7277+
}
72387278
}
72397279

72407280
/*
@@ -9031,9 +9071,9 @@ int main(int argc, char **argv) {
90319071
//pointer
90329072
//reference
90339073
{
9034-
typedef std::iterator_traits<std::vector<int>::iterator>::value_type ValueType;
9035-
typedef std::iterator_traits<std::vector<int>::iterator>::pointer Pointer;
9036-
typedef std::iterator_traits<std::vector<int>::iterator>::reference Reference;
9074+
typedef std::iterator_traits<std::vector<int>::iterator>::value_type ValueType;
9075+
typedef std::iterator_traits<std::vector<int>::iterator>::pointer Pointer;
9076+
typedef std::iterator_traits<std::vector<int>::iterator>::reference Reference;
90379077
assert(typeid(ValueType) == typeid(int));
90389078
assert(typeid(Pointer) == typeid(int*));
90399079
assert(typeid(Reference) == typeid(int&));

0 commit comments

Comments
 (0)