Opened 18 years ago

Last modified 11 years ago

#373 reopened Feature Requests (None)

LEDA graph adaptors for undirected graphs — at Version 2

Reported by: Douglas Gregor Owned by: Douglas Gregor
Milestone: To Be Determined Component: graph
Version: Boost 1.39.0 Severity: Not Applicable
Keywords: Cc: ich@…

Description (last modified by Douglas Gregor)

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 
(UGRAPH<...>).

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 
called.

Change History (2)

comment:1 by Marshall Clow, 15 years ago

Owner: changed from Douglas Gregor to doug_gregor
Severity: Optimization
Status: assignednew

Assigned to "doug_gregor" instead of nonexistent user "dgregor"

comment:2 by Douglas Gregor, 14 years ago

Description: modified (diff)
Owner: changed from doug_gregor to Douglas Gregor
Note: See TracTickets for help on using tickets.