Graph types

Defined by Graphs.jl

Graphs.jl provides two concrete graph types: SimpleGraph is an undirected graph, and SimpleDiGraph is its directed counterpart. Both of these types can be parameterized to specify how vertices are identified (by default, SimpleGraph and SimpleDiGraph use the system default integer type, usually Int64).

A graph G is described by a set of vertices V and edges E: G = {V, E}. V is an integer range 1:n; E is represented using forward (and, for directed graphs, backward) adjacency lists indexed by vertices. Edges may also be accessed via an iterator that yields Edge types containing (src<:Integer, dst<:Integer) values. Both vertices and edges may be integers of any type, and the smallest type that fits the data is recommended in order to save memory.

Graphs are created using SimpleGraph() or SimpleDiGraph(), see Graph construction for details.

Multiple edges between two given vertices are not allowed: an attempt to add an edge that already exists in a graph will not raise an error. This event can be detected using the return value of add_edge!.

Note that graphs in which the number of vertices equals or approaches the typemax of the underlying graph element (e.g., a SimpleGraph{UInt8} with 127 vertices) may encounter arithmetic overflow errors in some functions, which should be reported as bugs. To be safe, please ensure that your graph is sized with some capacity to spare.

Available in the wider ecosystem

In addition to providing SimpleGraph and SimpleDiGraph implementations, Graphs.jl also serves as an interface for custom graph types (see AbstractGraph interface).

Currently, several other packages implement alternative graph types:

  • SimpleWeightedGraphs.jl provides a structure for (un)directed graphs with the ability to specify weights on edges.
  • MetaGraphs.jl provides a structure for (un)directed graphs that supports user-defined properties on the graph, vertices, and edges.
  • MetaGraphsNext.jl does the same but in a type-stable manner, and with a slightly different interface.
  • StaticGraphs.jl supports very large graph structures in a space- and time-efficient manner, but as the name implies, does not allow modification of the graph once created.

Which graph type should I use?

These are general guidelines to help you select the proper graph type.

  • In general, prefer the native SimpleGraphs/SimpleDiGraphs structures in Graphs.jl.
  • If you need edge weights and don't require large numbers of graph modifications, use SimpleWeightedGraphs.jl.
  • If you need labeling of vertices or edges, use MetaGraphs.jl or MetaGraphsNext.jl.
  • If you work with very large graphs (billions to tens of billions of edges) and don't need mutability, use StaticGraphs.jl.