Boost logo

Boost Users :

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

        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!

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