Re: [Boost-users] [BGL] vertex, edge, and face properties of graph?

Subject: Re: [Boost-users] [BGL] vertex, edge, and face properties of graph?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-12-07 15:27:13

On Tue, 7 Dec 2010, Anders Wallin wrote:

> Hi All,
> I'm implementing a half-edge data structure(*) based on adjacency_list.
> I'm storing vertex and edge properties as bundled properties (classes
> VertProps and EdgeProps), and can read/write them conveniently with
> e.g.:
> graph[vertexDescriptor].vertProp_a = 2
> and
> x = graph[edgeDescriptor].edgeProp_b
> etc.
>
> I also need to keep track of the faces of the planar graph, and I'm
> wondering if there's a built-in way of doing this that would allow me
> to read/write face-properties via the same syntax:
> graph[faceDescriptor].faceProperty
>
> Could I derive my half-edge-class from adjacency_list, store and
> update a property-map for face-data, and provide a new overload for
> operator[] that takes a faceDescriptor type? or is there a better way?
> any examples available?
>
> thanks,
> AW
> (*) see e.g. http://www.holmes3d.net/graphics/dcel/

Have you looked at how CGAL (http://www.cgal.org/) handles this?  I 
believe they extend BGL to handle half-edges and such.  Faces are not a 
built-in construct in BGL, but there are some algorithms that work on 
planar graphs and that have representations of faces.  I'm not sure that 
you can attach properties to them, though, unless you can assign a 
canonical vertex or edge to each face and store properties there.

-- Jeremiah Willcock