Graph Types and Constructors

Erdos.jl defines a type hierarchy and associated methods for expressing a graph topology and implementing related algorithms. The ready to go graph types are the Graph type for undirected graphs and the DiGraph type for directed graphs. Custom types con be defined inheriting from the abstract types AGraph and ADiGraph. Graph types supporting the internal storages of edge/vertex properties are called networks in Erdos and are documeted here

Abstract Types

# Erdos.AGraph — Type.

abstract type AGraph end

Abstract undirected graph type

source

# Erdos.ADiGraph — Type.

abstract ADiGraph

Abstract directed graph type

source

# Erdos.AGraphOrDiGraph — Constant.

const AGraphOrDiGraph = Union{AGraph, ADiGraph}

Union of AGraph and ADiGraph.

source

# Erdos.AEdge — Type.

abstract type AEdge end

An abstract edge type.

source

Graph / DiGraph / Edge

# Erdos.Graph — Type.

mutable struct Graph{T<:Integer} <: AGraph
    ne::Int
    fadjlist::Vector{Vector{T}}
end

A simple graph type based on an adjacency list.

Graph{T}(n=0)
Graph(n=0) = Graph{Int}(n)

Construct a Graph with n vertices and no edges.

Graph{T}(adjmx::AbstractMatrix; upper=false, selfedges=true)

Construct a Graph{T} from the adjacency matrix adjmx, placing an edge in correspondence to each nonzero element of adjmx. If selfedges=false the diagonal elements of adjmx are ignored. If upper=true only the upper triangular part of adjmx is considered.

source

# Erdos.DiGraph — Type.

mutable struct DiGraph{T<:Integer} <: ADiGraph
    ne::Int
    fadjlist::Vector{Vector{T}}
    badjlist::Vector{Vector{T}}
end

A simple digraph type based on two adjacency lists (forward and backward).

DiGraph{T}(n=0)
DiGraph(n=0) = DiGraph{Int}(n)

Construct a DiGraph with n vertices and no edges.

DiGraph{T}(adjmx::AbstractMatrix; selfedges=true)

Construct a DiGraph{T} from the adjacency matrix adjmx, placing an edge in correspondence to each nonzero element of adjmx. If selfedges=false the diagonal elements of adjmx are ignored.

source

# Erdos.Edge — Type.

struct Edge
    src::Int
    dst::Int
end

A type representing an edge between two vertices of a graph.

source

Defining new types

In order to define a custom graph type, e.g. MyGraph <: AGraph, some guarantee have to be respected and some methods have to be exposed. Take a look to the files in src/factory/ for some examples. Custom edges, e.g. MyEdge <: AEdge, have to expose src(e) and dst(e) methods.

Guarantees:

  • vertices are integers in 1:nv(g)

Mandatory methods:

  • basic constructors: MyGraph(n), MyGraph())
  • nv(g)
  • ne(g)
  • out_neighbors(g, v)
  • in_neighbors(g, v) #digraph
  • edge(g, u, v)
  • add_edge!(g, u, v)
  • rem_edge!(g, u, v)
  • add_vertex!(g)
  • pop_vertex!(g)
  • graphtype(g)
  • digraphtype(g)
  • edgetype(g)
  • vertextype(g)
  • swap_vertices!(g, u, v)

Some methods have general fallbacks relying on the more foundamental API described above, but could probably made more efficient knowing the internal implementation of the graph.

Reccomended overrides:

  • in_adjlist(g) #digraph
  • out_adjlist(g)
  • has_edge(g, u, v)
  • ==(g, h)
  • out_edges(g, u)
  • in_edges(g, u) # digraph
  • rem_edge!(g, e)
  • graph(dg)
  • digraph(g)
  • reverse!(g) #digraph
  • unsafe_add_edge!(g, u, v)
  • rebuild!(g)
  • rem_vertex!(g, v)