Boost logo

Boost Users :

Subject: Re: [Boost-users] [BGL] IncidenceGraph and out_edges
From: chris (christian-baehnisch_at_[hidden])
Date: 2009-06-19 03:48:20


Hello,

> For an undirected graph there is, by definition/no source or target vertex
> implicit in the edge. And yet, source() and target() are still required for
> an undirected graph to behave properly with virtually every BGL algorithm.
> I used the term "esoteric" because this requires you to apply directional
> semantics to undirected edges, which is somewhat contradictory and imposes
> some interesting implementation requirements.
Yes, Im ok with this, you still want the incident vertives for a given edge
and there is no need to define extra functions for this for undirected graphs.

> The out_edges() requirement is a badly stated requirement that is trying to
> describe source/target requirements for undirected graphs, but do so in a
> way that precludes an implementation of graphs that contain loops. As such
> you should probably ignore the requirement.
>
> Explicit function for what?
A explicit function for traversing all vertices connected via an edge to a
fixed vertex. For example, looking at the implementation for depth_first_visit
you can find :

//ei an ei_end are out_edge_iterators
tie(ei, ei_end) = out_edges(u, g);
//...
while (ei != ei_end) {
        Vertex v = target(*ei, g);
//...
}
 
as you can see 'out_edges' together with 'target' is used to do this, i.e. for
traversing the so called vertex-ring of a given vertex. So why is there no
function called "vertex-vertex-Ring(vertex_descriptor u)" for this. Doing this
with "out_edges" and "target" means to change the implicit direction of an
undirected edge over and over again!

best regards, Chris


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net