4
$\begingroup$

Given two vertices in a simple grid graph, how to find the path connecting them such that the combined neighbourhood of the vertices in the path is the smallest?

Consider this path between the vertices $1$ and $18$ in a $5\times5$ graph, enter image description here

The neighbourhood graph of all the vertices in the path would give,enter image description here

The combined neighbourhood has a total of $13$ vertices.

For another path,

enter image description here,

The combined neighbourhood would be,enter image description here,

with a total of $14$ vertices.

I want to find a path that minimizes the number of vertices in the combined neighbourhood.

Improve this question
$\endgroup$
4
  • $\begingroup$ +1 for the clear question. We can always assume the starting point has coordinates $(0,0)$. Up to reflection symmetries and so on, we can also assume that the target point has coordinates $(m,n)$ for some $0 \leq n \leq m$. (Your first picture would be $m=3$ and $n=2$.) Suppose I first move to $(n,n)$ using right-up-right-...-up, and then move right-right-...-right to $(m,n)$. Do you think that is optimal? If yes, and you can prove it, then done. If no, can you give an example where that is not optimal? $\endgroup$
    – user293787
    Jul 31, 2022 at 9:10
  • 1
    $\begingroup$ Counter Example; Path from 1 to 22 in the 5x5 grid. Path you defined would be (1,6,7,12,17,22) with combined neighbourhood 14. A more optimal path would be (1,6,11,16.21,22) with combined neighbourhood 11. $\endgroup$
    – Dotman
    Jul 31, 2022 at 9:28
  • 1
    $\begingroup$ Ok good, so boundary plays a role. Is your graph always a square or rectangle? Is the starting point always a corner point, or can start and stop be anywhere? $\endgroup$
    – user293787
    Jul 31, 2022 at 9:32
  • 1
    $\begingroup$ It can be square or rectangle; It can start and stop anywhere $\endgroup$
    – Dotman
    Jul 31, 2022 at 9:45

2 Answers 2

Reset to default
4
$\begingroup$

I think this question of OP might be more appropriate for a site with more graph theory people. Anyhow, the following seems to be a reasonable strategy: Given the graph G, try to construct an auxiliary graph auxG, with directed edges and weights, so that the available function FindShortestPath on auxG solves the problem that OP is asking on G. This will be useful if auxG can be constructed reasonably quickly and is of a similar size as G.

To see what I mean: If one moves right-right-right-right-... then one extends the combined neighborhood by 3 with each hop. If one moves right-up-right-up-... then on average one extends the not by 3+3 for each right-up-combination, but only by 5. So we could give weight 3 to each existing edge, and add diagonal edges with weight 5. In this case, auxG would have the same vertices as G, but more edges.

Because of the boundary, which is important in this problem, we have to do something similar near the boundary. I will not describe this in words and just drop the code:

(* original grid graph *)
n=10;
G=GridGraph[{n,n},VertexLabels->Automatic];
coords=Round[VertexCoordinates/.AbsoluteOptions[G,VertexCoordinates]];

(* neighborhood computations *)
nbh0[vertex_,dist_:1]:=VertexList[NeighborhoodGraph[G,vertex,dist]];
nbh0[vertex_,dist_,distmax_]:=Select[nbh0[vertex,dist],(Norm[coords[[vertex]]-coords[[#]],Infinity]<=distmax)&];
nbh[vertex_,x___]:=DeleteCases[nbh0[vertex,x],vertex];
sizenbh[vertices_]:=Length[DeleteDuplicates[Flatten[Map[nbh0,vertices]]]];

(* construct auxG *)
aux[from_,to_]:=sizenbh[FindShortestPath[G,from,to]]-sizenbh[{from}];
aux[from_]:=Map[{DirectedEdge[from,#],aux[from,#]}&,nbh[from,2,1]];
{auxedges,auxweights}=Transpose[Flatten[Map[aux,VertexList[G]],1]];
auxG=Graph[auxedges,EdgeWeight->auxweights,VertexLabels->Automatic];

(* find path *)
findPath[from_,to_]:=Flatten[Map[FindShortestPath[G,#[[1]],#[[2]]]&,
   Partition[FindShortestPath[auxG,from,to],2,1]]]//.{a___,b_,b_,c___}:>{a,b,c};

I stress that the construction of auxG is currently ad-hoc, I have not verified that it really generates the paths that OP wants.

Here is G:

enter image description here

Here is auxG. It has directed edges with weights. Away from the boundary, the weights are $3$ for horizontal or vertical hop, and $5$ for diagonal hop. Near the boundary it is a bit more complicated:

enter image description here

Examples: Corner to opposite corner:

p1 = findPath[1,100]
(* {1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100} *)

Let us compare with the diagonal path:

p2 = {1,11,12,22,23,33,34,44,45,55,56,66,67,77,78,88,89,99,100};

They have equal neighborhood size:

Map[sizenbh,{p1,p2}]
(* {36,36} *)

The first example of OP is essentially

p3 = findPath[1,33]
(* {1,11,12,22,23,33} *)

which is the path OP has given. Finally, consider two paths from the left boundary to the right boundary:

p4=findPath[3,93]
(* {3,2,1,11,21,31,41,51,61,71,81,91,92,93} *)

p5=findPath[4,94]
(* {4,14,24,34,44,54,64,74,84,94} *)

Note that p4 walks along the boundary, p5 does not.

Map[sizenbh,{p4,p5}]
(* {26,30} *)

This shows that p4 is indeed better than walking horizontally, which would have neighborhood size 30. And p5 is as good as walking along the boundary, which also has neighborhood size 30.

Again, I do not claim that this always produces the paths that OP wants, but it seems to go in the right direction. It is based on calling FindShortestPath once (on auxG) so should be reasonably efficient.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ This is very interesting and works really fast for large graphs. I've been looking for some counter examples but haven't been able to find any. $\endgroup$
    – Dotman
    Jul 31, 2022 at 15:51
  • $\begingroup$ There are plenty counterexamples. For 5x5 grid and {start,stop}=={2, 24} it returns {2, 3, 4, 5, 10, 15, 20, 19, 24} which has total neighborhood 17, but there are other six paths with total neighborhood 16, for example: {2, 3, 8, 9, 14, 15, 20, 25, 24}. $\endgroup$
    – azerbajdzan
    Jul 31, 2022 at 17:46
  • $\begingroup$ @azerbajdzan Please Quit[] and try again. For n=5, with findPath[2,24] I get {2,3,4,5,10,15,20,25,24} with size $16$. But perhaps you find another counterexample (I am quite sure there is one). $\endgroup$
    – user293787
    Jul 31, 2022 at 18:03
  • 2
    $\begingroup$ And this is definitely counterexample: For n=8 findPath[1, 47] returns {1, 2, 3, 4, 5, 6, 7, 8, 16, 24, 32, 40, 39, 47} which has total neighborhood 27, but there are two paths with 25: {{1,2,10,11,19,20,28,29,37,38,46,47}, {1,2,3,11,12,20,21,29,30,38,39,47}}. $\endgroup$
    – azerbajdzan
    Jul 31, 2022 at 18:23
  • 1
    $\begingroup$ The last example I gave does not work even if I use fresh kernel. $\endgroup$
    – azerbajdzan
    Jul 31, 2022 at 18:26
2
$\begingroup$

Minimal combined neighborhood is given by cn, in this case it is 15 for three different paths.

g = GridGraph[{5, 5}, VertexLabels -> Automatic];
{start, stop} = {7, 20};
paths = FindPath[g, start, stop, All, All];
len = Length /@ (AdjacencyList[g, #] & /@ paths);
cn = Min[len]
bestpaths = paths[[Flatten[Position[len, cn]]]];
HighlightGraph[g, PathGraph[#]] & /@ bestpaths
Clear[g, paths, len, bestpaths, start, stop, cn]

(* 15 *)

enter image description here

For {start,stop}={2,22}:

(* 12 *)

enter image description here

Improve this answer
$\endgroup$
6
  • $\begingroup$ Take {start,stop}={2,22}. Your code produces {2,7,12,17,22}, but {2,1,6,11,16,21,22} is better. $\endgroup$
    – user293787
    Jul 31, 2022 at 10:56
  • $\begingroup$ This code only considers paths with length equal to that of the shortest path. In general it wont hold $\endgroup$
    – Dotman
    Jul 31, 2022 at 11:02
  • 2
    $\begingroup$ @user293787: I modified my code, now it works correctly, but it is more or less a brute-force. $\endgroup$
    – azerbajdzan
    Jul 31, 2022 at 11:03
  • $\begingroup$ Hmmm...Its not even showing an output for 6x6 grid $\endgroup$
    – Dotman
    Jul 31, 2022 at 11:10
  • 1
    $\begingroup$ Limiting the length of the paths at 2n where n is the grid length gives good results $\endgroup$
    – Dotman
    Jul 31, 2022 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.