Re: [boost] BGL: what constitutes an undirected graph?

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-02-01 12:45:07

Hi Hankel,

On Thu, 1 Feb 2001 hankel_o_fung_at_[hidden] wrote:
hankel> 
hankel> However, the meanings of e1==e2, source(e,g) and target(e,g) are
hankel> ambiguous when e1, e2 are edge descriptors and g is undirected,
hankel> even if g is not a multigraph:
hankel> 
hankel>   tie(e1,found) = edge(u, v, g);
hankel>   tie(e2,found) = edge(v, u, g);
hankel>   cout << source(e1,g) == source(e2,g) << endl;
hankel>   cout << target(e1,g) == target(e2,g) << endl;
hankel> 
hankel> Currently, the BGL interface does not require both comparisons
hankel> to return true/false. If we view logical equality as an indication
hankel> of identical observable behaviours, then both equalities above
hankel> should return true. If we want to traverse all vertices on a path
hankel> delimited by two edge iterators, we may want "source" and "target"
hankel> to depend on the direction we traverse (this seems to be the case
hankel> in the current implementation of adjacency_list).

I'm not exactly sure as to your point: are you saying that the BGL
definition and/or implementation of undirected edges is inconsistent, or
are you asking for a change in the definition? In the various docs that
you quoted, I don't see an inconsistency... if you disagree could you
point it out more explicitly.

The definition of of equality for an undirected edge is that if e1 = (u,v)
and e2 = (v,u) then e1 = e2. Now, the source and target functions merely
return the first and second vertex of the pair respectively, so in this
case source(e1) = u and source(e2) = v. Anotherwords, the statement e1 =
e2 does not imply that source(e1) = source(e2). Instead it implies the
more complicated statement:
  (( source(e1) = source(e2) && target(e1) = target(e2) )
   || ( source(e1) = target(e2) && target(e1) = source(e2) ))
To the best of my knowledge, this definition is the standard one
used in graph theory.

So are you asking for this definition to be changed? If so, exactly what
new definition are you proposing? Or perhaps is there some sort of
auxiliary functionality that you need to write some algorithm? If you
could tell me more about the path traversal that you are trying to
implement (show me code), perhaps I could suggest a way to implement it
using the current interface/definition.

hankel> Contrast to source, target and ==, although BGL also does not
hankel> states clearly the semantics of add_edge(u, v, g) and
hankel> add_edge(u, v, ep, g) for a general undirected graph g, they are
hankel> clearly defined in adjacency_list. Although I think it is natural
hankel> for one to follow this semantics for a general undirected, it is
hankel> still desirable to get it defined in the BGL requirements.

Thanks for pointing this out. I'll add to the documentation of
MutableGraph::add_edge the same semantic requirements as adjacency_list.
(that the requirement was not already there was an oversight).

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate                  email: jsiek_at_[hidden]
 Univ. of Notre Dame         work phone: [phone]
----------------------------------------------------------------------