9
$\begingroup$

Given a nXn lattice, I need to generate the graph such that there is an edge between two vertices iff they are directly "visible" to each other, i.e., there is no vertex between them.

I'm using

latticeSize = 3;
vertices = Range[latticeSize^2];
coords = Transpose[{Ceiling[vertices/latticeSize], 
    Mod[vertices, latticeSize, 1]}];
coordsPairs = Subsets[coords, {2}];
graph = UndirectedEdge @@@ 
   Replace[Pick[coordsPairs, 
     Map[GCD[#[[2, 1]] - #[[1, 1]], #[[2, 2]] - #[[1, 2]]] == 1 &, 
      coordsPairs]], Dispatch@Thread[coords -> vertices], {2}];
Graph[graph, VertexCoordinates -> Thread[vertices -> coords]]

enter image description here

I've poked at built-in graphs to try to find a predefined graph of this sort (oh, how I'd pay extra to have a graph search engine in MMA).

Might someone know of such a built-in, or if not, a more efficient mechanism to generate them?

$\endgroup$
  • $\begingroup$ "efficient" as in "fast"? $\endgroup$ – Dr. belisarius Sep 15 '15 at 2:18
  • $\begingroup$ @belisarius well, it's ok speed wise - I could shave time vectorizing the gcd, but really memory becomes the issue before that matters - the subsetting gets big fast. Kind of hoping someone chimes in with "...duh, that's just the built-in BigSquareGraphWithEdgesBetweenNonOccludedVertices..." (probably a version 11 addition ;-} ) $\endgroup$ – ciao Sep 15 '15 at 2:23
  • $\begingroup$ Oh, Ok. Thanks. That was my guess :) $\endgroup$ – Dr. belisarius Sep 15 '15 at 2:30
  • 1
    $\begingroup$ Number of edges $\endgroup$ – Dr. belisarius Sep 15 '15 at 2:54
  • 1
    $\begingroup$ I saw that. But OEIS links to a paper that seems to contain more info. Too late here to read it $\endgroup$ – Dr. belisarius Sep 15 '15 at 3:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.