Boost logo

Boost Users :

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!).


Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at