1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <iterator>
#include <vector>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Construct_theta_graph_2.h>
#include <CGAL/property_map.h>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
// select the kernel type
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Direction_2 Direction_2;
/* define the struct for edge property */
struct Edge_property {
/* record the Euclidean length of the edge */
double euclidean_length;
};
// define the Graph (e.g., to be undirected,
// and to use Edge_property as the edge property, etc.)
typedef boost::adjacency_list<boost::listS,
boost::vecS,
boost::undirectedS,
Point_2,
Edge_property> Graph;
int main(int argc, char ** argv)
{
const std::string fname = argc!=3 ? "data/n20.cin" : argv[2];
unsigned int k = argc!=3 ? 6 : atoi(argv[1]);
if (argc != 3) {
std::cout << "Usage: " << argv[0] << " <no. of cones> <input filename>" << std::endl;
std::cout << "Using default values " << k << " " << fname << "\n";
}
if (k<2) {
std::cout << "The number of cones should be larger than 1!" << std::endl;
return 1;
}
// open the file containing the vertex list
std::ifstream inf(fname);
if (!inf) {
std::cout << "Cannot open file " << argv[1] << "!" << std::endl;
return 1;
}
// iterators for reading the vertex list file
std::istream_iterator< Point_2 > input_begin( inf );
std::istream_iterator< Point_2 > input_end;
// initialize the functor
// If the initial direction is omitted, the x-axis will be used
CGAL::Construct_theta_graph_2<Kernel, Graph> theta(k);
// create an adjacency_list object
Graph g;
// construct the theta graph on the vertex list
theta(input_begin, input_end, g);
// select a source vertex for dijkstra's algorithm
boost::graph_traits<Graph>::vertex_descriptor v0;
v0 = vertex(0, g);
std::cout << "The source vertex is: " << g[v0] << std::endl;
std::cout << "The index of source vertex is: " << v0 << std::endl;
// calculating edge length in Euclidean distance and store them in the edge property
boost::graph_traits<Graph>::edge_iterator ei, ei_end;
for (std::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
boost::graph_traits<Graph>::edge_descriptor e = *ei;
boost::graph_traits<Graph>::vertex_descriptor u = source(e, g);
boost::graph_traits<Graph>::vertex_descriptor v = target(e, g);
const Point_2& pu = g[u];
const Point_2& pv = g[v];
double dist = CGAL::sqrt( CGAL::to_double(CGAL::squared_distance(pu,pv)) );
g[e].euclidean_length = dist;
std::cout << "Edge (" << g[u] << ", " << g[v] << "): " << dist << std::endl;
}
// calculating the distances from v0 to other vertices
boost::graph_traits<Graph>::vertices_size_type n = num_vertices(g);
// vector for storing the results
std::vector<double> distances(n);
// Calling the Dijkstra's algorithm implementation from boost.
boost::dijkstra_shortest_paths(g,
v0,
boost::weight_map(get(&Edge_property::euclidean_length, g)).
distance_map(CGAL::make_property_map(distances)) );
std::cout << "distances are:" << std::endl;
for (unsigned int i=0; i < n; ++i) {
std::cout << "distances[" << i << "] = " << distances[i] << ", (x,y)=" << g[vertex(i, g)];
std::cout << " at Vertex " << i << std::endl;
}
return 0;
}
|
