Edit on GitHub

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

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.

The constructors

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

return 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
  • unsafeaddedge!(g, u, v)
  • rebuild!(g)
  • rem_vertex!(g, v)