Neighborhoods and graph traversals

Manual

The AbstractGraph API for exploring neighbors and traversing graphs has to be somewhat adapted to account for the specific aspects of PeriodicGraphs. Here, we present a list of notes relative to these aspects, where g is a PeriodicGraph{N}:

neighbors(g, i) where i::Integer is the list of neighbors of PeriodicVertex{N}(i). Performance-wise, this operation is a simple access on the underlying structure of g so it is very fast, but the returned Vector{PeriodicVertex{N}} should not be modified.
neighbors(g, x) where x::PeriodicVertex{N} is an iterator over the neighbors of x but not an array. The iterator object is a PeriodicGraphs.OffsetVertexIterator.
edges(g) is an iterator over the direct edges of g. Every edge representative will thus be visited exactly once. It is invalidated by any change to g, so g should not be modified while iterating over edges(g). The iterator object is a PeriodicGraphs.PeriodicEdgeIter.
Graphs._neighborhood has a specialization for PeriodicGraph if required.

A typical BFS algorithm on g can be implemented like so:

function bfs(g::PeriodicGraph{N}, starting_vertex, depth) where N
    visited = Set{PeriodicVertex{N}}(starting_vertex)
    Q = Tuple{Int,PeriodicVertex{N}}[(0, starting_vertex)]
    for (distance, u) in Q
        distance > depth && break
        # do stuff with u
        for x in neighbors(g, u)
            x ∈ visited && continue
            push!(x, visited)
            # do stuff with x
            push!(Q, (distance+1, x))
        end
        # do more stuff
    end
    # return something
end

In some cases however, the Set-interface can end up being the bottleneck. In this kind of situation, it may be better to:

replace the initialization of visited by

width = PeriodicGraphs.graph_width!(g)
seen_size = nv(g)*(2*(1 + fld(depth-1, width)) + 1)^N
visited = falses(seen_size)

replace x ∈ visited by visited[hash_position(x, g)] and
replace push!(x, visited) by visited[hash_position(x, g)] = true

although some care should be taken since PeriodicGraphs.graph_width! is only a heuristic.

Such algorithms can be used to compute the topological invariants like coordination_sequence for example.

API

PeriodicGraphs.PeriodicEdgeIter — Type

PeriodicEdgeIter{N} <: AbstractEdgeIter

Edge iterator type for undirected N-periodic graphs.

The iterator only yields edges in the form (u, v, ofs) with either u < v or u == v && ofs > zero(ofs). This is possible because PeriodicGraphs are undirected, hence to each edge (u, v, ofs) in the graph corresponds its reverse edge (v, u, .-ofs). The iterator thus yields each edge of the graph exactly once.

source

PeriodicGraphs.OffsetVertexIterator — Type

OffsetVertexIterator{D} <: AbstractVector{PeriodicVertex{D}}
OffsetVertexIterator(ofs::SVector{D,Int}, list::AbstractVector{PeriodicVertex{D}}) where D

Iterator type that yields the sequence of PeriodicVertex in list, each offset by the input ofs.

source

PeriodicGraphs.graph_width! — Function

graph_width!(g::PeriodicGraph{N}) where N

Set the width internal field of the graph so that the for most n ∈ N*, the n-th neighbor of any vertex v of the initial cell is in a cell (i_1, i_2, ..., i_N) such that max(abs.((i_1, i_2, ..., i_N))) ≤ 1 + fld((n - 1), width). Return the new width.

This function is only a heuristic, it may produce a width that does not satisfy the condition.

This function returns the current width if it is not equal to -1 (internal value used to mark an unset width). If you decide to modify the other internal fields of g, it is probably a good idea to do g.width[] = -1 so that this function gets automatically called when needed, unless you are sure the width will not be affected by your change.

source