Re: [boost] Adapting boost::grid_graph vertex descriptors to Boost Geometry

Subject: Re: [boost] Adapting boost::grid_graph vertex descriptors to Boost Geometry
From: Seth (bugs_at_[hidden])
Date: 2017-10-29 21:26:22

On 29-10-17 21:12, Brook Milligan via Boost wrote:
> Generally Boost Graph vertex descriptors are opaque types with limited means of constructing them; they may be default constructed or constructed with the null_vertx() function, by dereferencing vertex iterators, calling source()/target() on an edge descriptor, or by calling the add_vertex() function.  It is never expected that one will construct a vertex descriptor directly with a non-default constructor.
>
> The Boost grid_graph is similar, with the exception that vertex descriptors may additionally be constructed from a vertex index.
>
> However, a vertex descriptor for an n-dimensional grid_graph is quite naturally an n-dimensional point.  Consequently, it should be possible, without breaking the abstraction, to construct one (and perhaps use one) as a point.  Given that this use is not documented in any way, doing so breaks the abstraction.
>
> At least three solutions are possible:
>
> - #include <boost/geometry/geometries/adapted/boost_array.hpp> in grid_graph.hpp: boost::array<> is the implementation of the grid graph vertex descriptor, so this would immediately make vertex descriptors model Boost Geometry points.
>
> - Add a boost/graph/adapt_grid_graph_to_geometry.hpp (better name needed) file that includes the same file so that the selection is optional.
>
> - Add a boost/geometry/geometries/adapted/grid_graph.hpp file that includes the same file, again making the selection optional.
>
> Since the contents of boost/geometry/geometries/adapted generally refer to external libraries (e.g., Boost Array), the last option seems the most appropriate, although it suffers in case the vertex descriptor is changed but not the adaptor.  That however applies to all the adaptors equally.
>
> Any of these solutions differs from using boost/geometry/geometries/adapted/boost_array.hpp directly in user code, because that requires unpacking the nature of the vertex descriptor and leaves open the potential for breaking changes in user code if the vertex descriptor changes.  Because a vertex descriptor is opaque, breaking the abstraction seems inappropriate, even here.
>
> Thus, I suggest the following:
>
> - add boost/geometry/geometries/adapted/grid_graph.hpp which includes boost/geometry/geometries/adapted/boost_array.hpp.
>
> - add the new adaptor to the Boost Geometry documentation
>
> - add a note to the Boost Graph grid_graph documentation indicating that it is possible to adapt the vertex descriptor and use it as a point.
>
> Thoughts?
>
> Cheers,
> Brook
>
Am I right in thinking you arlready have a working Proof Of Concept? Or
are your trying to decide on the design up front?

FWIW, if simple graph visualization is the only goal, using neato with
BGL's write_graphviz can do a "decent" ad-hoc rendering
https://stackoverflow.com/questions/37608482/how-to-display-grid-graph-using-boost/37609992#37609992
(though Graphviz should support multi-dimensional layouts technically, I
haven't tried with more than 2 dimensions)