Part of the Graph package.
This module shows how to use the Boost Graph library in DGtal.
The Boost Graph Library (http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/index.html) is a very rich library for handling graph concepts, structures and algorithms. It uses a lot generic programming to define a typology of graphs through a hierarchy of concept, and then it provides many generic algorithms on these graphs. Standard implementation of graphs are also provided (adjacency list, incidence matrix). Furthermore this library uses the Boost Property Map Library (http://www.boost.org/doc/libs/1_52_0/libs/property_map/doc/property_map.html) to associate data with vertices or edges in a very efficient and generic way.
For these reasons, it would be interesting that DGtal graphs match boost graph concepts. However, this cannot be done in full genericity with the present DGtal graph concepts. For instance, only finite graphs are handled by boost graphs. Furthermore, it is tricky to have light boost graphs (i.e. graphs constructed on-the-fly), because boost graphs require multipass iterators on vertices and edges.
For now, the only models that are wrapped to satisfy boost graph concepts are:
The file DigitalSurfaceBoostGraphInterface.h defines the boost graph traits for any kind of digital surface (see DigitalSurface). With these definitions, a DigitalSurface is a model of boost::VertexListGraphConcept, boost::AdjacencyGraphConcept, boost::IncidenceGraphConcept, boost::EdgeListGraphConcept. You may use a DigitalSurface as any boost graph instance in boost graph algorithms (see http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/table_of_contents.html).
A model of boost graph must satisfy a given number of traits (to define types) as well as functions acting on these types. This is done through specialization of boost::graph_traits. This is done for concrete realizations of template class DigitalSurface. The following snippet shows the boost graph way to get the types associated to a graph.
You may check that a DigitalSurface satisfies several graph concepts
For any boost graph, there is a function boost::vertices that returns a pair of multipass input iterator on vertices representing the range of vertices of the graph. The following snippet shows how it works.
For models of EdgeListGraphConcept, there is a function boost::edges that returns a pair of multipass input iterator on edges representing the range of (oriented) edges of the graph. The following snippet shows how it works.
For models of IncidenceGraphConcept, there is a function boost::out_edges that returns a pair of multipass input iterator on the edges that starts at the given vertex and ends on adjacent vertices. The following snippet shows how it works.
If you wish to use algorithms of the Boost Graph Library, most of them requires mapping from vertex or edge to some value (for instance a color for marking already visited vertices or a scalar for storing a distance or a weight). This is done very generically in Boost Graph through property maps. The system is rather complex but allows you to use indifferently in your algorithms an external map (for instance a std::map< vertex_descriptor, int >) or an embedded value in the vertex_descriptor type.
Standard boost graphs models offer simple mechanism to get a given property map for a graph. In DGtal, graph models do not integrate – for now – property maps. Therefore, only external property maps can be used. The snippet below shows how to create two property maps for the digital surface
g, using standard property map wrappers given in the Boost Property Map Library.
We may afterwards use this property maps in boost graph algorithms. This snippet extracts the connected components of the graph
g, and labels each vertex with its component (result is stored in
componentMap, hence is also accessible with
propColorMap is given a named parameter with a call to boost::color_map. This is the method used in the Boost Graph Library to give handle parameters, especially when the algorithm requires a lot of parameters, some of them being optionnal. This is explained in section (http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/bgl_named_params.html).
We need to store distances to the start vertex, therefore we create a dedicated property map (here
propDistanceMap). The algorithm also requires a queue (here
Q) and a first vertex (
The following snippet computes a vertex that is as far away as possible from
You may have a look at graph/testDigitalSurfaceBoostGraphInterface.cpp to see a few more examples of using Boost Graph algorithms (max-flow and min-cut).
The file ObjectBoostGraphInterface.h defines the boost graph traits for any kind of Object (see Object). With those definitios, an Object is a model of VertexListGraphConcept, AdjacencyGraphConcept, IncidenceGraphConcept, EdgeListGraphConcept. You may use an Object as a graph in any Boost Graph Library algorithm that satisfies the mentioned concepts.