Re: [Boost-users] boost.graph determining if one graph is a subgraph of another

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-05-18 21:34:05

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