Algorithm for checking connectivity of a lattice graph in Rn

Two points are adjacent if they have n-1 equal coordinates and 1 coordinate that differ by 1. For example, (1,4,3,0) in R^4 is adjacent to 8 points (0,4,3,0), (2,4,3,0), (1,3,3,0), (1,5,3,0), (1,4,2,0), (1,4,4,0), (1,4,3,-1) and (1,4,3,1). Two points are connected if there is a sequence of points between them, every two consecutive points are adjacent.

Suppose the input is a set of lattice points in R^n. What is a fast algorithm to check if they are connected? I only need to determine the connectivity (no need to find connected components); suppose all the points are contained in a given cube say [0,k]^n if this helps.

Thanks.

[Dyuman Joshi]

Assuming you have the coordinates as numeric vectors or arrays -

p1=[1,4,3,0] ;
n=numel(p1); %dimension of the space
fun = @(x) isequal(sort(abs(p1-x)),[zeros(1,n-1) 1]);

This assumes that coordinates are checked correspondingly (x to x, y to y, z to z ....)

p2=[0,4,3,0];
fun(p2)

ans = logical
   1

p3=[2,4,3,0];
fun(p3)

ans = logical
   1

p4=[1,3,3,0];
fun(p4)

ans = logical
   1

%non-adjacent point
p5=[1,2,3,4];
fun(p5)

ans = logical
   0

You can also modify the function handle for checking for any two pairs as well

Fun = @(in1,in2) isequal(sort(abs(in1-in2)),[zeros(1,n-1) 1]);

[Haoran]

Thanks Dyuman. However your code only checks if two points are adjacent. My question is like I have a lot of points say A, B, C, D and A is adjacent to B, B adjacent to C, C adjacent to D hence they are all connected. Here A and D are not adjacent but connected.

[Dyuman Joshi]

How are the points stored? As numeric arrays corresponding to each dimension?

Please specify if otherwise.

[Haoran]

Say we have k points in Rn. Then it is a k * n matrix, each row gives the coordinates of one point.

Answer 1

[Dinesh]

Hi Haoran,

If you have 'k' input points and there are 'n' different dimensions for a single point, then you can model this problem as a graph and then try to apply any of the two well-known graph traversal algorithms. These algorithms are DFS (Depth First Search) and BFS (Breadth First Search) algorithms.

These points can be modelled as vertices and the connections between points as edges. In the worst case, these algorithms have a run time of O(k + y) where 'k' is the number of vertices and 'y' is the number of edges. In simple terms, it means that either of these algorithms in the worst case should traverse the number of times that equals to the sum of their number of vertices and their edges.

Please refer to this link for more information on DFS.

Make sure to use a 'visited' array to mark the previously visited vertices to avoid infinite loops.

Once the entire traversal is complete, you can just check if all the points are visited in the 'visited' array. If not, then it is clear that all the points are not connected together. In each step of the DFS, you have to check if two points are connected to each other which can take at most 'n' steps because there can be 'n' different dimensions for a single point.

The time complexity of the algorithm to implement this is O(n * (k + y)) where 'n' is the number of dimensions, 'k' is the number of points and 'y' is the number of vertices.

[Haoran]

Thank you for the DFS algorithm. Sorry I am new to graph problems with matlab, and my questions are kind of basic. Correct me if wrong. The DFS says:

We start the search at one vertex. After visiting a vertex, we further perform a DFS for each adjacent vertex that we haven't visited before. This way we visit all vertices that are reachable from the starting vertex.

So, first, I find all the edges and the adjacency matrix M.

Then, start at one vertex A1 and use M to find the adjacent vertices Ai, Aj, ... and mark them "visited".

Now, use M to find all vertices adjacent to Ai, and mark them "visited" if any one is unvisited. Then go from Aj?

I am afraid I am not correct, as the run time is probably more than O(k+y). It seems like O(k^2).

[Dinesh]

Yes @Haoran. In this question, the number of edges can be at most k^2 as a single point can be connected to all the other points and this is applicable for all the points. Please note that 'y' is the number of edges as I've mentioned and this can be equated to 'k^2' to simplify the time complexity further. So the time complexity would be O(n * (k+k^2)) which can be approximated to O(n * k^2). Please note that 'n' is very important to include here because every time we check if two points are connected, it takes 'n' steps in the worst case. No matter how we try to simplify, it is not possible to improve the time complexity of this problem in the worst case. So, DFS can still be used.

[Haoran]

Thank you very much. Now I understand the complexity.