Graph: Generic access to vertex/edge properties
Hi. I'm currently trying to implement a generic pattern matching (aka subgraph isomorphism) algorithm for use with the Boost Graph Library. My first-attempt function signature looks like this (comments included for further description of what I'm attempting) //! Seeks to find matches of the graph \a g2 in the graph \a g1. /*! This is called "graph pattern matching", or "subgraph homomorphism/isomorphism". The results are returned in a std::list of std::maps where the maps' key is the node_descriptor in \a g2 and the values are the corresponding node_descriptors in \a g1. The size of the returned list represents the number of matches. If \a properties is true it means that all vertex and edge properties must be equal in both structures for a match to be found. Otherwise, only the graph structure itself will be checked. \sa positioned_pattern_match */ template <class Graph> std::list< std::map<typename graph_traits<Graph>::vertex_descriptor, typename graph_traits<Graph>::vertex_descriptor> > pattern_match(const Graph& g1, const Graph& g2, bool properties = true); For the case where the 'properties' switch is false I have everything I need, but if 'properties' is true I'm a bit unsure on how to proceed. The problem, as I see it, is to do a generic consecutive access of all the properties of the current vertex/edge being checked and see if they're equal in both 'g1' and 'g2'. Could anyone provide me a solution/clue on how to solve this problem in a generic way so that the algorithm can be used for any graph? Regards, -- Tarjei Knapstad
Hi Tarjei, One way is to pass in a comparison functor to your algorithm. (One my to-do list is a change the implementation of internal properties to use a heterogeneous associative list class that would know how to check for equality, etc.) On 8 Aug 2002, Tarjei Knapstad wrote: tarjei> tarjei> The problem, as I see it, is to do a generic consecutive access of all tarjei> the properties of the current vertex/edge being checked and see if tarjei> they're equal in both 'g1' and 'g2'. tarjei> ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
--- In Boost-Users@y..., Jeremy Siek <jsiek@c...> wrote: Hi Jeremy, Thanks for your reply.
Hi Tarjei,
One way is to pass in a comparison functor to your algorithm.
This sprang to mind shortly after sending my original post :) And actually, this does make the algorithm more general. Not being able to pass a comparison functor requires that all properties are equality comparable, and that all properties are must be checked. You may have pointers to objects stored as properties, and would like to check if the objects pointed to are equal and not if they point to the same object. You may also want to omit checking graph coloring and such properties. So I'll go with the comp. functor solution (allthough I'll need two, one for vertices and one for edges), but still there should be a default like in STL algorithms like sort(), which compares all properties by using operator=().
(One my to-do list is a change the implementation of internal properties to use a heterogeneous associative list class that would know how to check for equality, etc.)
That sounds nice :) <snip> Cheers, Tarjei Knapstad
participants (3)
-
Jeremy Siek -
Tarjei Knapstad -
tarjeiknaps