Re: [boost] [Review] Boost Graphs Library (GGCL)

From: Dietmar Kuehl (dietmar_kuehl_at_[hidden])
Date: 2000-08-29 12:15:26

Hi,
Beman Dawes wrote:

> [It's OK if GGCL can't handle planar graphs today, but the docs should say
> so, and say what plans are for the future. If GGCL can handle planar graphs
> already, then explanations of the how's and why's are needed, with
> examples.]

Mention of planar graph is probably reasonable. Note, however, that planar
graphs
will probably use some rather special operations for specialized
algorithms: While
some algorithms can do with just knowing that the underlying graph is planer,
most
will need knowledge about certain planar properties like eg. dual edges.
Efficient
determination of such things requires rather special data structures like eg.
the
"quad edge" graph (each edge consists basically of four pointer to fully
represent
the undirectional edge and the dual edge).

> Background: I'm interested in planar graphs because they are the subspecies
> of graph used to represent topology when doing digital geography.  See
> http://www.census.gov/geo/www/tiger/index.html.
>
> The topology involved is concerned with 0-cells, 1-cells, and
> 2-cells.  These correspond to vertices, edges, and the polygons bounded by
> vertices and edges.  The computer representation is a planar graph.  A US
> nationwide street map, for example, is a planar graph with over 40 million
> edges.

Interesting... Due to bridges, the German national street map is not a planar
graph! It is, however, close to being planar. Depending on your needs, the
street map might even be a directed graph to cope with one ways.

I will try to look at GGCL this week, too.

Regards,
  Dietmar


_________________________________________________________
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com