Adapting boost::grid_graph vertex descriptors to Boost Geometry

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Adapting boost::grid_graph vertex descriptors to Boost Geometry

Boost - Dev mailing list
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


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

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

Boost - Dev mailing list
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)

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

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

Boost - Dev mailing list

> On Oct 29, 2017, at 3:26 PM, Seth via Boost <[hidden email]> wrote:
>
> Am I right in thinking you arlready have a working Proof Of Concept? Or
> are your trying to decide on the design up front?

I have verified that including boost/geometry/geometries/adapted/boost_array.hpp allows boost grid_graph vertex descriptors (which are implemented with boost array) to be, for example, constructed and manipulated as boost geometry points.

Adding this to boost (my suggestion was to do so in boost/geometry/geometries/adapted/grid_graph.hpp) would make it a supported (if optional) abstraction.  I feel that is a valuable enhancement, because otherwise there is no way to construct a perfectly meaningful vertex descriptor from the coordinates of the point it corresponds to without breaking the normal abstraction of vertex descriptors.

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

This has nothing to do with visualization.

Cheers,
Brook


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost