# How to implement a Von Neumann neighborhood algorithm to random matrices/grids?

I'm trying to generate square grid templates to drill holes on a plate for a fragmentation experiment. The first part of the experiment I used the program below to generate uniformly random sites for drilling.

gridTemplate[msize_, ndrill_] := Module[{l},
(* msize is the size of the grid's square matrix
ndrill is the number of holes made in the plate *)
l = {};
While[Length[l] < ndrill,
l = Append[l, RandomInteger[{1, msize}, 2]] // DeleteDuplicates];
Grid[SparseArray[
MapThread[# -> Item[Style[#2, White], Background -> Gray] &, {l,
Range[ndrill]}], {msize, msize}], Frame -> All]]


It generates a grid like this: Now, I need to implement a algorithm that randomly chooses the initial drilling site on the grid and subsequent sites should be randomly picked only in the Von Neumann neighborhood of the sites that already have been selected. I really have no clue on how to implement this, I've tried to understand how it was implemented in this thread (mathematica.stackexchange.com/q/39793/47756), but it was beyond my current understanding.

Also is there an easy way to attribute numbers to each site and then generate a list of the positions (number attributed) of the drilled sites?

Does this what you want? I use a rectangular GridGraph in order to compute Neumann neighborhoods with VertexComponent.

m = 10;
n = 20;
holecount = 200;
G = GridGraph[{m, n}];
holes = {RandomInteger[m n]};
Do[
neumannneigborhood = Complement[VertexComponent[G, holes, 1], holes];
holes = Join[holes, {RandomChoice[neumannneigborhood]}],
{holecount-1}];
pts = Flatten[Outer[List, Range[n], Range[m]], 1];
holecoords = pts[[holes]];


Now holes contains the list of vertex indices in the order of drilling. holecoords contains the according $x$-$y$ coordinates in the plane.

Some visualization:

Manipulate[
HighlightGraph[G, holes[[1 ;; k]],
VertexSize -> .75,
PlotRange -> {{-1, n + 2}, {-1, m + 2}}],
{k, 1, holecount, 1}]

• Thanks for your help @HenrikSchumacher, the program does more or less what I have in mind, but I'll need to better understand it and to think about is on a way that is not dependent on Manipulate, since I have to generate around 200 templates to drill, and not only I'm not the only one in the lab drilling them, but the only person who programs in the Wolfram Language (though not yet very proficient) and owns a Mathematica license. Apr 17, 2018 at 14:59
• nicholas80, you're welcome. The part about manipulate is merely for visualization. The drilling is done in the Do loop. I added a way to extract the list holecoords  $x$-y\$-coodinates of the holes (in the order they were drilled). Hope that helps. Apr 17, 2018 at 15:13
• thanks again for your help help and ultra fast reply. I thought of using a While loop using the holecount as the condition, but your solution using just the Do loop is more elegant (and simpler too). Your suggestion of using networks instead of the grids is interesting, since one of my hypothesis involves treating the material as a network of sites, and the loss of material due to perforation as removing vertexes, this way I can use shortest path measures to study the fragmentation. Apr 17, 2018 at 15:40
• Hi @Henrik, it may be an idiot question, but how do I perform the inverse operation of what you did in holecoords, i.e. transforming list of x-y coordinates in a vertex list? Jul 23, 2018 at 14:28
• Not an idiot question at all. You might use Nearest for that: nf = Nearest[(pts) -> Automatic]; Flatten[nf[holecoords]]. But note that this will find the nearest point among pts, even if holecoords is not a subset of the vertex coordinates. Jul 23, 2018 at 14:41