BGL: what constitutes an undirected graph?

From: hankel_o_fung_at_[hidden]
Date: 2001-02-01 07:05:49

Hi folks,

What constitutes an undirected graph? In graph_theory_review.html,
it says:

 "In an undirected graph ... (u,v) and (v,u) are two ways of
  writing the same edge.

 "In an undirected graph edge (u,v) is incident on vertices u and v."

In graph_concepts.html :
 "When using undirected graphs just mentally disregard the
  directionality in the function names ...

 "If the undirected graph is a multigraph then (u,v) and (v,u)
  might be parallel edges. If the graph is not a multigraph then
  (u,v) and (v,u) must be the same edge."

In using_graph_algorithms.html :

And in Graph.html, it reads
 "boost::graph_traits<G>::edge_descriptor
  An edge descriptor corresponds to a unique edge (u,v) in a graph.
  An edge descriptor must be DefaultConstructible, Assignable, and
  EqualityComparable."

However, the meanings of e1==e2, source(e,g) and target(e,g) are
ambiguous when e1, e2 are edge descriptors and g is undirected,
even if g is not a multigraph:

  tie(e1,found) = edge(u, v, g);
  tie(e2,found) = edge(v, u, g);
  cout << source(e1,g) == source(e2,g) << endl;
  cout << target(e1,g) == target(e2,g) << endl;

Currently, the BGL interface does not require both comparisons
to return true/false. If we view logical equality as an indication
of identical observable behaviours, then both equalities above
should return true. If we want to traverse all vertices on a path
delimited by two edge iterators, we may want "source" and "target"
to depend on the direction we traverse (this seems to be the case
in the current implementation of adjacency_list).

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

Cheers, Hankel

(BTW, I find that the following two files are not "reachable"
from index.html: (1)using_boost_graph_library.html, (2)faq.html.
The first one seems to be a copy of using_adjacency_list.html.)