Grid Graphs

Grid Graphs

GraphIdx.Grid — Module.

Computations related to grid graphs

source
GraphIdx.Grid.GridGraph — Type.

Capture all we need to know about a grid graph.

source
GraphIdx.Grid.ImplicitGridGraph — Type.

Idea: Do not store the graph explicitly but compute the neighbors as needed. For avoiding too many allocations, return just a view to the buffer

source
GraphIdx.Grid.Pixel — Type.

Position in a grid graph

source
GraphIdx.Grid.collect_edges — Method.
collect_edges(::GridGraph)

Return a Vector{Tuple{Int,Int}} of edges and Vector{Float64} of weights.

source
GraphIdx.Grid.compute_dirs — Method.
compute_dirs(dn)

Setting the neighborhood degree (dn) to i will set all numbers less or equal i in the following diagram as neighbors of [*].

[…] […] […] […] […] […] […]
[…] […] [4] [3] [4] […] […]
[…] [4] [2] [1] [2] [4] […]
[…] [3] [1] [*] [1] [3] […]
[…] [4] [2] [1] [2] [4] […]
[…] […] [4] [3] [4] […] […]
[…] […] […] […] […] […] […]

Example

julia> import GraphIdx.Grid: compute_dirs, Pixel

julia> compute_dirs(2)
2-element Array{Pixel,1}:
 Pixel(1, 0)
 Pixel(1, 1)
source
GraphIdx.Grid.iter_edges — Method.
iter_edges(proc, n1, n2, dirs)

Call proc(u::Int, v::Int, len::Float64) for every grid edge u -- v having length. Hereby u and v are the index of the corresponding grid-nodes.

source
GraphIdx.Grid.iter_edges_pixel — Method.
iter_edges_pixel(proc, g::GridGraph)

Iterate over the edges on a grid graph. Same as `iteredgespixel(::Function, ::Int, ::Int, ::Vector{Pixel}).

Example

julia> import GraphIdx.Grid: GridGraph, iter_edges_pixel

julia> iter_edges_pixel(GridGraph(2, 3)) do i1, j1, i2, j2, len
           println("($i1,$j1) -- ($i2,$j2): $len")
       end
(1,1) -- (2,1): 1.0
(1,2) -- (2,2): 1.0
(1,3) -- (2,3): 1.0
(1,1) -- (1,2): 1.0
(1,2) -- (1,3): 1.0
(2,1) -- (2,2): 1.0
(2,2) -- (2,3): 1.0
source
GraphIdx.Grid.iter_edges_pixel — Method.
iter_edges_pixel(proc, n1, n2, dirs)

Call proc(i1, j1, i2, j2, len) for every grid edge (i1, j1) -- (i2, j2) having length.

source
GraphIdx.Grid.line_D — Method.
line_D(n)

Return the incidence matrix for a line graph of length n. Is equivalent to incmat(1, n, 1).

Example

julia> import GraphIdx.Grid: line_D

julia> line_D(3)
2×3 SparseArrays.SparseMatrixCSC{Float64,Int64} with 4 stored entries:
  [1, 1]  =  1.0
  [1, 2]  =  -1.0
  [2, 2]  =  1.0
  [2, 3]  =  -1.0
source
GraphIdx.Grid.lipschitz — Method.
lipschitz(n1, n2, [dn | dirs])

Compute an upper bound for the Lipschitz-constant for ... TODO: Be more precise

source
GraphIdx.Grid.num_edges — Method.
num_edges(n1, n2, dirs)
num_edges(n1, n2, dn::Int)

Number of edges in a grid graph n1×n2 along directions dirs. If called with last argument a number, first generate dirs.

source