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

Full docs

Graphs.SimpleGraphs.SimpleDiGraphMethod
SimpleDiGraph{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
source
Graphs.SimpleGraphs.SimpleDiGraphMethod
SimpleDiGraph(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
source
Graphs.SimpleGraphs.SimpleDiGraphMethod
SimpleDiGraph{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.

source
Graphs.SimpleGraphs.SimpleDiGraphMethod
SimpleDiGraph(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

SimpleDiGraphFromIterator

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
source
Graphs.SimpleGraphs.SimpleDiGraphMethod
SimpleDiGraph{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
source
Graphs.SimpleGraphs.SimpleDiGraphMethod
SimpleDiGraph(::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
source
Graphs.SimpleGraphs.SimpleDiGraphMethod
SimpleDiGraph{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
source
Graphs.SimpleGraphs.SimpleDiGraphFromIteratorMethod
SimpleDiGraphFromIterator(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
source
Graphs.SimpleGraphs.SimpleEdgeIterType
SimpleEdgeIter

The function edges returns a SimpleEdgeIter for AbstractSimpleGraphs. 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))
source
Graphs.SimpleGraphs.SimpleGraphMethod
SimpleGraph{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
source
Graphs.SimpleGraphs.SimpleGraphMethod
SimpleGraph(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
source
Graphs.SimpleGraphs.SimpleGraphMethod
SimpleGraph{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
source
Graphs.SimpleGraphs.SimpleGraphMethod
SimpleGraph{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.

source
Graphs.SimpleGraphs.SimpleGraphMethod
SimpleGraph(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

SimpleGraphFromIterator

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
source
Graphs.SimpleGraphs.SimpleGraphMethod
SimpleGraph(::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
source
Graphs.SimpleGraphs.SimpleGraphMethod
SimpleGraph{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
source
Graphs.SimpleGraphs.SimpleGraphFromIteratorMethod
SimpleGraphFromIterator(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
source
Graphs.SimpleGraphs.add_edge!Method
add_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
source
Graphs.SimpleGraphs.add_vertex!Method
add_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
source
Graphs.SimpleGraphs.adjMethod
adj(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.

source
Graphs.SimpleGraphs.badjMethod
badj(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.

source
Graphs.SimpleGraphs.rem_edge!Method
rem_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
source
Graphs.SimpleGraphs.rem_vertices!Method
rem_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
source
Graphs.SimpleGraphs.AbstractSimpleGraphType
AbstractSimpleGraph

An abstract type representing a simple graph structure. AbstractSimpleGraphs must have the following elements:

  • vertices::UnitRange{Integer}
  • fadjlist::Vector{Vector{Integer}}
  • ne::Integer
source
Graphs.SimpleGraphs.rem_vertex!Method
rem_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
source
Graphs.SimpleGraphs.throw_if_invalid_eltypeMethod
throw_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}.

source
Graphs.squashMethod
squash(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.

source