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

4 views (last 30 days)
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.
  2 Comments
Walter Roberson
Walter Roberson on 29 Jan 2018
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
Steven Lord on 29 Jan 2018
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.

Sign in to comment.

Answers (1)

czeslaw
czeslaw on 29 Jan 2018
Edited: Walter Roberson on 29 Jan 2018
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
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.
  6 Comments
czeslaw
czeslaw on 29 Jan 2018
Edited: czeslaw on 29 Jan 2018
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.

Sign in to comment.

Categories

Find more on Graph and Network Algorithms in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!