**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

**Next message:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #395: BGL graph types do not support allocators"**Previous message:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #372: adjacency_matrix should model BidirectionalGraph"**Maybe in reply to:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #373: LEDA graph adaptors for undirected graphs"**Next in thread:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #373: LEDA graph adaptors for undirected graphs"

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

**Next message:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #395: BGL graph types do not support allocators"**Previous message:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #372: adjacency_matrix should model BidirectionalGraph"**Maybe in reply to:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #373: LEDA graph adaptors for undirected graphs"**Next in thread:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #373: LEDA graph adaptors for undirected graphs"

*
This archive was generated by hypermail 2.1.7
: 2017-02-16 18:49:57 UTC
*