Re: [boost] [graph] Archetype's redundant members (Re: [graph]Direct Edge Access)

Subject: Re: [boost] [graph] Archetype's redundant members (Re: [graph]Direct Edge Access)
From: Takatoshi Kondo (redboltz_at_[hidden])
Date: 2013-03-14 01:04:35

Hi Jeremiah,

On Wed, Mar 13, 2013 at 9:35 PM, Takatoshi Kondo <redboltz_at_[hidden]> wrote:
> Hi Jeremiah,
>
> Thanks for your advice. I studied about archetypes.
> If I understood the minimal archetype requirements based on concepts
> correctly, some graph archetypes seems to have redundant members. In
> addition, vertex_list_graph_archetype::degree_size_type should inherit
> from incidence_graph_archetype.

Now, I understand that AdjacencyGraph Concept doesn't provide
out_degree(v, g). I removed it from adjacency_graph_archetype. Also I
removed degree_size_type. As the result of that, ambiguity of the
vertex_list_graph has been solved. I updated my patch.

>
> So, I wrote a patch. After applying the patch, all Boost.Graph tests
> passed. Could you check the patch?
>
> -- Takatoshi Kondo
>
> On Thu, Mar 7, 2013 at 4:41 PM, Jeremiah Willcock <jewillco_at_[hidden]> wrote:
>> On Thu, 7 Mar 2013, Takatoshi Kondo wrote:
>>
>>> Hi Jeremiah,
>>>
>>> Thank you for your reply. I'm relieved that I understand correctly. I
>>> come up with a related question.
>>> I think that general graph algorithm developers should test two
>>> different things.
>>>
>>> One is concepts. If function my_algo() required
>>> VertexAndEdgeListGraphConcept for the parameter g, it should be
>>> checked as follows:
>>>
>>> #include <boost/graph/graph_concepts.hpp>
>>>
>>> template <typename Graph>
>>> void my_algo(Graph g) {
>>>    BOOST_CONCEPT_ASSERT(( boost::VertexAndEdgeListGraphConcept<Graph> ));
>>>
>>>    boost::edge(0, 1, g); // accidental invalid use ... Line A
>>> }
>>>
>>> But this test cannot detect out of concepts functions usage as Line A
>>> if class Graph accidentally provide them.
>>> So, these problems should be detected the following test:
>>>
>>> void my_algo_test() {
>>>    typedef /* Only satisfies VertexAndListGraphConcept*/ Graph; // ...
>>> Line B
>>>    Graph g;
>>>    my_algo(g);
>>> }
>>>
>>> How do I define the type that is only satisfied specific concepts?
>>
>>
>> Those are called "archetypes" in the terminology of the Boost Concept Check
>> Library
>> (http://www.boost.org/doc/libs/1_53_0/libs/concept_check/concept_check.htm).
>> There is a set of them for Boost.Graph concepts in
>> <boost/graph/graph_archetypes.hpp>.  They do not appear to have
>> documentation, but example uses include most files with the name pattern
>> *_cc.cpp in libs/graph/test (e.g., bfs_cc.cpp).
>>
>>
>> -- Jeremiah Willcock
>>
>> _______________________________________________
>> Unsubscribe & other changes:
>> http://lists.boost.org/mailman/listinfo.cgi/boost
>
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

-- Takatoshi Kondo