General utilities

diameter(adjacency_matrix :: Matrix{<:Integer}) :: Int

Compute the diameter of a graph from its simple adjacency matrix.

All values in adjacency_matrix should be either 0 or 1.

distances(adjacency_matrix :: Matrix{T}) :: Matrix{T} where T<:Integer

Compute the shortest distance from any vertex to any other vertex in the graph for the given adjacency_matrix.

Return a Matrix whose entry at (i,j) is the length of a shortest path from i to j.

The Graph has to be connected. This method uses Seidels APSP-Algorithm.

adjacency_matrix(adjList::Vector{Vector{<:Integer}}) :: Matrix{Int}

Construct the adjacency matrix from an adjacency list.

matrix_equal(A::Matrix{Int}, B::Matrix{Int}, p::Vector{Int}) :: Bool

returns true if A == B[p,p]`

matrix_equal(A::Matrix{Int}, B::Matrix{Int}) :: Bool

Return true if A equals B.

This function is much faster than calling A==B. However, A and B are assumed to have the same dimensions.

invert_permutation(p::Vector{<:Integer})

Return the inverse of the permutation p.

Example

julia> p = [2,1,4,5,3];
julia> p_inv = invert_perm(p); 
julia> show(p_inv)
[4, 2, 5, 1, 6, 3]
julia> show(p_inv[p])
[1, 2, 3, 4, 5, 6]

degrees(A::Matrix{<:Integer}) :: Vector{<:Integer}

Return a vector containing the degrees of every vertex given an adjacency matrix A.

degrees(g::TriangulatedPolygon) :: Vector{Int32}

Compute a list of the degrees of every single vertex in g.

relative_degree(A::Matrix{<:Integer}, u::Integer, V::Vector{<:Integer}) :: Int32

Compute the number of edges going from u into any vertex in the subset of points V.

Arguments

-A::Matrix{<:Integer}: the adjacency matrix. A[i,j] = 1 if there is an edge going from i to j

relative_degree(g::TriangulatedPolygon, u::Integer, V::Vector{<:Integer}) :: Vector{<:Integer}

Count the number of edges in g going from u to a vertex in V.

relative_degrees(A::Matrix{<:Integer}, U::Vector{<:Integer}, V::Vector{<:Integer}) :: Vector{Int32}

Compute the relative degrees of points in U onto the subset of points V.