CGAL 6.1 - Cone-Based Spanners

Loading...
Searching...
No Matches
User Manual

Author
  Weisheng Si, Quincy Tse and Frédérik Paradis

# Introduction

This chapter describes the package for constructing two kinds of cone-based spanners: Yao graph and Theta graph, given a set of vertices on the plane and the directions of cone boundaries. Both exact and inexact constructions are supported. In exact construction, the cone boundaries are calculated using roots of polynomials, which achieves the exactness by avoiding using \( \pi \) in the computation. In inexact construction, the cone boundaries are calculated with a floating point approximation of \( \pi \) value and is still accurate enough for most applications. Moreover, for visualization purpose, this chapter describes a global function that, given a constructed graph as input, can generate the data and script files for `Gnuplot` to plot that graph.

# Definitions

This section gives detailed definitions of Yao graph and Theta graph, which are followed in our implementation. In particular, because this package supports constructing Yao graph and Theta graph exactly, we need to be clear on which cone a cone boundary belongs to. The definitions presented here clarify on this.

Given a set \(V\) of vertices on the plane, the directed Yao Graph with an integer parameter \(k (k > 1)\) on \(V\) is obtained as follows. For each vertex \(u \in V\), starting from a given direction (e.g., the direction of positive \(x\)-axis), draw \(k\) equally-spaced rays \(l_0\), \(l_1\), ..., \(l_{k-1}\) originating from \(u\) in counterclockwise order (see Figure 114.1 (a)). These rays divide the plane into \(k\) cones of angle \(2\pi/k\), denoted by \( c(u, 0), c(u, 1), ..., c(u, k-1)\) respectively in counterclockwise order. To avoid overlapping at boundaries, it is stipulated here that the area of \( c(u, i)\), where \( i=0, \ldots, k-1\), includes the ray \(l_{i}\) but excludes the ray \(l_{(i+1)\% k}\). In each cone of \(u\), draw a directed edge from \(u\) to its closest vertex by Euclidean distance in that cone. Ties are broken arbitrarily. These directed edges will form the edge set of the directed Yao graph on \(V\). The undirected Yao Graph on \(V\) is obtained by ignoring the directions of the edges. Note that if both edge \(uv\) and \(vu\) are in the directed Yao graph, only one edge \(uv\) exists in the undirected Yao graph. Figure 114.1 (b) gives an example of Yao graph with \(k=5\).

Figure 114.1 Cones and an example of Yao Graph with \(k=5\).

Similar to Yao graph, the directed or undirected Theta Graph is also obtained by letting each vertex \(u \in V\) select a closest vertex in each of its cones to have an edge. The only difference is that closest in Theta Graph means the smallest projection distance onto the bisector of that cone, not the direct Euclidean distance. For instance, in Figure 114.2, vertex \(u\)'s closest vertex will be vertex \(b\).

Figure 114.2 The bisector in a cone of a Theta Graph.

Variants of Yao graph and Theta graph are Half Yao graph and Half Theta graph. The difference is that only the edges in the even or odd cones are drawn. For instance, in the even case of the Theta graph with \(k=6\), only the edges in the cones \(c(u, 0)\), \(c(u, 2)\), and \(c(u, 4)\) are drawn.

# Software Design

This package provides the following template functors:

- `Compute_cone_boundaries_2`: The functor for computing the directions of cone boundaries given a cone number and an initial direction.
- `Construct_theta_graph_2`: The functor for constructing Theta graphs given a set of vertices on the plane.
- `Construct_yao_graph_2`: The functor for constructing Yao graphs given a set of vertices on the plane.

In addition to these functors, for visualizing the constructed graphs, this package provides a global function called `CGAL::gnuplot_output_2()` to output a `boost::adjacency_list` data structure to `Gnuplot` data and script files. Below, we detail the design and the usage of the above functors and function.

## Computing Cone Boundaries

The functor `Compute_cone_boundaries_2` has the following definition.

template <typename Traits>
class Compute_cone_boundaries_2;

The template parameter `Traits` determines whether the cone boundaries are computed exactly or inexactly. If this parameter is `Exact_predicates_exact_constructions_kernel_with_root_of`, the computation will be done exactly; if this parameter is `Exact_predicates_inexact_constructions_kernel`, the computation will be done inexactly. The exact computation is implemented based on the fact that when the cone angle \( \theta \) is in the form of \( 2\pi / n \), where \( n \) is a positive integer, \( \sin(\theta) \) and \( \cos(\theta) \) can be represented exactly by roots of polynomials, thus avoiding using \( \pi \) in the computation. The exact computation requires the number type of either `CORE::Expr` or `leda_real`. In inexact computation, the cone angle \( \theta \) is simply calculated as \( 2\pi/k \), where \( k \) is the number of cones and \( \pi \) takes the value of the constant `CGAL_PI=3.14159265358979323846`. Then, the \( \sin(\theta) \) and \( \cos(\theta) \) are calculated. While the inexact computation is done by the general functor definition, the exact computation is done by a specialization of this functor.

This functor is currently used by the functors `Construct_theta_graph_2` and `Construct_yao_graph_2` in constructing Theta and Yao graphs. This functor can also be used in other applications where the plane needs to be divided into equally-angled cones. For how to use this functor to compute cone boundaries in writing an application, please refer to Section Examples.

## Constructing a Theta Graph

The functor `Construct_theta_graph_2` has the following definition

template <typename Traits, typename Graph>
class Construct_theta_graph_2;

Similar to the functor `Compute_cone_boundaries_2`, the template parameter `Traits` determines whether the Theta graph will constructed exactly or inexactly. The template parameter `Graph` specifies the graph type used to store the constructed graph. Our package requires it to be boost::adjacency_list from the Boost Graph Library (BGL). The advantage of using `boost::adjacency_list` is that it provides convenience to the further processing of the constructed graphs, since BGL includes most common graph algorithms. Note that BGL altogether provides two template classes for representing graphs: `boost::adjacency_list` and `boost::adjacency_matrix`, with the former suitable for sparse graphs and the latter suitable for dense graphs. While cone-based spanners are sparse graphs and the interfaces provided by `boost::adjacency_list` and `boost::adjacency_matrix` are different, our package only supports `boost::adjacency_list`.

Note that there are seven template parameters for `boost::adjacency_list` in BGL: `OutEdgeList`, `VertexList`, `Directed`, `VertexProperties`, `EdgeProperties`, `GraphProperties`, `EdgeList`, of which we require `VertexProperties` to be `Traits::Point_2`, and other parameters can be chosen freely. Also note that, here we pass `Point_2` directly as bundled properties to `boost::adjacency_list`, because this makes our implementation more straightforward than using a property map. If you want more properties other than `Point_2` for vertices, you can still construct external properties by using property maps.

In constructing Theta graphs, this functor uses the algorithm from Chapter 4 of the book by Narasimhan and Smid [2]. Basically, it is a sweep line algorithm and uses a balanced search tree to store the vertices that have already been scanned. It has the complexity of \(O(n \log n)\), where \(n\) is the number of vertices in the plane. This complexity has been proved to be optimal.

For more details on how to use this `Construct_theta_graph_2` functor to write an application to build Theta graphs, please refer to Section Examples.

## Constructing a Yao Graph

The functor `Construct_yao_graph_2` has a similar definition as `Construct_theta_graph_2`.

template <typename Traits, typename Graph>
class Construct_yao_graph_2;

The way of using these two template parameters is the same as that of `Construct_theta_graph_2`, so please refer to the previous subsection for the details. We note here that construction algorithm for Yao graph is a slight adaptation of the algorithm for constructing Theta graph, having a complexity of \(O(n^2)\). The increase of complexity in this adaptation is because in constructing Theta graph, the searching of the 'closest' node by projection distance can be done by a balanced search tree, but in constructing Yao graph, the searching of the 'closest' node by Euclidean distance cannot be done by a balanced search tree.

Note that an optimal algorithm for constructing Yao graph with a complexity of \(O(n \log n)\) is described in [1]. However, this algorithm is much more complex to implement than the current algorithm implemented, and it can hardly reuse the codes for constructing Theta graphs, so it is not implemented in this package right now.

## Gnuplot Output

This package also implements a template function `CGAL::gnuplot_output_2()`, which reads a `boost::adjacency_list` object and generate two files used by `Gnuplot` to visualize the graph stored in the `boost::adjacency_list` object. This template function has the following definition:

template <typename Graph_>
void gnuplot_output_2(const Graph_& g, const std::string& prefix);
CGAL::gnuplot_output_2
void gnuplot_output_2(const Graph &g, const std::string &prefix)
outputs a set of files used by Gnuplot to plot g.
Definition: gnuplot_output_2.h:139

The template parameter `Graph_` specifies the type of the graph to be plotted. For this function to work, the graph type must be `boost::adjacency_list` with `Point_2` as the `VertexProperties`. As for the two arguments to the function, `g` gives the graph to be plotted, and `prefix` gives the prefix for the names of the files generated by the function. Specifically, this function will generate the following two files:

- A data file named `prefix.v` that contains the \((x, y)\)-coordinates of each vertex. To be read by `Gnuplot`, the \((x, y)\)-coordinates are written into the data file with decimal format, no matter which number type is used in the CGAL kernel. This is achieved by calling `to_double()` on \(x\) or \(y\) coordinate before outputting them.
- A `Gnuplot` script file named `prefix.plt` to be loaded by `Gnuplot` to plot the set of vertices and the set of edges. The set of vertices is read from the above data file and the set of edges are included in the script file with the syntax `set arrow from x1, y1 to x2, y2`.

For details on how to use this function to generate `Gnuplot` files, please refer to Section Examples.

# Examples

## Computing Cone Boundaries Exactly or Inexactly

The following example shows how to compute the directions of the cone boundaries exactly given the cone number and the initial direction. This example basically consists of the following steps:

1. Define `Exact_predicates_exact_constructions_kernel_with_root_of` as the kernel type to compute the cone boundaries exactly.
2. Construct a `Compute_cone_boundaries_2` object named `cones` with the above kernel as the template parameter. Note that since the functor `Compute_cone_boundaries_2` has no member variables but member types and functions, its constructor needs no arguments.
3. Initialize a vector of `Direction_2` named `rays` to store the computed results.
4. Use `cones` to compute the cone boundaries by passing the cone number, the initial direction and the beginning iterator of `rays` to it.
5. Output the computed results.

File Cone_spanners_2/compute_cones.cpp

#include <cstdlib>
#include <iostream>
#include <iterator>
#include <vector>
#include <CGAL/Exact_predicates_exact_constructions_kernel_with_root_of.h>
#include <CGAL/Compute_cone_boundaries_2.h>
// select the kernel type
typedef CGAL::Exact_predicates_exact_constructions_kernel_with_root_of Kernel;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Direction_2 Direction_2;
int main(int argc, char ** argv) {
unsigned int k = argc < 2 ? 6 : atoi(argv[1]);
if (argc < 2) {
std::cout << "Usage: " << argv[0] << " <no. of cones> [<direction-x> <direction-y>]" << std::endl;
std::cout << "Using default value " << k << "\n";
}
if (k<2) {
std::cout << "The number of cones should be larger than 1!" << std::endl;
return 1;
}
Direction_2 initial_direction;
if (argc <= 2)
initial_direction = Direction_2(1, 0); // default initial_direction
else if (argc == 4)
initial_direction = Direction_2(atof(argv[2]), atof(argv[3]));
else {
std::cout << "Usage: " << argv[0] << " <no. of cones> [<direction-x> <direction-y>]" << std::endl;
return 1;
}
// construct the functor
CGAL::Compute_cone_boundaries_2<Kernel> cones;
// create the vector rays to store the results
std::vector<Direction_2> rays(k);
// compute the cone boundaries and store them in rays
cones(k, initial_direction, rays.begin());
// display the computed rays, starting from the initial direction, ccw order
for (unsigned int i=0; i<k; i++)
std::cout << "Ray " << i << ": " << rays[i] << std::endl;
return 0;
}
CGAL::Compute_cone_boundaries_2
The functor for computing the directions of cone boundaries with a given cone number and a given init...
Definition: Compute_cone_boundaries_2.h:60
CGAL::Exact_predicates_exact_constructions_kernel_with_root_of
Kernel::Direction_2
Kernel::Point_2
Kernel

Note that, in this example, for any k<=28, the computation can be done successfully; for any k>28, the computation cannot be completed because `CORE::Expr`, which we use as the number type for the exact kernel, exceeds its limit. It seems that k<=28 will suffice for most applications. Also, if inexact computation is used, the computation will be successful for any k>1, and much quicker than exact computation. We also note here that we don't experiment with `leda_real`.

As a final note, to compute the cone boundaries inexactly, just define the `Kernel` to be `Exact_predicates_inexact_constructions_kernel` in the above example.

## Constructing Graphs Exactly or Inexactly and Generating Gnuplot Files

The following example shows how to construct Theta graphs exactly and generate `Gnuplot` files. This example basically consists of the following steps:

1. Define `Exact_predicates_exact_constructions_kernel_with_root_of` as the kernel type to construct the graph exactly.
2. Define the graph type to store the constructed graph.
3. Construct a `Construct_theta_graph_2` object named `theta` with the number of cones and the initial direction as constructor arguments.
4. Construct a graph object `g` to store the constructed graph.
5. Use `theta` to construct the Theta graph by passing the input vertices and `g` to it.
6. Generate `Gnuplot` files for plotting the construct graph.

File Cone_spanners_2/theta_io.cpp

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <iterator>
#include <string>
#include <vector>
#include <CGAL/Exact_predicates_exact_constructions_kernel_with_root_of.h>
#include <CGAL/Construct_theta_graph_2.h>
#include <CGAL/gnuplot_output_2.h>
// select the kernel type
typedef CGAL::Exact_predicates_exact_constructions_kernel_with_root_of Kernel;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Direction_2 Direction_2;
/* Note: due to a bug in the boost library, using a directed graph
* will cause a compilation error with g++ and clang++ when using c++11 standard.
* See https://lists.boost.org/Archives/boost/2016/05/229458.php.
*/
// define the graph type
typedef boost::adjacency_list<boost::listS,
boost::vecS,
boost::undirectedS,
Point_2
> Graph;
int main(int argc, char ** argv)
{
unsigned int k=4; // By default, no. of cones==4
std::string filename="data/n9.cin"; // file used by default
if (argc > 1 &&
(!strcmp(argv[1],"-h") || !strcmp(argv[1],"--help") || !strcmp(argv[1],"-?")))
{
std::cout << "Usage: " << argv[0] << " <no. of cones> <input filename> [<direction-x> <direction-y>]" << std::endl;
return 1;
}
if (argc > 1)
{
k = atoi(argv[1]);
if (k<2) {
std::cout << "The number of cones should be larger than 1!" << std::endl;
return 1;
}
}
if (argc > 2)
{ filename=std::string(argv[2]); }
// open the file containing the vertex list
std::ifstream inf(filename);
if (!inf) {
std::cout << "Cannot open file " << filename << "!" << std::endl;
return 1;
}
Direction_2 initial_direction;
if (argc == 1 || argc == 3)
initial_direction = Direction_2(1, 0); // default initial_direction
else if (argc == 5)
initial_direction = Direction_2(atof(argv[3]), atof(argv[4]));
else {
std::cout << "Usage: " << argv[0] << " <no. of cones> <input filename> [<direction-x> <direction-y>]" << 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
CGAL::Construct_theta_graph_2<Kernel, Graph> theta(k, initial_direction);
// create an adjacency_list object
Graph g;
// construct the theta graph on the vertex list
theta(input_begin, input_end, g);
// obtain the number of vertices in the constructed graph
boost::graph_traits<Graph>::vertices_size_type n = boost::num_vertices(g);
// generate gnuplot files for plotting this graph
std::string file_prefix = "t" + std::to_string(k) + "n" + std::to_string(n);
CGAL::gnuplot_output_2(g, file_prefix);
return 0;
}
CGAL::Construct_theta_graph_2
A template functor for constructing Theta graphs with a given set of 2D points and a given initial di...
Definition: Construct_theta_graph_2.h:52

To construct Theta graphs inexactly, just define the `Kernel` to be `Exact_predicates_inexact_constructions_kernel` in the above example. And the way of constructing Yao graphs exactly or inexactly is the same as that of constructing Theta graphs, just replacing the functor `Construct_theta_graph_2` by the functor `Construct_yao_graph_2`.

Note that, for Theta graph, the `Kernel` defined must support the `CGAL::sqrt()` operation. This is required by the `bisector()` function, which is used to calculate the angle bisector of a cone. For instance, the compiler will complain if `Exact_predicates_exact_constructions_kernel` (not supporting `CGAL::sqrt()`) is defined as the kernel, but `Exact_predicates_inexact_constructions_kernel` will be fine since it supports `CAL::sqrt()`. For Yao graph, there is no such restriction, since its construction does not need `CGAL::sqrt()`.

Also note that when using g++ or clang++ compilers with the c++11 standard, using a directed graph will cause a compilation error due to a bug in the boost library. As a workaround you can use a undirected graph instead.

After compiling `theta_io.cpp`, execute the executable `theta_io` to construct a Theta graph with 4 cones on a set of 20 vertices (which is given in the file `data/n20.cin`):

$ ./theta_io 4 data/n20.cin

The following two files will be generated for `Gnuplot`:

- `t4n20.v`: This file contains the \((x, y)\)-coordinates of the 20 vertices.
- `t4n20.plt`: This is the script to be loaded by `Gnuplot`. It will read `t4n20.v` to plot the vertices. It will also plot all the edges, which are included in this script itself.

Figure 114.3 shows the Theta graph plotted when the above `t4n20.plt` is loaded by `Gnuplot`.

Figure 114.3 A directed Theta graph of 20 vertices with \(k=4\).

## Constructing Half Theta or Yao Graphs

By default, the functors `Construct_theta_graph_2` and `Construct_yao_graph_2` construct full Theta and Yao graphs. They also provide a way to compute Half Theta and Yao graphs. As mentioned in Section Definitions, only the edges for the odd or even cones are added to the graph in an Half Theta and Yao graph. To do so, the constructor of the functors provides a parameter of type `Cones_selected` which is an enumeration that contains the following possible values: `ALL_CONES`, `EVEN_CONES` and `ODD_CONES`. Users should include the `CGAL/Cone_spanners_enum_2.h` header file to use these enum values. The following are the examples on the functor constructions for Half Theta and Yao Graphs.

// Construct an Half Theta graph with the edges only in the even cones.
CGAL::Construct_theta_graph_2<Kernel, Graph> theta(k, Direction_2(1,0), CGAL::EVEN_CONES);
// Construct an Half Theta graph with the edges only in the odd cones.
CGAL::Construct_theta_graph_2<Kernel, Graph> theta(k, Direction_2(1,0), CGAL::ODD_CONES);
// Construct an Half Yao graph with the edges only in the even cones.
CGAL::Construct_yao_graph_2<Kernel, Graph> yao(k, Direction_2(1,0), CGAL::EVEN_CONES);
// Construct an Half Yao graph with the edges only in the odd cones.
CGAL::Construct_yao_graph_2<Kernel, Graph> yao(k, Direction_2(1,0), CGAL::ODD_CONES);
CGAL::Construct_yao_graph_2
A template functor for constructing Yao graphs with a given set of 2D points and a given initial dire...
Definition: Construct_yao_graph_2.h:49
CGAL::ODD_CONES
@ ODD_CONES
selects odd cones.
Definition: Cone_spanners_enum_2.h:35
CGAL::EVEN_CONES
@ EVEN_CONES
selects even cones.
Definition: Cone_spanners_enum_2.h:32

## Exact Construction Can Make a Difference

This subsection gives an example vertex set on which the exact construction provided in this package can produce the correct Theta graph while the inexact construction cannot.

This vertex set, given in the file `examples/data/n9.cin`, consists of 9 vertices with the following \((x, y)\)-coordinates:

0.000000 0.000000
0.000000 1.000000
0.000000 2.000000
1.000000 0.000000
1.000000 1.000000
1.000000 2.000000
2.000000 0.000000
2.000000 1.000000
2.000000 2.000000

If we construct the directed Theta graph on this vertex set with \(k=4\) and its cone boundaries on the \(x\) and \(y\) axis, the exact construction will produce the Theta graph shown in Figure 114.4. Based on our definition on Theta graph presented in the Section Definitions, we can verify that the Theta graph in Figure 114.4 is correctly constructed.

Figure 114.4 The correct Theta graph produced by the exact construction.

On the other hand, the inexact construction will produce the Theta graph depicted in Figure 114.5. We can see that this Theta graph is not constructed correctly, since the inexact construction will make wrong decisions on whether those vertices on the cone boundaries belong to a certain cone.

Figure 114.5 The incorrect Theta graph produced by the inexact construction.

This example demonstrates that the exact construction capability provided by this package can be very valuable if it is a strict requirement that graphs be constructed correctly.

## Using BGL Algorithms

The following example, 'dijkstra_theta.cpp', shows how to call algorithms from BGL to do further processing after the graphs are constructed. Since the constructed Theta or Yao graphs are stored in the class `boost::adjacency_list`, it is convenient to apply BGL algorithms into the constructed graphs. Specifically, this example constructs a Theta graph first and then calculates the shortest paths on this graph by calling the Dijkstra's algorithm from BGL. It mainly consists of the following steps:

1. Define `Exact_predicates_inexact_constructions_kernel` as the kernel type to construct the graph inexactly.
2. Define a structure named `Edge_property` for storing the Euclidean length of each edge, which is needed by the Dijkstra's algorithm.
3. Define the graph type to store the constructed graph, passing `Edge_property` as a template parameter to the graph type `boost::adjacency_list`.
4. Construct a `Construct_theta_graph_2` object named `theta`.
5. Construct a graph object `g` to store the constructed graph.
6. Use `theta` to construct the Theta graph by passing the input vertices and `g` to it.
7. After `g` is constructed, calculate the Euclidean length of each edge in `g`.
8. Calculate the shortest distances from `v0` to other vertices by calling the function `dijkstra_shortest_paths()` from BGL.

File Cone_spanners_2/dijkstra_theta.cpp

#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;
}
CGAL::Exact_predicates_inexact_constructions_kernel
CGAL::to_double
double to_double(const NT &x)
CGAL::sqrt
NT sqrt(const NT &x)
CGAL::squared_distance
Kernel::FT squared_distance(Type1< Kernel > obj1, Type2< Kernel > obj2)