[BGL] Shared nodes on path
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!
Hi,
As described, your problem is NP-hard, which means that if you were to find
a way to solve it in polynomial time in the number of vertices in the
graph, you'd also be able to solve a lot of other hard problems that
nobody's ever been able to solve in polynomial time. For example, given an
algorithm that solves your problem, you could use that algorithm to find
Hamiltonian paths in graphs: for any graph G with n vertices, just run the
algorithm on that graph and the path (u, x_0, ..., x_{n-2}, v), where the
x_i's are vertices not appearing in G (or, say, isolated vertices in G) and
u and v are two vertices from G. If the algorithm outputs a path, it's a
path of length n-1 and thus Hamiltonian.
In addition, there can easily be an exponential number of paths output by
such an algorithm, so even if you could find an efficient algorithm, once
you reach graphs with on the order of hundreds of nodes, there's no
guarantee that you have enough space to store the results or time to read
them.
Maybe there are some additional constraints on your actual problem or the
graphs you're dealing with that make it simpler than what you've described
above? If so, those would be good to know. If not, and you still want to
write an algorithm to do this, I'd suggest that you don't try to do
anything fancy with the BGL. Your best bet will just enumerating through
all candidate paths of the appropriate length and checking if the candidate
is an actual path in G.
-Aaron
On Thu, Feb 27, 2014 at 3:40 AM, Sensei
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!
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On 27/02/14 18:11, Aaron Windsor wrote:
Hi,
As described, your problem is NP-hard, which means that if you were to find a way to solve it in polynomial time in the number of vertices in the graph, you'd also be able to solve a lot of other hard problems that nobody's ever been able to solve in polynomial time. For example, given an algorithm that solves your problem, you could use that algorithm to find Hamiltonian paths in graphs: for any graph G with n vertices, just run the algorithm on that graph and the path (u, x_0, ..., x_{n-2}, v), where the x_i's are vertices not appearing in G (or, say, isolated vertices in G) and u and v are two vertices from G. If the algorithm outputs a path, it's a path of length n-1 and thus Hamiltonian. [...]
Maybe there are some additional constraints on your actual problem or the graphs you're dealing with that make it simpler than what you've described above? If so, those would be good to know. If not, and you still want to write an algorithm to do this, I'd suggest that you don't try to do anything fancy with the BGL. Your best bet will just enumerating through all candidate paths of the appropriate length and checking if the candidate is an actual path in G.
Hi Aaron, Unfortunately, you're right, it is NP-hard, however, I have some dimensions that can be relied on. The graph G can be very huge, but each node has *at most* four outgoing edges. The path P consists usually of ~50 nodes. A solution is either complete, i.e., the length of a solution is equal to the length of P, or the solution is not acceptable. The only thing I could do with BGL, then, is just to find all paths from one vertices to another, and check the length. Am I right? Thanks!
On Fri, Feb 28, 2014 at 4:49 AM, Sensei
On 27/02/14 18:11, Aaron Windsor wrote:
Hi,
As described, your problem is NP-hard, which means that if you were to find a way to solve it in polynomial time in the number of vertices in the graph, you'd also be able to solve a lot of other hard problems that nobody's ever been able to solve in polynomial time. For example, given an algorithm that solves your problem, you could use that algorithm to find Hamiltonian paths in graphs: for any graph G with n vertices, just run the algorithm on that graph and the path (u, x_0, ..., x_{n-2}, v), where the x_i's are vertices not appearing in G (or, say, isolated vertices in G) and u and v are two vertices from G. If the algorithm outputs a path, it's a path of length n-1 and thus Hamiltonian. [...]
Maybe there are some additional constraints on your actual problem or
the graphs you're dealing with that make it simpler than what you've described above? If so, those would be good to know. If not, and you still want to write an algorithm to do this, I'd suggest that you don't try to do anything fancy with the BGL. Your best bet will just enumerating through all candidate paths of the appropriate length and checking if the candidate is an actual path in G.
Hi Aaron,
Unfortunately, you're right, it is NP-hard, however, I have some dimensions that can be relied on.
The graph G can be very huge, but each node has *at most* four outgoing edges.
The path P consists usually of ~50 nodes.
A solution is either complete, i.e., the length of a solution is equal to the length of P, or the solution is not acceptable.
The only thing I could do with BGL, then, is just to find all paths from one vertices to another, and check the length. Am I right?
Yes, pretty much. Even then, you're going to have to do some bookkeeping to keep track of nodes you've already seen on a path and backtrack correctly - e.g., you used nodes a, b, and c on a path from x to y so when you find paths from y to something else you'll have to remove a, b, and c from the graph you explore. And even with nodes of degree 4, you've still got an NP-hard problem and the possibility of an exponential number of paths being output from your algorithm. -Aaron
On 2/28/14, 5:58pm, Aaron Windsor wrote:
Yes, pretty much. Even then, you're going to have to do some bookkeeping to keep track of nodes you've already seen on a path and backtrack correctly - e.g., you used nodes a, b, and c on a path from x to y so when you find paths from y to something else you'll have to remove a, b, and c from the graph you explore. And even with nodes of degree 4, you've still got an NP-hard problem and the possibility of an exponential number of paths being output from your algorithm.
Thanks Aaron, I appreciate your advice. I'll be very careful in exploring possible nodes. Cheers!
participants (2)
-
Aaron Windsor -
Sensei