SimpleGraphs formats
Graphs.jl provides two basic graph formats based on adjacency lists, along with many other functions defined in the Graphs.SimpleGraphs
submodule.
Index
Graphs.SimpleGraphs.AbstractSimpleGraph
Graphs.SimpleGraphs.SimpleDiGraph
Graphs.SimpleGraphs.SimpleDiGraph
Graphs.SimpleGraphs.SimpleDiGraph
Graphs.SimpleGraphs.SimpleDiGraph
Graphs.SimpleGraphs.SimpleDiGraph
Graphs.SimpleGraphs.SimpleDiGraph
Graphs.SimpleGraphs.SimpleDiGraph
Graphs.SimpleGraphs.SimpleDiGraph
Graphs.SimpleGraphs.SimpleEdgeIter
Graphs.SimpleGraphs.SimpleGraph
Graphs.SimpleGraphs.SimpleGraph
Graphs.SimpleGraphs.SimpleGraph
Graphs.SimpleGraphs.SimpleGraph
Graphs.SimpleGraphs.SimpleGraph
Graphs.SimpleGraphs.SimpleGraph
Graphs.SimpleGraphs.SimpleGraph
Graphs.SimpleGraphs.SimpleGraph
Graphs.SimpleGraphs.SimpleDiGraphFromIterator
Graphs.SimpleGraphs.SimpleGraphFromIterator
Graphs.SimpleGraphs.add_edge!
Graphs.SimpleGraphs.add_vertex!
Graphs.SimpleGraphs.adj
Graphs.SimpleGraphs.badj
Graphs.SimpleGraphs.rem_edge!
Graphs.SimpleGraphs.rem_vertex!
Graphs.SimpleGraphs.rem_vertices!
Graphs.SimpleGraphs.throw_if_invalid_eltype
Graphs.is_directed
Graphs.squash
Full docs
Graphs.SimpleGraphs.SimpleDiGraph
— TypeSimpleDiGraph{T}
A type representing a directed graph.
Graphs.SimpleGraphs.SimpleDiGraph
— MethodSimpleDiGraph{T}(adjm::AbstractMatrix)
Construct a SimpleDiGraph{T}
from the adjacency matrix adjm
. If adjm[i][j] != 0
, an edge (i, j)
is inserted. adjm
must be a square matrix. The element type T
can be omitted.
Examples
julia> using Graphs
julia> A1 = [false true; false false]
2×2 Matrix{Bool}:
0 1
0 0
julia> SimpleDiGraph(A1)
{2, 1} directed simple Int64 graph
julia> A2 = [2 7; 5 0]
2×2 Matrix{Int64}:
2 7
5 0
julia> SimpleDiGraph{Int16}(A2)
{2, 3} directed simple Int16 graph
Graphs.SimpleGraphs.SimpleDiGraph
— MethodSimpleDiGraph(g::AbstractSimpleGraph)
Construct an directed SimpleDiGraph
from a graph g
. The element type is the same as for g
.
Examples
julia> using Graphs
julia> g = path_graph(Int8(5))
{5, 4} undirected simple Int8 graph
julia> SimpleDiGraph(g)
{5, 8} directed simple Int8 graph
Graphs.SimpleGraphs.SimpleDiGraph
— MethodSimpleDiGraph{T}(g::AbstractGraph)
SimpleDiGraph(g::AbstractGraph)
Construct a SimpleDiGraph
from any AbstractGraph
by enumerating edges.
If g
is undirected, both directed edges (u, v)
and (v, u)
are added if undirected edge {u, v}
exists.
Graphs.SimpleGraphs.SimpleDiGraph
— MethodSimpleDiGraph(edge_list::Vector)
Construct a SimpleDiGraph
from a vector of edges. The element type is taken from the edges in edge_list
. The number of vertices is the highest that is used in an edge in edge_list
.
Implementation Notes
This constructor works the fastest when edge_list
is sorted by the lexical ordering and does not contain any duplicates.
See also
Examples
julia> using Graphs
julia> el = Edge.([ (1, 3), (1, 5), (3, 1) ])
3-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 3
Edge 1 => 5
Edge 3 => 1
julia> SimpleDiGraph(el)
{5, 3} directed simple Int64 graph
Graphs.SimpleGraphs.SimpleDiGraph
— MethodSimpleDiGraph{T}(g::SimpleDiGraph)
Construct a copy of g. If the element type T
is specified, the vertices of g
are converted to this type. Otherwise the element type is the same as for g
.
Examples
julia> using Graphs
julia> g = complete_digraph(5)
{5, 20} directed simple Int64 graph
julia> SimpleDiGraph{UInt8}(g)
{5, 20} directed simple UInt8 graph
Graphs.SimpleGraphs.SimpleDiGraph
— MethodSimpleDiGraph(::Type{T})
Construct an empty SimpleDiGraph{T}
with 0 vertices and 0 edges.
Examples
julia> using Graphs
julia> SimpleDiGraph(UInt8)
{0, 0} directed simple UInt8 graph
Graphs.SimpleGraphs.SimpleDiGraph
— MethodSimpleDiGraph{T}(n=0)
Construct a SimpleDiGraph{T}
with n
vertices and 0 edges. If not specified, the element type T
is the type of n
.
Examples
julia> using Graphs
julia> SimpleDiGraph(UInt8(10))
{10, 0} directed simple UInt8 graph
Graphs.SimpleGraphs.SimpleDiGraphFromIterator
— MethodSimpleDiGraphFromIterator(iter)
Create a SimpleDiGraph
from an iterator iter
. The elements in iter
must be of type <: SimpleEdge
.
Examples
julia> using Graphs
julia> g = SimpleDiGraph(2);
julia> add_edge!(g, 1, 2);
julia> add_edge!(g, 2, 1);
julia> h = SimpleDiGraphFromIterator(edges(g))
{2, 2} directed simple Int64 graph
julia> collect(edges(h))
2-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
Edge 2 => 1
Graphs.SimpleGraphs.SimpleEdgeIter
— TypeSimpleEdgeIter
The function edges
returns a SimpleEdgeIter
for AbstractSimpleGraph
s. The iterates are in lexicographical order, smallest first. The iterator is valid for one pass over the edges, and is invalidated by changes to the graph.
Examples
julia> using Graphs
julia> g = path_graph(3);
julia> es = edges(g)
SimpleEdgeIter 2
julia> e_it = iterate(es)
(Edge 1 => 2, (1, 2))
julia> iterate(es, e_it[2])
(Edge 2 => 3, (2, 3))
Graphs.SimpleGraphs.SimpleGraph
— TypeSimpleGraph{T}
A type representing an undirected graph.
Graphs.SimpleGraphs.SimpleGraph
— MethodSimpleGraph{T}(adjm::AbstractMatrix)
Construct a SimpleGraph{T}
from the adjacency matrix adjm
. If adjm[i][j] != 0
, an edge (i, j)
is inserted. adjm
must be a square and symmetric matrix. The element type T
can be omitted.
Examples
julia> using Graphs
julia> A1 = [false true; true false];
julia> SimpleGraph(A1)
{2, 1} undirected simple Int64 graph
julia> A2 = [2 7; 7 0];
julia> SimpleGraph{Int16}(A2)
{2, 2} undirected simple Int16 graph
Graphs.SimpleGraphs.SimpleGraph
— MethodSimpleGraph(g::SimpleDiGraph)
Construct an undirected SimpleGraph
from a directed SimpleDiGraph
. Every directed edge in g
is added as an undirected edge. The element type is the same as for g
.
Examples
julia> using Graphs
julia> g = path_digraph(Int8(5))
{5, 4} directed simple Int8 graph
julia> SimpleGraph(g)
{5, 4} undirected simple Int8 graph
Graphs.SimpleGraphs.SimpleGraph
— MethodSimpleGraph{T}(g::SimpleGraph)
Construct a copy of g. If the element type T
is specified, the vertices of g
are converted to this type. Otherwise the element type is the same as for g
.
Examples
julia> using Graphs
julia> g = complete_graph(5)
{5, 10} undirected simple Int64 graph
julia> SimpleGraph{UInt8}(g)
{5, 10} undirected simple UInt8 graph
Graphs.SimpleGraphs.SimpleGraph
— MethodSimpleGraph{T}(g::AbstractGraph)
SimpleGraph(g::AbstractGraph)
Construct a SimpleGraph
from any AbstractGraph
by enumerating edges.
If g
is directed, a directed edge {u, v}
is added if either directed edge (u, v)
or (v, u)
exists.
Graphs.SimpleGraphs.SimpleGraph
— MethodSimpleGraph(edge_list::Vector)
Construct a SimpleGraph
from a vector of edges. The element type is taken from the edges in edge_list
. The number of vertices is the highest that is used in an edge in edge_list
.
Implementation Notes
This constructor works the fastest when edge_list
is sorted by the lexical ordering and does not contain any duplicates.
See also
Examples
julia> using Graphs
julia> el = Edge.([ (1, 2), (1, 5) ])
2-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
Edge 1 => 5
julia> SimpleGraph(el)
{5, 2} undirected simple Int64 graph
Graphs.SimpleGraphs.SimpleGraph
— MethodSimpleGraph(::Type{T})
Construct an empty SimpleGraph{T}
with 0 vertices and 0 edges.
Examples
julia> using Graphs
julia> SimpleGraph(UInt8)
{0, 0} undirected simple UInt8 graph
Graphs.SimpleGraphs.SimpleGraph
— MethodSimpleGraph{T}(n=0)
Construct a SimpleGraph{T}
with n
vertices and 0 edges. If not specified, the element type T
is the type of n
.
Examples
julia> using Graphs
julia> SimpleGraph(UInt8(10))
{10, 0} undirected simple UInt8 graph
Graphs.SimpleGraphs.SimpleGraphFromIterator
— MethodSimpleGraphFromIterator(iter)
Create a SimpleGraph
from an iterator iter
. The elements in iter must be of type <: SimpleEdge
.
Examples
julia> using Graphs
julia> g = SimpleGraph(3);
julia> add_edge!(g, 1, 2);
julia> add_edge!(g, 2, 3);
julia> h = SimpleGraphFromIterator(edges(g));
julia> collect(edges(h))
2-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
Edge 2 => 3
Graphs.SimpleGraphs.add_edge!
— Methodadd_edge!(g, e)
Add an edge e
to graph g
. Return true
if edge was added successfully, otherwise return false
.
Examples
julia> using Graphs
julia> g = SimpleGraph(2);
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 2, 3)
false
Graphs.SimpleGraphs.add_vertex!
— Methodadd_vertex!(g)
Add a new vertex to the graph g
. Return true
if addition was successful.
Examples
julia> using Graphs
julia> g = SimpleGraph(Int8(typemax(Int8) - 1))
{126, 0} undirected simple Int8 graph
julia> add_vertex!(g)
true
julia> add_vertex!(g)
false
Graphs.SimpleGraphs.adj
— Methodadj(g[, v])
Return the adjacency list of a graph. If v
is specified, return only the adjacency list for that vertex.
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.
Graphs.SimpleGraphs.badj
— Methodbadj(g::SimpleGraph[, v::Integer])
Return the backwards adjacency list of a graph. If v
is specified, return only the adjacency list for that vertex.
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.
Graphs.SimpleGraphs.rem_edge!
— Methodrem_edge!(g, e)
Remove an edge e
from graph g
. Return true
if edge was removed successfully, otherwise return false
.
Implementation Notes
If rem_edge!
returns false
, the graph may be in an indeterminate state, as there are multiple points where the function can exit with false
.
Examples
julia> using Graphs
julia> g = SimpleGraph(2);
julia> add_edge!(g, 1, 2);
julia> rem_edge!(g, 1, 2)
true
julia> rem_edge!(g, 1, 2)
false
Graphs.SimpleGraphs.rem_vertices!
— Methodrem_vertices!(g, vs, keep_order=false) -> vmap
Remove all vertices in vs
from g
. Return a vector vmap
that maps the vertices in the modified graph to the ones in the unmodified graph. If keep_order
is true
, the vertices in the modified graph appear in the same order as they did in the unmodified graph. This might be slower.
Implementation Notes
This function is not part of the official Graphs API and is subject to change/removal between major versions.
Examples
julia> using Graphs
julia> g = complete_graph(5)
{5, 10} undirected simple Int64 graph
julia> vmap = rem_vertices!(g, [2, 4], keep_order=true);
julia> vmap
3-element Vector{Int64}:
1
3
5
julia> g
{3, 3} undirected simple Int64 graph
Graphs.is_directed
— Methodis_directed(g)
Return true
if g
is a directed graph.
Graphs.SimpleGraphs.AbstractSimpleGraph
— TypeAbstractSimpleGraph
An abstract type representing a simple graph structure. AbstractSimpleGraph
s must have the following elements:
vertices::UnitRange{Integer}
fadjlist::Vector{Vector{Integer}}
ne::Integer
Graphs.SimpleGraphs.rem_vertex!
— Methodrem_vertex!(g, v)
Remove the vertex v
from graph g
. Return false
if removal fails (e.g., if vertex is not in the graph); true
otherwise.
Performance
Time complexity is $\mathcal{O}(k^2)$, where $k$ is the max of the degrees of vertex $v$ and vertex $|V|$.
Implementation Notes
This operation has to be performed carefully if one keeps external data structures indexed by edges or vertices in the graph, since internally the removal is performed swapping the vertices v
and $|V|$, and removing the last vertex $|V|$ from the graph. After removal the vertices in g
will be indexed by $1:|V|-1$.
Examples
julia> using Graphs
julia> g = SimpleGraph(2);
julia> rem_vertex!(g, 2)
true
julia> rem_vertex!(g, 2)
false
Graphs.SimpleGraphs.throw_if_invalid_eltype
— Methodthrow_if_invalid_eltype(T)
Internal function, throw a DomainError
if T
is not a concrete type Integer
. Can be used in the constructor of AbstractSimpleGraphs, as Julia's typesystem does not enforce concrete types, which can lead to problems. E.g SimpleGraph{Signed}
.
Graphs.squash
— Methodsquash(g::Union{SimpleGraph, SimpleDiGraph}; alwayscopy=true)
Specialised version of Graphs.squash
for SimpleGraph
and SimpleDiGraph
. If alwayscopy
is true
, the resulting graph will always be a copy, otherwise it can also be the original graph.