On May 14, 2005, at 1:45 AM, Alex Helder wrote:

Hello:

If I have two graphs,

G = ( E, V) G' = ( E', V' )

what would be the most efficient way, using BGL, to determine whether G' is a subgraph of G?. I'm not interested in 'isomorphic' subgraphs.

Of course, if G' is a subset of G, then E' is a subset of E and V' is a subset of V.

I guess I could iterate over all the edge and vertex descriptors for both graphs ...

but I was wondering if there was another way. I'm not experienced with graph theory (if that isn't obvious by now!)

The big question you need to answer is: How can you match the vertices in V' to the vertices in V? Likewise, how can you match the edges in E' to the edges in E? It sounds like you're referring to the problem of finding a "subgraph isomorphism", which is trying to find a G' = (E', V') in G = (E, V) that is a subgraph. It's not a trivial problem, and we don't have an algorithm for it in the BGL (although we're interested in getting one!). Doug