Custom graph typing question (Graphs.jl)

Specific Domains Graphs
1

I’ve defined a new graph type which is a subtype of Graphs.AbstractSimpleGraph to represent a grid-like structure:

using Graphs

mutable struct GridSpace{N, T<:Integer} <: Graphs.AbstractSimpleGraph{T}
    ne::T                       #Number of edges
    fadjlist::Vector{Vector{T}} #Sorted adjacency list [src]: (dst, dst, dst)
    gridSize::NTuple{N, T}      #Size of grid (x,y,z...)
    wrapAround::Bool            #Does the grid wrap around
end

And I’ve defined some functions for this new type:

#GridSpaces are not directed
Graphs.is_directed(::Type{<:GridSpace}) = false
Graphs.is_directed(g::GridSpace) = false

#Give compiler information about element types
Base.eltype(g::GridSpace{N,T}) where {N,T} = T
Graphs.edgetype(g::GridSpace) = Graphs.SimpleEdge{eltype(g)}

I’ve also defined the has_edge() function. However, when I try to collect the edge iterations type information is lost (I get a Vector{Any}):

julia> g = GridSpace(4,[[2,3],[1,4],[1,4],[2,3]], (2,2), false)
{4, 4} undirected simple Int64 graph

julia> collect(edges(g))
4-element Vector{Any}:
 Edge 1 => 2
 Edge 1 => 3
 Edge 2 => 4
 Edge 3 => 4

What do I need to define to fix this type issue? I think it has to do with the eltype for SimpleEdgeIter, but I’m not sure exactly how I should define it. Should I define my own method for edges()?

2

This should work:
Base.eltype(::Type{Graphs.SimpleGraphs.SimpleEdgeIter{GridSpace{N, T}}}) where {N, T} = Edge{T}

1 Like
3

That does work! This solution is better than the monstrosity I was using temporary:

edges(g::CellSpace{N,T}) where {N,T<:Integer} = (SimpleEdge(i,j) for (i,v) in enumerate(g.fadjlist) for j in v if j>i)

But I thought I would share it anyways. :person_shrugging: