Get all possible paths from one point of a square matrix to another with obstacles

Question

I have a square matrix (say 5x5) with a number of start and end points (say 3 sets):

The ultimate goal is to find the path for each pair of points so that there no path crosses another. In that simple example, there is probably more than one solution, but in real life, once you start adding more pairs of points, there will be a unique solution that fills the entire matrix so that no square is left unoccupied.

My first step however, is to find all possible paths from one start point to its corresponding end point, for each pair of points, so that I can then discard all those where a path crosses another. If possible, I would like to do this without having to resort to graph theory because 1) I know nothing about it and 2) it doesn't appear to be implemented in Octave.

I have done a fair bit of research on that found the following function from GitHub which does almost exactly what I am trying to achieve, but does rely on graph theory:

function pth = pathbetweennodes(adj, src, snk, verbose)
%PATHBETWEENNODES Return all paths between two nodes of a graph
%
% pth = pathbetweennodes(adj, src, snk)
% pth = pathbetweennodes(adj, src, snk, vflag)
%
%
% This function returns all simple paths (i.e. no cycles) between two nodes
% in a graph.  Not sure this is the most efficient algorithm, but it seems
% to work quickly for small graphs, and isn't too terrible for graphs with
% ~50 nodes.
%
% Input variables:
%
%   adj:    adjacency matrix
%
%   src:    index of starting node
%
%   snk:    index of target node
%
%   vflag:  logical scalar for verbose mode.  If true, prints paths to
%           screen as it traverses them (can be useful for larger,
%           time-consuming graphs). [false]
%
% Output variables:
%
%   pth:    cell array, with each cell holding the indices of a unique path
%           of nodes from src to snk.

% Copyright 2014 Kelly Kearney

My problem is trying to compute the adjacency matrix. Not being familiar with graph theory, I kind of understand the concept of an adjacency matrix but am at a loss for actually generating the said matrix.

If I treat each pair separately and consider the other occupied squares as "off-limits", I would have 25 - 4 = 21 nodes for each scenario, and on paper I can write down the edges manually, but I don't know how to code this? Can anybody help?

If we use the example above and order the nodes row-wise, we would have something like this considering the blue pair of points, the goal being to go from node 1 to node 17 (or vice-versa, there is no directionality involved):

 1  2  3  4  5 
    6     7  8
 9 10 11 12 13
14 15 16 17
18    19 20 21

The edges are the valid moves (vertical or horizontal, no diagonal) so something like:

1 - 2
2 - 1
2 - 3
2 - 6
3 - 2
3 - 4
etc...

How do you go from this to some code?

Of course, if there is a better way to approach the problem, I'm open to any suggestions. In terms of the scale of the problem, it can go up to a 10x10 grid with 10 pairs of start/end points, so that's 82 nodes.

Answer 1

An adjacency matrix is a matrix for which element adj(n,:) will tell you with booleans (or path lengths) if node n is adjacent to all other elements. e.g. in your case adj(14,:) is all zeroes except for adj(14,9), adj(14,15) and adj(14,18).

You are starting from a good yet slightly off initial though. A node without connections is still a node in your system. That will make your life much easier!

Your initial matrix is simply node_ids=1:25, or if you want node_ids=reshape(1:25,5,5). The nodes that you don't want to visit can be described as nodes that are not adjacent to anything. So, the way to program this is to first create and adjacency matrix for a 5x5 (or whatever size) mesh, and then delete all paths that you do not want, e.g. adj(:,6)=0 (for all nodes, make sure that they are not adjacent to node 6 (note, node is the first red circle in your example)).

To build this matrix you just need to know which nodes are adjacent, but for a cube, finding an equation to give you its adjacents nodes is easy (or just check node_ids(ind2sub(your_node)+[0 1]) and other combinations)