[graph] Archetype's redundant members (Re: [graph]Direct Edge Access)
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. 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@osl.iu.edu> 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
Hi Jeremiah, On Wed, Mar 13, 2013 at 9:35 PM, Takatoshi Kondo <redboltz@gmail.com> 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@osl.iu.edu> 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
participants (1)
-
Takatoshi Kondo