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.

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):

Full Docs for AbstractGraph types and functions

Base.reverseMethod
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
source
LightGraphs.dstMethod
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
source
LightGraphs.edgesMethod
edges(g)

Return (an iterator to or collection of) the edges of a graph. For AbstractSimpleGraphs 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
source
LightGraphs.has_contiguous_verticesMethod
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.

source
LightGraphs.has_edgeMethod
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
source
LightGraphs.has_vertexFunction
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
source
LightGraphs.inneighborsMethod
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
source
LightGraphs.is_directedMethod
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
source
LightGraphs.neMethod
ne(g)

Return the number of edges in g.

Examples

julia> using LightGraphs

julia> g = path_graph(3);

julia> ne(g)
2
source
LightGraphs.nvMethod
nv(g)

Return the number of vertices in g.

Examples

julia> using LightGraphs

julia> nv(SimpleGraph(3))
3
source
LightGraphs.outneighborsMethod
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
source
LightGraphs.srcMethod
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
source
LightGraphs.verticesFunction
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
source
Base.zeroMethod
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
source