GridGraph

A rectangular (or higher-dimensional) grid graph.

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageGridGraph✓↗

GridGraph(dims)the Cartesian product of paths of the given lengths — GridGraph({m, n}) is an $m \times n$ grid. Vertices are numbered 1-based, the first index varying fastest, as in Wolfram.

SageMathenumeratio_graph(graphs.GridGraph(dims))

Typed signatures

Type	Package	Applies
(list<integer>) -> value	combinatorics	always

Domain: Collections

Examples

Basic #

A 3x4 grid has 12 vertices

live ↗

In$\mathrm{VertexCount}(\mathrm{GridGraph}(\bigl\lbrack3, 4\bigr\rbrack))$Out$12$

$m(n-1) + n(m-1) = 3 \cdot 3 + 4 \cdot 2 = 17$ edges

live ↗

In$\mathrm{EdgeCount}(\mathrm{GridGraph}(\bigl\lbrack3, 4\bigr\rbrack))$Out$17$

Dimensions are given as a list, so a three- and a four-dimensional grid come from lists of $2$s Vertices are numbered with the first index varying fastest, as in Wolfram (our own convention, not a known value).

live ↗

In$\bigl\lbrack\mathrm{GridGraph}(\bigl\lbrack2, 2, 2\bigr\rbrack), \mathrm{GridGraph}(\bigl\lbrack2, 2, 2, 2\bigr\rbrack)\bigr\rbrack$Out$\bigl\lbrack\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6, 7, 8\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(1, 5), \mathrm{UndirectedEdge}(2, 4), \mathrm{UndirectedEdge}(2, 6), \mathrm{UndirectedEdge}(3, 4), \mathrm{UndirectedEdge}(3, 7), \mathrm{UndirectedEdge}(4, 8), \mathrm{UndirectedEdge}(5, 6), \mathrm{UndirectedEdge}(5, 7), \mathrm{UndirectedEdge}(6, 8), \mathrm{UndirectedEdge}(7, 8)\bigr\rbrack), \mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(1, 5), \mathrm{UndirectedEdge}(1, 9), \mathrm{UndirectedEdge}(2, 4), \mathrm{UndirectedEdge}(2, 6), \mathrm{UndirectedEdge}(2, 10), \mathrm{UndirectedEdge}(3, 4), \mathrm{UndirectedEdge}(3, 7), \mathrm{UndirectedEdge}(3, 11), \mathrm{UndirectedEdge}(4, 8), \mathrm{UndirectedEdge}(4, 12), \mathrm{UndirectedEdge}(5, 6), \mathrm{UndirectedEdge}(5, 7), \mathrm{UndirectedEdge}(5, 13), \mathrm{UndirectedEdge}(6, 8), \mathrm{UndirectedEdge}(6, 14), \mathrm{UndirectedEdge}(7, 8), \mathrm{UndirectedEdge}(7, 15), \mathrm{UndirectedEdge}(8, 16), \mathrm{UndirectedEdge}(9, 10), \mathrm{UndirectedEdge}(9, 11), \mathrm{UndirectedEdge}(9, 13), \mathrm{UndirectedEdge}(10, 12), \mathrm{UndirectedEdge}(10, 14), \mathrm{UndirectedEdge}(11, 12), \mathrm{UndirectedEdge}(11, 15), \mathrm{UndirectedEdge}(12, 16), \mathrm{UndirectedEdge}(13, 14), \mathrm{UndirectedEdge}(13, 15), \mathrm{UndirectedEdge}(14, 16), \mathrm{UndirectedEdge}(15, 16)\bigr\rbrack)\bigr\rbrack$

Scope #

Vertices are numbered with the first index varying fastest, as in Wolfram (our own convention, not a known value).

live ↗

In$\mathrm{GridGraph}(\bigl\lbrack2, 3\bigr\rbrack)$Out$\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(2, 4), \mathrm{UndirectedEdge}(3, 4), \mathrm{UndirectedEdge}(3, 5), \mathrm{UndirectedEdge}(4, 6), \mathrm{UndirectedEdge}(5, 6)\bigr\rbrack)$

Applications #

Eccentricity on a $3\times3$ grid: $2$ at the centre, $4$ at the corners

live ↗

In$\mathrm{Map}(\operatorname{\_1}↦\mathrm{VertexEccentricity}(\mathrm{GridGraph}(\bigl\lbrack3, 3\bigr\rbrack), \operatorname{\_1}), \mathrm{VertexList}(\mathrm{GridGraph}(\bigl\lbrack3, 3\bigr\rbrack)))$Out$\bigl\lbrack4, 3, 4, 3, 2, 3, 4, 3, 4\bigr\rbrack$

Properties #

A $1\times4$ grid is a path

live ↗

In$\mathrm{IsPathGraph}(\mathrm{GridGraph}(\bigl\lbrack1, 4\bigr\rbrack))$Out$\mathrm{True}$

Swapping the dimensions gives the same path

live ↗

In$\mathrm{IsPathGraph}(\mathrm{GridGraph}(\bigl\lbrack4, 1\bigr\rbrack))$Out$\mathrm{True}$

Extra size-1 dimensions add nothing, so still a path

live ↗

In$\mathrm{IsPathGraph}(\mathrm{GridGraph}(\bigl\lbrack1, 4, 1\bigr\rbrack))$Out$\mathrm{True}$

Grids are bipartite, coloured like a checkerboard

live ↗

In$\mathrm{IsBipartiteGraph}(\mathrm{GridGraph}(\bigl\lbrack3, 4\bigr\rbrack))$Out$\mathrm{True}$

A $2\times2$ grid is the $4$-cycle Vertices are numbered with the first index varying fastest, as in Wolfram (our own convention, not a known value).

live ↗

In$\bigl\lbrack\mathrm{GridGraph}(\bigl\lbrack2, 2\bigr\rbrack), \mathrm{CycleGraph}(4)\bigr\rbrack$Out$\bigl\lbrack\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(2, 4), \mathrm{UndirectedEdge}(3, 4)\bigr\rbrack), \mathrm{Graph}(\bigl\lbrack1, 2, 3, 4\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(2, 3), \mathrm{UndirectedEdge}(3, 4), \mathrm{UndirectedEdge}(4, 1)\bigr\rbrack)\bigr\rbrack$

A $2\times2\times2$ grid is the cube graph Vertices are numbered with the first index varying fastest, as in Wolfram (our own convention, not a known value).

live ↗

In$\bigl\lbrack\mathrm{GridGraph}(\bigl\lbrack2, 2, 2\bigr\rbrack), \mathrm{HypercubeGraph}(3)\bigr\rbrack$Out$\bigl\lbrack\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6, 7, 8\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(1, 5), \mathrm{UndirectedEdge}(2, 4), \mathrm{UndirectedEdge}(2, 6), \mathrm{UndirectedEdge}(3, 4), \mathrm{UndirectedEdge}(3, 7), \mathrm{UndirectedEdge}(4, 8), \mathrm{UndirectedEdge}(5, 6), \mathrm{UndirectedEdge}(5, 7), \mathrm{UndirectedEdge}(6, 8), \mathrm{UndirectedEdge}(7, 8)\bigr\rbrack), \mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6, 7, 8\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(1, 5), \mathrm{UndirectedEdge}(2, 4), \mathrm{UndirectedEdge}(2, 6), \mathrm{UndirectedEdge}(3, 4), \mathrm{UndirectedEdge}(3, 7), \mathrm{UndirectedEdge}(4, 8), \mathrm{UndirectedEdge}(5, 6), \mathrm{UndirectedEdge}(5, 7), \mathrm{UndirectedEdge}(6, 8), \mathrm{UndirectedEdge}(7, 8)\bigr\rbrack)\bigr\rbrack$

About

Examples	11
Checked against	Wolfram Language 11 agreeSageMath 3 agree4 differ
Crosswalk	Wolfram LanguageSageMath

Implementation

mappedsagepackages/oracle/src/mappings.ts

See also: HypercubeGraph, CompleteGraph