GitHub

Graph algorithms

Defined by Graphs.jl

Graphs.jl provides a number of graph algorithms, including Cuts, Cycles, and Trees, among many others. The algorithms work on any graph type that conforms to the Graphs.jl API.

External algorithm packages

Several other packages implement additional graph algorithms:

  • GraphsColoring.jl provides algorithms for graph coloring, i.e., assigning colors to vertices such that no two neighboring vertices have the same color.
  • GraphsFlows.jl provides algorithms for graph flows.
  • GraphsMatching.jl provides algorithms for matchings on weighted graphs.
  • GraphsOptim.jl provides algorithms for graph optimization that rely on mathematical programming.

Interfaces to other graph libraries

Several packages make established graph libraries written in other languages accessible from within Julia and the Graphs.jl ecosystem:

  • IGraphs.jl is a thin Julia wrapper around the C graphs library igraph.
  • NautyGraphs.jl provides graph structures compatible with the graph isomorphism library nauty, allowing for efficient isomorphism checking and canonization, as well as computing the properties of graph automorphism groups.

Dispatching to algorithm implementations in external packages

Apart from providing additional graph types and algorithms, many packages extend existing functions in Graphs.jl with new backends. This can make it easier to use the algorithms from within Graphs.jl.

For example, NautyGraphs.jl provides a new backend for graph isomorphism calculations:

julia> using Graphs, NautyGraphs

julia> g = star_graph(5)
{5, 4} undirected simple Int64 graph

julia> Graphs.Experimental.has_isomorph(g, g, NautyAlg())
true

Here, dispatching via NautyAlg() implicitly converts g to a nauty-compatible format and uses nauty for the isomorphism computation.

Functions extended by IGraphs.jl

A list of functions extended by IGraphs.jl can be obtained with

import IGraphs
IGraphs.igraphalg_methods()
3-element Vector{Symbol}:
 :diameter
 :has_isomorph
 :radius

Functions extended by NautyGraphs.jl

A list of functions extended by NautyGraphs.jl can be obtained with

import NautyGraphs
NautyGraphs.nautyalg_methods()
2-element Vector{Symbol}:
 :count_isomorph
 :has_isomorph