- 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.) - 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

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@...

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 != 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> 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@...

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

---------------------------------------------------------------------- - --- In boost@y..., Jeremy Siek <jsiek@l...> wrote:
>

Yes, that's what I mean. Sorry for not writing concisely.

> 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.

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

Cheers, Hankel

> algorithms assume the above to be true for both directed and

> undirected graphs.

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

BidirectionalGraph, and added some text to the docs for adjacency_list.

Thanks for emailing about this!

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

----------------------------------------------------------------------