[boost] Graph, Property "patches" and remarks from HP

From: David Abrahams (dave_at_[hidden])
Date: 2003-02-17 00:58:19

Someone at HP has been testing against boost and has found a bug and
some workarounds for parts of the graph library.  The message he sent
me is enclosed. His "question about the validity of the boost sources"
is clearly the result of a misunderstanding on the part of whoever is
implementing two-phase lookup over at HP, but I think the "patches"
could be safely applied before we branch for release.

Unfortunately what he sent me was a 1.3 megabyte uncompressed
attachment, but the actual proposed changes are quite small; I've
mercifully removed it from the message and instead posted it
(compressed) at
http://groups.yahoo.com/group/boost/files/graph.cpp.bz2.

I'm sorry for the poor presentation of the changes but I'm on vacation
at the moment and I don't feel like trying to turn this behemoth into
an actual patchset in a hurry.

-Dave


attached mail follows:

Hi David,

> Hi Vikram,
> The "sane-testing" branch has now been integrated into the main trunk,
> so at this point the best way for you to get a snapshot is:
>
>   cvs -d:pserver:anonymous_at_[hidden]:/cvsroot/boost login
>   cvs -z3
> -d:pserver:anonymous_at_[hidden]:/cvsroot/boost co boost
>
> Please let me know if this gives you any problems, and I'll assemble a
> snapshot for you.  Testing instructions haven't changed.

I was able to download the cvs snapshot and do a build with our development
compiler. Thanx much for your help. I've few questions:

When building graph library (graph/test/graph.cpp)

1) "boost/graph/copy.hpp" line 440
# Undeclared variable 'g'.
     g, vertex_index), orig2copy[0])),
     ^
I think this should be g_in?

2) I've found few workarounds to the problems that are encountered in
compiling graph.cpp. I'd appreciate if these could be incorporated in the
sources to enable aCC users to use this library. I'll inform you as when
these bugs are fixed.

2.1) libs/graph/test/graph_type.hpp

#line 136
 Graph g;
 typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
 typedef boost::graph_traits<Graph>::edge_descriptor Edge;
...

It helps aCC if the instantiation of Graph is moved after the typedefs as:

 typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
 typedef boost::graph_traits<Graph>::edge_descriptor Edge;
 Graph g;

This workaround is related to the comments after <=======>

2.2) boost/pending/property.hpp

near #line 67
enum { match = detail::same_property<Tag1,Tag2>::value };

It helps aCC if this enum could be changed to the equivalent construct as
follows:

const int match = detail::same_property<Tag1,Tag2>::value;

I was able to get graph.cpp to compile with these changes. Let me know
what's your take on these.

<================================>

I also have a question about the validity of boost sources.

In file graph/test/graph_type.hpp about #line 136
 typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;

This implies that graph_traits<Graph> has a type[def] vertex_descriptor in
it.
>From the definition of template class graph_traits, I find

boost/graph/graph_traits.hpp #line 36

 template <typename G>
 struct graph_traits {
   typedef typename G::vertex_descriptor vertex_descriptor;
   ...
 };

This further implies that G => Graph has a type[def] for vertex_descriptor.

>From graph/test/graph_type.hpp about line 2
typedef boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS,
boost::property<vertex_id_t, std::size_t>, boost::property<edge_id_t,
std::size_t> > Graph;

So, looking up class adjacency_list (boost/graph/adjacency_list.hpp about
line 301), I couldn't find a typedef for vertex_descriptor in it. Although,
it's possible to get to such a typdef from its base class, but according to
C++ standard this is not legal.

14.6.2 - Dependent names [temp.dep]

-3- In the definition of a class template or a member of a class template,
if a base class of the class template depends on a template-parameter, the
base class scope is not examined during unqualified name lookup either at
the point of definition of the class template or member or during an
instantiation of the class template or member. [Example:

typedef double A;
template<class T> class B {
        typedef int A;
};
template<class T> struct X : B<T> {
        A a;                    //   a  has type  double
};

The type name A in the definition of X<T> binds to the typedef name defined
in the global namespace scope, not to the typedef name defined in the base
class B<T>. ]
...

-thanx
Vikram
P.S. I've attached the preprocessed file with the changes (and line numbers
mentioned above also correspond). I've made changes in the file under
#ifdefs as (1)VIKSourceWork, (2.1)VIKGraphWork and (2.2) VIKEnum.


-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com