Nonintersecting lattice paths with given start and endpoints

Question

A prominent topic in combinatorics is the enumeration of nonintersecting lattice paths subject to certain conditions. My goal is fairly simple: given starting points $(1,1), (2,1), \ldots, (k,1)$ and endpoints $(x_1, y_1), \ldots, (x_k, y_k)$, I would like to generate all families of $k$ nonintersecting lattice paths with these start/endpoints. By "lattice path," I mean a path in the plane whose steps are either $(1,0)$ or $(0,1)$.

My current method is hugely inefficient, because I first look at all $k$-tuples of paths with the prescribed start/endpoints, and then delete the ones in which the paths intersect. In order to find all paths between $(a,b)$ and $(x,y)$, I use FindPath and GridGraph as follows:

AllPaths[{{a_, b_}, {x_, y_}}] := 
  Map[{a - 1, b - 1} + # &, 
   Round[FindPath[GridGraph[{y - b + 1, x - a + 1}], 
      1, (x - a + 1) (y - b + 1), {x - a + y - b}, All] /. 
     Thread[Range[(x - a + 1) (y - b + 1)] -> 
       GraphEmbedding[GridGraph[{y - b + 1, x - a + 1}]]]], {2}];

By repeating this for each start/endpoint pair, and then taking Tuples with one path from each set, I get the set of all families of lattice paths --- which is humongous, so that deleting the intersecting families takes a long time.

Is there a more efficient way to construct families of nonintersecting lattice paths? Perhaps, for instance, by using Fold in some clever manner to restrict subsequent paths to the region bounded by their predecessor?

Answer 1

It is not clear to me what "nonintersecting" means, I interpreted this as "vertex disjoint paths".

Then, a possible solution goes as follows.

ClearAll[findpath,arrange,vertexdisjointpaths];

findpath[a_List,b_List,occupied_List]:=Module[{vx,vy,paths,steps},
If[AnyTrue[b-a,Negative],Return[{}]];
vy={0,1};
vx={1,0};
steps=Join[Table[vx,{(b-a)[[1]]}],Table[vy,{(b-a)[[2]]}]];
paths=Accumulate[Prepend[#,a]]&/@Permutations[steps];
paths=Select[paths,Not[IntersectingQ[occupied,#]]&]
];

arrange[List[{},otherpaths_]]:={otherpaths};

arrange[List[{{start_,goal_},waiting___},otherpaths_]]:=Module[{paths,occupied},
    occupied=Union@@otherpaths;
    paths=findpath[start,goal,occupied];
    Join@@Table[arrange[List[{waiting},Prepend[otherpaths,newpath]]],{newpath,paths}]
    ];

vertexdisjointpaths[fromto_List]:=arrange[{fromto,{}}];

Example:

fromto = {{{1,1}, {2,6}}, {{2,1}, {5,5}}, {{3,1}, {6,4}}, {{4,1}, {7,3}}};

Timing[ans = vertexdisjointpaths[fromto]; Length[ans]]

(* {0.097192, 350} *)

Short[ans, 10]

terminalpoints = 
  ListPlot[fromto, PlotStyle -> Directive[Black, PointSize[Large]], 
   AspectRatio -> Automatic, ImageSize -> Small, Axes -> None];

samples = RandomChoice[ans, 12];

Show[terminalpoints, ListLinePlot[#]] & /@ samples

Remarks:

fromto is a list {{s1,g1},{s2,g2},...,{sn,gn}} (n=0,1,2,.. ) where s_i and g_i are start and goal of i-th traveller.

findpath[a, b, occupied] will list up all possible paths of the form P = {a, p_1, ... , p_n, b} starting from point a and stopping at point b. Each path P should avoid "occupied": this means all the points in P cannot be a member of the list "occupied".

arrange[{fromto, otherpaths}] is a main recursive function. This routine tries to find a path for the 1-st traveller (using "findpath") assuming 2-nd, ..., n-th traveller's paths are already known and stored in "otherpaths". This assumtion is validated by recursively calling itself.