# LightGraphs Types

*LightGraphs.jl* supports both the `AbstractGraph`

type and two concrete simple graph types – `SimpleGraph`

for undirected graphs and `SimpleDiGraph`

for directed graphs – that are subtypes of `AbstractGraph`

.

## Concrete Types

*LightGraphs.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 specifying 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 as 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()`

; there are several options (see the tutorials for examples).

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 spare capacity.

## AbstractGraph Type

*LightGraphs.jl* is structured around a few abstract types developers can base their types on. See Developing Alternate Graph Types for the minimal methods to implement.

`LightGraphs.AbstractEdge`

`LightGraphs.AbstractEdgeIter`

`LightGraphs.AbstractGraph`

`LightGraphs.HasContiguousVertices`

To encourage experimentation and development within the JuliaGraphs ecosystem, *LightGraphs.jl* defines the `AbstractGraph`

type, which is used by libraries like MetaGraphs.jl (for graphs with associated meta-data) and SimpleWeightedGraphs.jl (for weighted graphs). All types that are a subset of `AbstractGraph`

must implement the following functions (most of which are described in more detail in Accessing Graph Properties and Making and Modifying Graphs):

`Base.reverse`

`Base.zero`

`LightGraphs.dst`

`LightGraphs.edges`

`LightGraphs.edgetype`

`LightGraphs.has_contiguous_vertices`

`LightGraphs.has_edge`

`LightGraphs.has_vertex`

`LightGraphs.inneighbors`

`LightGraphs.is_directed`

`LightGraphs.ne`

`LightGraphs.nv`

`LightGraphs.outneighbors`

`LightGraphs.src`

`LightGraphs.vertices`

## Full Docs for AbstractGraph types and functions

`LightGraphs.AbstractEdge`

— Type`AbstractEdge`

An abstract type representing a single edge between two vertices of a graph.

`LightGraphs.AbstractEdgeIter`

— Type`AbstractEdgeIter`

An abstract type representing an edge iterator.

`LightGraphs.AbstractGraph`

— Type`AbstractGraph`

An abstract type representing a graph.

`LightGraphs.HasContiguousVertices`

— Type`HasContiguousVertices{G}`

A trait indicating whether the vertices of graphs of type `G`

are always contiguous integers starting at 1.

`Base.reverse`

— Method`reverse(e)`

Create a new edge from `e`

with source and destination vertices reversed.

**Examples**

```
julia> using LightGraphs
julia> g = SimpleDiGraph(2);
julia> add_edge!(g, 1, 2);
julia> reverse(first(edges(g)))
Edge 2 => 1
```

`LightGraphs.dst`

— Method`dst(e)`

Return the destination vertex of edge `e`

.

**Examples**

```
julia> using LightGraphs
julia> g = SimpleGraph(2);
julia> add_edge!(g, 1, 2);
julia> dst(first(edges(g)))
2
```

`LightGraphs.edges`

— Method`edges(g)`

Return (an iterator to or collection of) the edges of a graph. For `AbstractSimpleGraph`

s it returns a `SimpleEdgeIter`

. The expressions `e in edges(g)`

and `e ∈ edges(ga)`

evaluate as calls to `has_edge`

.

**Implementation Notes**

A returned iterator is valid for one pass over the edges, and is invalidated by changes to `g`

.

**Examples**

```
julia> using LightGraphs
julia> g = path_graph(3);
julia> collect(edges(g))
2-element Array{LightGraphs.SimpleGraphs.SimpleEdge{Int64},1}:
Edge 1 => 2
Edge 2 => 3
```

`LightGraphs.edgetype`

— Method`edgetype(g)`

Return the type of graph `g`

's edge

`LightGraphs.has_contiguous_vertices`

— Method`has_contiguous_vertices(::Type{G}) -> Bool where {G <: AbstractGraph}`

Method implemented by graph types to indicate whether their vertices are contiguous numbers. Defaults to true.

`LightGraphs.has_edge`

— Method`has_edge(g, s, d)`

Return true if the graph `g`

has an edge from node `s`

to node `d`

.

An optional `has_edge(g, e)`

can be implemented to check if an edge belongs to a graph, including any data other than source and destination node.

`e ∈ edges(g)`

or `e ∈ edges(g)`

evaluate as calls to `has_edge`

, c.f. `edges`

.

**Examples**

```
julia> using LightGraphs
julia> g = SimpleDiGraph(2);
julia> add_edge!(g, 1, 2);
julia> has_edge(g, 1, 2)
true
julia> has_edge(g, 2, 1)
false
```

`LightGraphs.has_vertex`

— Function`has_vertex(g, v)`

Return true if `v`

is a vertex of `g`

.

**Examples**

```
julia> using LightGraphs
julia> has_vertex(SimpleGraph(2), 1)
true
julia> has_vertex(SimpleGraph(2), 3)
false
```

`LightGraphs.inneighbors`

— Method`inneighbors(g, v)`

Return a list of all neighbors connected to vertex `v`

by an incoming edge.

**Implementation Notes**

Returns a reference to the current graph's internal structures, not a copy. Do not modify result. If the graph is modified, the behavior is undefined: the array behind this reference may be modified too, but this is not guaranteed.

**Examples**

```
julia> g = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0]);
julia> inneighbors(g, 4)
2-element Array{Int64,1}:
3
5
```

`LightGraphs.is_directed`

— Method`is_directed(G)`

Return `true`

if the graph type `G`

is a directed graph; `false`

otherwise. New graph types must implement `is_directed(::Type{<:G})`

. The method can also be called with `is_directed(g::G)`

**Examples**

```
julia> using LightGraphs
julia> is_directed(SimpleGraph(2))
false
julia> is_directed(SimpleGraph)
false
julia> is_directed(SimpleDiGraph(2))
true
```

`LightGraphs.ne`

— Method`ne(g)`

Return the number of edges in `g`

.

**Examples**

```
julia> using LightGraphs
julia> g = path_graph(3);
julia> ne(g)
2
```

`LightGraphs.nv`

— Method`nv(g)`

Return the number of vertices in `g`

.

**Examples**

```
julia> using LightGraphs
julia> nv(SimpleGraph(3))
3
```

`LightGraphs.outneighbors`

— Method`outneighbors(g, v)`

Return a list of all neighbors connected to vertex `v`

by an outgoing edge.

**Implementation Notes**

Returns a reference to the current graph's internal structures, not a copy. Do not modify result. If the graph is modified, the behavior is undefined: the array behind this reference may be modified too, but this is not guaranteed.

**Examples**

```
julia> g = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0]);
julia> outneighbors(g, 4)
1-element Array{Int64,1}:
5
```

`LightGraphs.src`

— Method`src(e)`

Return the source vertex of edge `e`

.

**Examples**

```
julia> using LightGraphs
julia> g = SimpleGraph(2);
julia> add_edge!(g, 1, 2);
julia> src(first(edges(g)))
1
```

`LightGraphs.vertices`

— Function`vertices(g::AbstractGraph)`

Return (an iterator to or collection of) the vertices of a graph.

**Implementation Notes**

A returned iterator is valid for one pass over the edges, and is invalidated by changes to `g`

.

**Examples**

```
julia> using LightGraphs
julia> collect(vertices(SimpleGraph(4)))
4-element Array{Int64,1}:
1
2
3
4
```

`Base.zero`

— Method`zero(G)`

Return a zero-vertex, zero-edge version of the graph type `G`

. The fallback is defined for graph values `zero(g::G) = zero(G)`

.

**Examples**

```
julia> g = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0]);
julia> zero(typeof(g))
{0, 0} directed simple Int64 graph
julia> zero(g)
{0, 0} directed simple Int64 graph
```