0
$\begingroup$

** Edit: I just noticed my current algorithm is incorrect, as it only finds paths starting/ending at the given node. I'm trying to figure out a solution, but I'm a bit stuck.

Say I have an undirected graph. I would like to find all possible combinations of nodes that could be connected with a single path, that include a certain node.

--clarification: That is paths starting and ending at any node. Not just paths starting at the node in question.

Take this graph for example:

A----B
|    |
|    |
D----C

The solution for node A would be:

ABCD; example path A->B->C->D. Alternatively B->A->C->D or many others. As long as we have one, we're good.
ABC; example path C->B->A, etc.
ADC
AB
AD
A; 'path' from itself to itself

I understand this is a -very- hard problem with a lot of results. To make it simpler it is allowed to have some duplicates in the end result, but less would be better(this makes cyclic graphs a bit easier).

My current(naive) solution is as follows:

  1. Start at the node in question
  2. Note current path as possible path.
  3. If no possible connections, return.
  4. For each possible connection, go into recursion via [2].

See the following example. The problem with my algorithm is that a lot of duplicates are generated. Here the bottom two items in the example tree are the same solution. enter image description here

$\endgroup$
11
  • $\begingroup$ From your description, it seems this algorithm must (among others) find an Hamiltonian path, if one exists in the graph. As the problem of finding such a path is NP-hard, there won't be improvements to make your algorithm efficient. However, if all you want is to reduce or completely remove the investigation of duplicate solutions, there probably is an algorithm that achieves that. $\endgroup$
    – Discrete lizard
    Feb 13 '18 at 13:00
  • $\begingroup$ Yes indeed. If I can reduce the number of duplicates(and currently make the algorithm at all, as I figured out it's incorrect), that would be great. It is part of a bigger algorithm, and duplicates make it slower. $\endgroup$ Feb 13 '18 at 13:02
  • $\begingroup$ Also, I don't only need hamiltonian paths. Every node in the example tree is a valid solution. (The stated algorithm by chance works for this specific graph) $\endgroup$ Feb 13 '18 at 13:03
  • $\begingroup$ If you have some nodes, and it is possible to make a path that visits those nodes exactly once(and does not touch other nodes), then that set is part of the total solution. I need to find all of those sets. $\endgroup$ Feb 13 '18 at 13:05
  • $\begingroup$ Yes, you don't only need Hamiltonian paths, but since you must at least find them, this problem is NP-hard. You state this procedure is a part of a bigger algorithm. Could you perhaps say what that algorithm is or what the actual problem is you're trying to solve? It could be the case that there is a more efficient algorithm for your actual problem that doesn't use this subroutine, so this can be very relevant! $\endgroup$
    – Discrete lizard
    Feb 13 '18 at 13:06
1
$\begingroup$

Just use depth-first search. Each node you encounter in the search tree corresponds to a path from the source vertex.

$\endgroup$
3
  • $\begingroup$ That would only find all paths -starting- with the first node. I also need paths where it is in the middle. $\endgroup$ Feb 13 '18 at 22:09
  • $\begingroup$ You don't formally define the problem; you just give an example. Your example is apparently incorrect, since it only gives paths starting at the given node. So what was I supposed to do? $\endgroup$ Feb 13 '18 at 23:49
  • $\begingroup$ I appreciate your help, don't get me wrong. As I understand my question is not clear. However, the second sentence of my post states the problem. 'I would like to find all possible combinations of nodes that could be connected with a single path, that include a certain node.' $\endgroup$ Feb 14 '18 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.