
Boost Users : 
From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 20050518 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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net