## BGL: what constitutes an undirected graph?

Expand Messages
• 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
Message 1 of 5 , Feb 1, 2001
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 :

"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.)
• Hi Hankel, On Thu, 1 Feb 2001 hankel_o_fung@yahoo.com wrote: hankel hankel However, the meanings of e1==e2, source(e,g) and target(e,g) are hankel ambiguous
Message 2 of 5 , Feb 1, 2001
Hi Hankel,

On Thu, 1 Feb 2001 hankel_o_fung@... 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
(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@...
Univ. of Notre Dame work phone: (219) 631-3906
----------------------------------------------------------------------
• 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 !=
Message 3 of 5 , Feb 1, 2001
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@... 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> (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@...
jsiek> Univ. of Notre Dame work phone: (219) 631-3906
jsiek> ----------------------------------------------------------------------
jsiek>
jsiek>
jsiek>
jsiek>
jsiek>
jsiek>

----------------------------------------------------------------------
Jeremy Siek www: http://www.lsc.nd.edu/~jsiek/
Ph.D. Candidate email: jsiek@...
Univ. of Notre Dame work phone: (219) 631-3906
----------------------------------------------------------------------
• ... Yes, that s what I mean. Sorry for not writing concisely. ... So, what is the current status? Is the above property of out_edges already a requirement
Message 4 of 5 , Feb 1, 2001
--- In boost@y..., Jeremy Siek <jsiek@l...> wrote:
>
> 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);
>
Yes, that's what I mean. Sorry for not writing concisely.

> This certainly should be made explicit.
So, what is the current status? Is the above property of out_edges
already a requirement (though undocumented) of BGL? Or is it just
a coincidence that the current implementations in BGL assume the
above?

> I know most of the BGL graph
> algorithms assume the above to be true for both directed and
> undirected graphs.

Cheers, Hankel
• On Fri, 2 Feb 2001 hankel_o_fung@yahoo.com wrote: hankel --- In boost@y..., Jeremy Siek wrote: hankel hankel I m guessing, but perhaps you
Message 5 of 5 , Feb 1, 2001
On Fri, 2 Feb 2001 hankel_o_fung@... wrote:
hankel> --- In boost@y..., Jeremy Siek <jsiek@l...> wrote:
hankel> >
hankel> > I'm guessing, but perhaps you are looking for some kind of guarantee
hankel> > like the following for undirected graphs:
hankel> >
hankel> > for (tie(ui, ui_end) = out_edges(u, g); ui != ui_end; ++ui)
hankel> > assert(source(*ui, g) == u);
hankel> >
hankel> Yes, that's what I mean. Sorry for not writing concisely.
hankel>
hankel> > This certainly should be made explicit.
hankel> So, what is the current status? Is the above property of out_edges
hankel> already a requirement (though undocumented) of BGL? Or is it just
hankel> a coincidence that the current implementations in BGL assume the
hankel> above?

I would have to say that the current status is that the above property is
already a requirement, and that this qualifies as a documentation bug.
I've already updated the descriptions in IncidenceGraph and