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

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-02-01 14:46:24

I'm guessing, but perhaps you are looking for some kind of guarantee
like the following for undirected graphs:

for (tie(ui, ui_end) = out_edges(u, g); ui != ui_end; ++ui)
  assert(source(*ui, g) == u);

This certainly should be made explicit. I know most of the BGL graph
algorithms assume the above to be true for both directed and undirected
graphs.

Cheers,
Jeremy

On Thu, 1 Feb 2001, Jeremy Siek wrote:

jsiek> Hi Hankel,
jsiek> 
jsiek> On Thu, 1 Feb 2001 hankel_o_fung_at_[hidden] wrote:
jsiek> hankel> 
jsiek> hankel> However, the meanings of e1==e2, source(e,g) and target(e,g) are
jsiek> hankel> ambiguous when e1, e2 are edge descriptors and g is undirected,
jsiek> hankel> even if g is not a multigraph:
jsiek> hankel> 
jsiek> hankel>   tie(e1,found) = edge(u, v, g);
jsiek> hankel>   tie(e2,found) = edge(v, u, g);
jsiek> hankel>   cout << source(e1,g) == source(e2,g) << endl;
jsiek> hankel>   cout << target(e1,g) == target(e2,g) << endl;
jsiek> hankel> 
jsiek> hankel> Currently, the BGL interface does not require both comparisons
jsiek> hankel> to return true/false. If we view logical equality as an indication
jsiek> hankel> of identical observable behaviours, then both equalities above
jsiek> hankel> should return true. If we want to traverse all vertices on a path
jsiek> hankel> delimited by two edge iterators, we may want "source" and "target"
jsiek> hankel> to depend on the direction we traverse (this seems to be the case
jsiek> hankel> in the current implementation of adjacency_list).
jsiek> 
jsiek> I'm not exactly sure as to your point: are you saying that the BGL
jsiek> definition and/or implementation of undirected edges is inconsistent, or
jsiek> are you asking for a change in the definition? In the various docs that
jsiek> you quoted, I don't see an inconsistency... if you disagree could you
jsiek> point it out more explicitly.
jsiek> 
jsiek> The definition of of equality for an undirected edge is that if e1 = (u,v)
jsiek> and e2 = (v,u) then e1 = e2. Now, the source and target functions merely
jsiek> return the first and second vertex of the pair respectively, so in this
jsiek> case source(e1) = u and source(e2) = v. Anotherwords, the statement e1 =
jsiek> e2 does not imply that source(e1) = source(e2). Instead it implies the
jsiek> more complicated statement:
jsiek>   (( source(e1) = source(e2) && target(e1) = target(e2) )
jsiek>    || ( source(e1) = target(e2) && target(e1) = source(e2) ))
jsiek> To the best of my knowledge, this definition is the standard one
jsiek> used in graph theory.
jsiek> 
jsiek> So are you asking for this definition to be changed? If so, exactly what
jsiek> new definition are you proposing? Or perhaps is there some sort of
jsiek> auxiliary functionality that you need to write some algorithm? If you
jsiek> could tell me more about the path traversal that you are trying to
jsiek> implement (show me code), perhaps I could suggest a way to implement it
jsiek> using the current interface/definition.
jsiek> 
jsiek> hankel> Contrast to source, target and ==, although BGL also does not
jsiek> hankel> states clearly the semantics of add_edge(u, v, g) and
jsiek> hankel> add_edge(u, v, ep, g) for a general undirected graph g, they are
jsiek> hankel> clearly defined in adjacency_list. Although I think it is natural
jsiek> hankel> for one to follow this semantics for a general undirected, it is
jsiek> hankel> still desirable to get it defined in the BGL requirements.
jsiek> 
jsiek> Thanks for pointing this out. I'll add to the documentation of
jsiek> MutableGraph::add_edge the same semantic requirements as adjacency_list.
jsiek> (that the requirement was not already there was an oversight).
jsiek> 
jsiek> Cheers,
jsiek> Jeremy
jsiek> 
jsiek> 
jsiek> ----------------------------------------------------------------------
jsiek>  Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
jsiek>  Ph.D. Candidate                  email: jsiek_at_[hidden]
jsiek>  Univ. of Notre Dame         work phone: [phone]
jsiek> ----------------------------------------------------------------------
jsiek> 
jsiek> 
jsiek> 
jsiek> 
jsiek> 
jsiek> 

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