/ 
Graph-Maker-Other-6
River stage zero No dependents
/ Graph::Maker::KnightGrid

NAME

Graph::Maker::KnightGrid - create Knight grid graph

SYNOPSIS

use Graph::Maker::KnightGrid;
$graph = Graph::Maker->new ('knight_grid', dims => [8,8]);

DESCRIPTION

Graph::Maker::KnightGrid creates a Graph.pm graph for a grid of squares with edges connecting squares as a chess knight moves.

The dims and cyclic parameters are the same as Graph::Maker::Grid but the edges here are steps 2,1.

+------+------+------+------+    dims => [3,4]
|      |      |      |      |
|  1   |   2  |   3  |   4  |    edges 1 to 7
|      |      |      |      |          1 to 10
+------+------+------+------+          2 to 9
|      |      |      |      |          2 to 11
|  5   |   6  |   7  |   8  |          2 to 8
|      |      |      |      |          ...
+------+------+------+------+          6 to 4
|      |      |      |      |          6 to 12
|  9   |  10  |  11  |  12  |          ...
|      |      |      |      |          etc
+------+------+------+------+

Cyclic

cyclic => 1 makes the grid wrap-around at its sides. For 2 dimensions this is knight moves on a torus.

For 1 dimension like dims => [6] there are no edges. A knight move 2,1 means move 2 in one dimension and 1 in another. When there is only 1 dimension there is no second dimension for the second step. 2 dimensions like dims => [6,1] can be given and in that case the effect is steps +/-1 and +/-2 along the row of vertices cycling at the ends.

For a 1x1 cyclic grid dims => [1,1], or any higher 1x1x1 etc, there is a self-loop edge since the knight move wraps around from the single vertex to itself. This is the same as the 1-vertex cyclic case in Graph::Maker::Grid. (It also has a self-loop for 1-dimension dims => [1] whereas here that is no edges as described above.)

FUNCTIONS

$graph = Graph::Maker->new('knight_grid', key => value, ...)

The key/value parameters are

dims     => arrayref of dimensions
cyclic   => boolean
graph_maker => subr(key=>value) constructor, default Graph->new

dims and cyclic are in the style of Graph::Maker::Grid. Other parameters are passed to the constructor, either graph_maker or Graph->new().

Like Graph::Maker::Grid, if the graph is directed (the default) then edges are added both forward and backward between vertices. Option undirected => 1 creates an undirected graph and for it there is a single edge between vertices.

FORMULAS

Vertex Degree

For a 2-dimensional grid each vertex is degree up to 8 if the grid is big enough (each dimension >= 5). In a cyclic grid all vertices are this degree. For higher dimensions the degree increases. In general for D dimensions

max_degree = 4*D*(D-1)  = 0, 8, 24, 48, 80, ...       (A033996)

OEIS

A few of the entries in Sloane's Online Encyclopedia of Integer Sequences related to these graphs include

A033996    max vertex degree in a D dimensional grid

A035008    number of edges in an NxN grid
A180413    number of edges in an NxNxN grid

SEE ALSO

Graph::Maker, Graph::Maker::Grid

LICENSE

Copyright 2015, 2016, 2017 Kevin Ryde

This file is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

This file is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with This file. If not, see http://www.gnu.org/licenses/.