Re: [Boost-users] BGL -- adjacency_matrix, graph concepts

Subject: Re: [Boost-users] BGL -- adjacency_matrix, graph concepts
From: Raymond Wan (r.wan_at_[hidden])
Date: 2009-10-06 10:41:24

Hi Andrew,

Andrew Sutton wrote:
>> template <class EdgeIterator> adjacency_list(EdgeIterator first,
>> EdgeIterator last,
>> 
>> template <typename EdgeIterator> adjacency_matrix(EdgeIterator
>> first,
>> 
>> It's not the same because of "typename"?  As a toy example, I've
>> taken the MST example and have modified it a lot to get this:
>> 
> 
> They're basically the same constructor. The extra int (m) in
> adjacency_list is only used to disambiguate the signature from
> another constructor. The value is effectively ignored, IIRC.

I see -- then the fact that one says "class" and the other says
"typename" is merely a typo?  Or is there a difference, but based on my
elementary level, that difference is unimportant?  (I'm guessing the
latter...)

>> The 5th line from the end is what is causing me problems.  It
>> seemed to work with an adjacency_list.  (I'd also would like to add
>> weights, but I guess add_edge could support that...I just think
>> that this way is faster based on the "Quick Tour of the BGL" page
>> in the docs.)
> 
> You need to be more specific when you say, "causing me problems". If
> there's a compiler error, what it is it? Is there a runtime error?

Sorry for not being clear!  I thought what i did was "so" wrong, that my 
mistake was obvious (i.e., that constructor does not exist, etc.).  The 
error I'm getting is a compiler error (below).

Is the error telling me (from "candidates are...") that it only works 
with directed graphs?  (Sorry for the strange characters...my g++ is 
printing them out and I don't know why...it looks like I'm using 
colorgcc in the wrong terminal, but I don't think that's the case.)

-----
sample.cpp: In function âint main()â:

sample.cpp:34: error: no matching function for call to
âboost::adjacency_matrix<boost::undirectedS, boost::no_property,
boost::property<boost::edge_weight_t, int, boost::no_property>,
boost::no_property, std::allocator<bool> >::adjacency_matrix(main()::E
[7], main()::E*, int [7], const int&)â

/usr/local/boost_1_39_0/include/boost/graph/adjacency_matrix.hpp:601:
note: candidates are: boost::adjacency_matrix<Directed, VertexProperty,
EdgeProperty, GraphProperty, Allocator>::adjacency_matrix(typename
std::vector<typename boost::mpl::if_<typename
boost::has_property<typename
boost::detail::retag_property_list<boost::edge_bundle_t,
EdgeProperty>::type>::type, std::pair<bool, typename
boost::detail::retag_property_list<boost::edge_bundle_t,
EdgeProperty>::type>, char>::type, typename Allocator::rebind<typename
boost::mpl::if_<typename boost::has_property<typename
boost::detail::retag_property_list<boost::edge_bundle_t,
EdgeProperty>::type>::type, std::pair<bool, typename
boost::detail::retag_property_list<boost::edge_bundle_t,
EdgeProperty>::type>, char>::type>::other>::size_type) [with Directed =
boost::undirectedS, VertexProperty = boost::no_property, EdgeProperty =
boost::property<boost::edge_weight_t, int, boost::no_property>,
GraphProperty = boost::no_property, Allocator = std::allocator<bool>]

/usr/local/boost_1_39_0/include/boost/graph/adjacency_matrix.hpp:474:
note:                 boost::adjacency_matrix<boost::undirectedS,
boost::no_property, boost::property<boost::edge_weight_t, int,
boost::no_property>, boost::no_property, std::allocator<bool> >
::adjacency_matrix(const boost::adjacency_matrix<boost::undirectedS,
boost::no_property, boost::property<boost::edge_weight_t, int,
boost::no_property>, boost::no_property, std::allocator<bool> >&)
-----

>> adjacency_matrix.cpp . Other than the pros/cons of adjacency
>> matrices and lists, is there something wrong with adjacency
>> matrices; any reason for its absence in the examples directory?
> They don't seem to be used as frequently, so don't get as much
> attention.

I see.  Is that the only reason?  I was worried that maybe there's a 
problem with adjacency_matrix (hence the compiler errors I was getting 
above).

>> One final question -- in the documentation, it lists various graph
>> concepts 
>> (http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/graph_concepts.html)
>>  such as BidirectionalGraph, VertexAndEdgeListGraph,
>> AdjacencyMatrix, etc. Are these concepts relevant to BGL or only in
>> a general sense? What I mean is what is their relationship with
>> adjacency_list and adjacency_matrix?  Any pointers would be
>> appreciated...
> These concepts describe the interface (functions, types, and
> semantics) used to interact with graphs by the generic algorithms in
> the BGL. The adjacency_list and adjacency_matrix are data structures
> that conform to the requirements of the concepts.

I see.  In other words, BidirectionalGraph, etc. are "abstract views" 
and there is no way one would call a "BidirectionalGraph constructor" -- 
there's no such thing?  For example, in the documentation, one might say 
that a problem requires a "BidirectionalGraph".  This is short-hand for 
both the authors and the readers that the problem requires some data 
structure, types, etc.?

Thank you for your help!

Ray