\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.14 - Cone-Based Spanners
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 97.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 97.1 (b) gives an example of Yao graph with \(k=5\).

Example-Y5.jpg
Figure 97.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 97.2, vertex \(u\)'s closest vertex will be vertex \(b\).

BisectorInThetaGraph.jpg
Figure 97.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:

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);

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 Kernel::Point_2 Point_2;
typedef Kernel::Direction_2 Direction_2;
int main(int argc, char ** argv) {
if (argc < 2) {
std::cout << "Usage: " << argv[0] << " <no. of cones> [<direction-x> <direction-y>]" << std::endl;
return 1;
}
unsigned int k = atoi(argv[1]);
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
// 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;
}

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 <boost/lexical_cast.hpp>
#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 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 http://lists.boost.org/Archives/boost/2016/05/229458.php.
*/
// define the graph type
typedef boost::adjacency_list<boost::listS,
boost::vecS,
#ifdef CGAL_CXX11
boost::undirectedS,
#else
boost::directedS,
#endif
Point_2
> Graph;
int main(int argc, char ** argv)
{
if (argc < 3) {
std::cout << "Usage: " << argv[0] << " <no. of cones> <input filename> [<direction-x> <direction-y>]" << std::endl;
return 1;
}
unsigned int k = atoi(argv[1]);
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(argv[2]);
if (!inf) {
std::cout << "Cannot open file " << argv[2] << "!" << std::endl;
return 1;
}
Direction_2 initial_direction;
if (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" + boost::lexical_cast<std::string>(k) + "n" + boost::lexical_cast<std::string>(n);
CGAL::gnuplot_output_2(g, file_prefix);
return 0;
}

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 97.3 shows the Theta graph plotted when the above t4n20.plt is loaded by Gnuplot.

t4n20.jpg
Figure 97.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 a 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.
// Construct an Half Theta graph with the edges only in the odd cones.
// Construct an Half Yao graph with the edges only in the even cones.
// Construct an Half Yao graph with the edges only in the odd cones.

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 97.4. Based on our definition on Theta graph presented in the Section Definitions, we can verify that the Theta graph in Figure 97.4 is correctly constructed.

t4n9exact.jpg
Figure 97.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 97.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.

t4n9inexact.jpg
Figure 97.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 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)
{
if (argc != 3) {
std::cout << "Usage: " << argv[0] << " <no. of cones> <input filename>" << std::endl;
return 1;
}
unsigned int k = atoi(argv[1]);
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(argv[2]);
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
// 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 (boost::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];
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;
}