Find All Possible Paths from a Single SourceNode to a Single TargetNode Without Visiting Old Paths

Hi All,

If I have node set nodeset=[nodeID x y] of size numberOfNodes x 3. I also have undirected path pathset=[PathID nodeID1 nodeID2] of size PathID x 3. I would like to find all possible paths from a single sourceNode to a single TargetNode. Visiting the previously travelled edge (path) is not allowed because there would be too much solutions. Visiting the previously travelled vertices are allowed.

Is there a function out there in Matlab that can help me do this: Example: AllPaths(nodeset, pathset, sourceNode, TargetNode) output: sets of vector containing PathID's that gives those possible path.

Your help much appreciated. Thank you in advance.

[Walter Roberson]

On undirected graphs, there are an infinite number of paths between any two nodes that are connected indirectly at all.

Someone asked a similar question a couple of months ago; they were trying to investigate centrality of social networks. I was not able to come up with an algorithm which did not come down to breadth-first search or depth-first search.

[Steven Lord]

If like the person Walter remembers who asked the similar question a couple months ago you're trying to investigate centrality of a graph or digraph, take a look at the centrality function.

Answer 1

[czeslaw]

Thank you all for the reply,

In response to Walter, for instance, if I have paths following a square figure with a diagonal in the middle, there will be 3 ways to go from point A to points C.

So if I input AllPaths(nodeset, pathset, A, C), the function that I looked for should output: 
1. A B C
2. A C
3. A D C

https://www.google.com/search?q=square+with+diagonal+in+middle&source=lnms&tbm=isch&sa=X&ved=0ahUKEwitqbmr4_3YAhWb8oMKHQW7DHYQ_AUICigB#imgrc=b7rkz9Th23mF7M:

I am not certain about that centrality function, would it be helpful for this kind of example. Any suggestions would be much appreciated. Thank you.

[Walter Roberson]

ABCADC is also a valid path.

[Steven Lord]

From the Google image search, I believe the node labeling the original poster refers to is:

x = [0 1 1 0];
y = [0 0 1 1];
g = graph({'A', 'A', 'A', 'B', 'C'}, ...
          {'B', 'C', 'D', 'C', 'D'});
plot(g, 'XData', x, 'YData', y, 'NodeLabelMode', 'auto')

ADAC, ABAC, and ADABC also all seem like valid paths ending up at C. What additional restrictions do you want to impose on a "possible path" that rules out those three cases?

[czeslaw]

Hi Steven, thanks for the reply.

Yes, I forgot to mention that travelling to any previously travelled path in any case should not be allowed. So in this case, to travel from A to C, only below options are the are the solutions.

1. A B C
2. A C
3. A D C

[Walter Roberson]

When you speak of previously traveled paths, that is a reference to edges, not to vertices. So if you had

     A -- B --- C
          /\
         /  \
         D--E

then using the previously traveled path rule, the A to C route would have to permit

ABC
ABDEBC
ADEDBC

Is that what you want? That each different way of traversing a loop should be counted?

If you instead had rule about not visiting any previously visited vertex then only ABC would be permitted in this sample diagram.

[czeslaw]

Hi Roberson, thanks for the reply.

Based on your figure, I can see that ABC and ABDEBC are allowed. I do not see how ADEDBC is possible here since there are no path between A D in that figure? In any case, Its okay to visit the previously visited vertex, but not allowed to visit the previously visited edge (connectivity between two vertices). The later case I imagine would result in extremely huge number of solutions. The former (able to visit the previously travelled vertex but not path) would have fewer solutions. But if both cases are difficult, not able to visit travelled vertices and paths (edges) would also work for me, in this case, only ABC is the solutions as you mentioned.

[Walter Roberson]

Sorry I meant ABEDBC