Re: [Boost-bugs] [Boost C++ Libraries] #373: LEDA graph adaptors for undirected graphs

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #373: LEDA graph adaptors for undirected graphs
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2008-04-29 18:31:59

#373: LEDA graph adaptors for undirected graphs
-------------------------------+--------------------------------------------
  Reporter:  dgregor           |       Owner:  dgregor     
      Type:  Feature Requests  |      Status:  new         
 Milestone:                    |   Component:  graph       
   Version:  None              |    Severity:  Optimization
Resolution:  None              |    Keywords:              
-------------------------------+--------------------------------------------
Changes (by dgregor):

  * owner:  doug_gregor => dgregor

Old description:

> {{{
> 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.
> }}}

New description:

 {{{
 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.
 }}}

-- 
Ticket URL: <http://svn.boost.org/trac/boost/ticket/373#comment:2>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.