1 #include <boost/graph/graph_traits.hpp>
2 #include <boost/graph/adjacency_list.hpp>
3 #include <boost/graph/dijkstra_shortest_paths.hpp>
4 using namespace boost;
5
6 #include <iostream> // for std::cout
7 #include <utility> // for std::pair
8 #include <algorithm> // for std::for_each
9 using namespace std;
10
11 #include <limits.h>
12
13 int main(int,char*[])
14 {
15
16 typedef adjacency_list < listS, vecS, /*directedS*/undirectedS,
17 no_property, property < edge_weight_t, int > > Graph;
18 typedef graph_traits < Graph >::vertex_descriptor VertexDescriptor;
19 typedef graph_traits < Graph >::edge_descriptor EdgeDescriptor;
20 typedef graph_traits<Graph>::edge_iterator EdgeIterator;
21 typedef graph_traits<Graph>::vertex_iterator VertexIterator;
22 typedef std::pair<int, int> Edge;
23 typedef std::pair<EdgeDescriptor, bool> EdgeExistResult;
24
25 const int vertice_num = 65536;
26
27 Graph g(vertice_num);
28
29 add_edge(0, 1, 1, g); // first, second, weight, graph
30 add_edge(1, 2, 1, g);
31 add_edge(2, 3, 1, g);
32 add_edge(1, 3, 1, g);
33
34 EdgeExistResult edge_exist = edge(3, 1, g);
35 if (edge_exist.second == true) {
36 cout << "yes" << endl;
37 } else {
38 cout << "no" << endl;
39 }
40
41 EdgeIterator ei, ei_end;
42 for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
43 cout << source(*ei, g) << "," << target(*ei, g) << endl;
44 }
45
46 /* graph_traits<Graph>::vertex_iterator vi, vi_end;
47 for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
48 cout << *vi << endl;
49 } */
50
51 vector<VertexDescriptor> parent(num_vertices(g));
52 vector<int> dist(num_vertices(g));
53 VertexDescriptor s = vertex(3, g);
54 dijkstra_shortest_paths(g, s, predecessor_map(&parent[0]).distance_map(&dist[0]));
55 // shortest path from 3 to 0
56 if (dist[0] != INT_MAX)
57 cout << dist[0] << endl;
58
59 int i = 0;
60 while (i != 3) {
61 cout << i << endl;
62 i = parent[i];
63 }
64 return 0;
65
66 }