Boost logo

Boost :

From: (noreply_at_[hidden])
Date: 2005-03-22 10:33:34

Bugs item #1168420, was opened at 2005-03-22 10:33
Message generated for change (Tracker Item Submitted) made by Item Submitter
You can respond by visiting:

Category: graph
Group: None
Status: Open
Resolution: None
Priority: 5
Submitted By: Douglas Gregor (dgregor)
Assigned to: Douglas Gregor (dgregor)
Summary: LEDA graph adaptors for undirected graphs

Initial Comment:
The LEDA graph adaptors in the BGL seem to work properly for
directed graphs (the LEDA type GRAPH<...>), but there are no
corresponding adaptors for the undirected LEDA graph type

Undirected LEDA graphs follow a very different model than the
undirected graphs in the BGL, which will require some special
machinery. The LEDA type UGRAPH<...> is actually just a class
derived from GRAPH<...> that applies the "make_undirected()"
member function upon initialization. make_undirected() moves all of
the in-edges of each vertex to the out-edges list. This has several
unfortunate consequences:
  1) The in-degree of an undirected LEDA graph is always zero, even
when the out-degree is greater than zero. The in_edges list is
therefore empty.
  2) When traversing the list of out-edges for a vertex u, the edges
returned may have u as their target but not their source. This breaks
an important invariant in the BGL, which mandates that source(e,
g)==u if e came from out_edges(u, g). Similarly for in-edges.

Thus, an undirected LEDA graph adaptor will need to introduce
special adaptors for the out_edge_iterator and in_edge_iterator
types, which return a new edge_descriptor type for LEDA that can
swap the source and target of a LEDA edge as needed. Additionally,
graph-mutating operations (such as add_edge) may need to ensure
that the graph remains undirected, as if make_undirected() had been


You can respond by visiting:

This email is sponsored by: 2005 Windows Mobile Application Contest
Submit applications for Windows Mobile(tm)-based Pocket PCs or Smartphones
for the chance to win $25,000 and application distribution. Enter today at
Boost-bugs mailing list

Boost list run by bdawes at, gregod at, cpdaniel at, john at