0

** 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

Aart Stuurman
  • 101
  • 4
  • 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. – Discrete lizard Feb 13 '18 at 13:00
  • 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. – Aart Stuurman Feb 13 '18 at 13:02
  • 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) – Aart Stuurman Feb 13 '18 at 13:03
  • 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. – Aart Stuurman Feb 13 '18 at 13:05
  • 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!

     – Discrete lizard Feb 13 '18 at 13:06
  • Alright. I was hoping to make a smaller question. Final goal: Say I have an undirected graph. I need to map paths onto this graph so that each node is touched exactly once. There may be any number of paths, and a lone node is alright(it's connected to nothing). This is already pretty hard, but I need to find -every- possible way to do this mapping. Every mapping will be compared with a scoring algorithm(we cannot use this scoring algorithm to make our problem simpler, sadly) – Aart Stuurman Feb 13 '18 at 13:11
  • Well I guess finding a single mapping is not hard, as you can just have only disconnected nodes. – Aart Stuurman Feb 13 '18 at 13:12
  • So my idea was: if I sortof traverse the graph starting at a node and find all paths including that node, I can then strip that node from the graph and go do the same for another node, until there are no nodes left in the graph. Hence the original question. – Aart Stuurman Feb 13 '18 at 13:17
  • Also, there will be some boundary conditions, like minimum path length. That will decrease valid results, but I feel like those are fairly easy to implement once a base algorithm exists. – Aart Stuurman Feb 13 '18 at 13:20
  • Please define your problem exactly. Is the path allowed to visit the same node twice? (E.g. should a square A-B-C-D-A with additional nodes and edges A-E and C-F include a path containing all 6 nodes?) And do you really need to list all paths individually? (There can be exponentially many.) – reinierpost Apr 15 '18 at 15:14
  • Are you sure there isn't any predictability in the scoring you can exploit? E.g. on a complete graph ($n$ nodes each connected to all other $n-1$), assuming that no node may be visited twice, are there no dependencies between the scores of the $\sum_{k=2}^n{k!}/2 + 1$ different paths? – reinierpost Apr 15 '18 at 17:27

1 Answers1

1

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

David Richerby
  • 81,689
  • 26
  • 141
  • 235
  • That would only find all paths -starting- with the first node. I also need paths where it is in the middle. – Aart Stuurman Feb 13 '18 at 22:09
  • 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? – David Richerby Feb 13 '18 at 23:49
  • 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.' – Aart Stuurman Feb 14 '18 at 11:57