[Boost-users] [BGL] Shared nodes on path

Subject: [Boost-users] [BGL] Shared nodes on path
From: Sensei (senseiwa_at_[hidden])
Date: 2014-02-27 06:40:34

Dear all,

I have a simple question about the most efficient way of finding shared 
nodes between a path and a graph. Let me be more explicit.

I have an oriented graph G, and a very simple graph P, which is actually 
a simple oriented path (n0 -> n1 -> ... -> nK). I need to find *all* the 
possible shared paths between P and G with the same length as P.

For instance, being

        P = n1 -> n2 -> n3 -> n4 -> n5 -> n6

we may find that the G and P share only two sub-paths

        n1 -> n2 -> n3
        n5 -> n6

I'd like to find all sub-graphs that connect the two paths, for instance 
having

        n1 -> n2 -> n3 -> n10 -> n5 -> n6
        n1 -> n2 -> n3 -> n42 -> n5 -> n6

with the constraint that the solution must be a path with the same 
length as P, therefore a solution as these

        n1 -> n2 -> n3 -> n9 -> n8 -> n5 -> n6
        n1 -> n2 -> n3 -> n5 -> n6

would not be acceptable.

I know I can do it manually, but I think a BGL-aware solution is quite 
better that a manual search :)

Thanks & Cheers!