# 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*.