Boost logo

Boost Users :

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2006-03-09 10:51:42

On Mar 3, 2006, at 4:42 AM, Gavin Band wrote:
> However, I have some comments - forgive me if these have been made
> before or are just wishful thinking. As a mathematician, I tend to
> think of a directed graph as being also an undirected graph, just by
> forgetting the orientation of the edges. Then it should make sense to
> take connected_components() of any graph, directed or undirected, just
> by treating it as an undirected graph. However, I realise this
> conception may be naive in the context of the BGL, which has to deal
> with ways to store edges and their directions.

Mathematically, that is correct. In practice there are real issues
that make it a bit harder to do with most existing graph data
structures. For instance, when storing a directed graph, one only
stores the edge (u, v) as part of the vertex u; however, an
undirected graph needs to be able to access (u, v) from v as well.
That requires some extra storage and computation.

> Still - my graph seems to meet all of the formal requirements for
> connected_components, but to fail the (apparently informal)
> requirement
> that it be undirected (Under "Graph Concepts" in the documentation
> there
> is a discussion of directed vs. undirected graphs, but this stops
> short
> of a formal definition, unless I have misunderstood). Do think it is
> possible 1) to formalise the requirements for directed and undirected
> graphs, and

I'm not sure where to draw the formal/informal line. Concepts are by
nature very informal. The discussion of directedness should probably
mention explicitly that directed_category will be either convertible
to directed_tag (for directed graphs) or undirected_tag (for
undirected graphs).

> 2) to write a graph adaptor undirected_graph<> which turns a
> directed graph G into its corresponding undirected graph H?

It is doable. The adaptor would need to scan the graph to build in-
edge lists, then deal with flipping the source/target of the
underlying descriptors as necessary.

> Better yet,
> to use this (or some other method) to make the algorithms work for all
> graphs that they make (mathematical) sense for? Perhaps there are
> good
> reasons why this is not possible.

This is definitely possible. Connected components, for instance, will
have a different implementation for directed graphs as for undirected
graphs, but both would have the same interface. It's definitely
doable, and we would love to integrate that functionality into the
BGL. I'm not sure when or if we'll find the time to write it ourselves.


Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at