SimpleGraphs formats

SimpleDiGraph{T}

A type representing a directed graph.

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

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

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.

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

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

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

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

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

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

SimpleGraph{T}

A type representing an undirected graph.

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

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

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

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.

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

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

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

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

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

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

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.

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.

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

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

is_directed(g)

Return true if g is a directed graph.

AbstractSimpleGraph

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

• vertices::UnitRange{Integer}
• fadjlist::Vector{Vector{Integer}}
• ne::Integer

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

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}.

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.