Graph: Generic access to vertex/edge properties

From: Tarjei Knapstad (tarjeik_at_[hidden])
Date: 2002-08-08 08:09:51

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