Operators
Graphs.jl implements the following graph operators. In general, functions with two graph arguments will require them to be of the same type (either both SimpleGraph
or both SimpleDiGraph
).
Index
Base.getindex
Base.intersect
Base.join
Base.reverse
Base.reverse!
Base.size
Base.sum
Base.sum
Base.union
Graphs.cartesian_product
Graphs.complement
Graphs.compute_shifts
Graphs.crosspath
Graphs.difference
Graphs.egonet
Graphs.induced_subgraph
Graphs.merge_vertices
Graphs.merge_vertices!
Graphs.symmetric_difference
Graphs.tensor_product
SparseArrays.blockdiag
SparseArrays.sparse
Full docs
Base.getindex
— Methodg[iter]
Return the subgraph induced by iter
. Equivalent to induced_subgraph
(g, iter)[1]
.
Base.intersect
— Methodintersect(g, h)
Return a graph with edges that are only in both graph g
and graph h
.
Implementation Notes
This function may produce a graph with 0-degree vertices. Preserves the eltype of the input graph.
Examples
julia> using Graphs
julia> g1 = 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> g2 = SimpleDiGraph([0 1 0; 0 0 1; 1 0 0]);
julia> foreach(println, edges(intersect(g1, g2)))
Edge 1 => 2
Edge 2 => 3
Edge 3 => 1
Base.join
— Methodjoin(g, h)
Return a graph that combines graphs g
and h
using blockdiag
and then adds all the edges between the vertices in g
and those in h
.
Implementation Notes
Preserves the eltype of the input graph. Will error if the number of vertices in the generated graph exceeds the eltype.
Examples
julia> using Graphs
julia> g = join(star_graph(3), path_graph(2))
{5, 9} undirected simple Int64 graph
julia> collect(edges(g))
9-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
Edge 1 => 3
Edge 1 => 4
Edge 1 => 5
Edge 2 => 4
Edge 2 => 5
Edge 3 => 4
Edge 3 => 5
Edge 4 => 5
Base.reverse
— Functionreverse(g)
Return a directed graph where all edges are reversed from the original directed graph.
Implementation Notes
Preserves the eltype of the input graph.
Examples
julia> using Graphs
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> foreach(println, edges(reverse(g)))
Edge 1 => 3
Edge 2 => 1
Edge 3 => 2
Edge 4 => 3
Edge 4 => 5
Edge 5 => 4
Base.reverse!
— Functionreverse!(g)
In-place reverse of a directed graph (modifies the original graph). See reverse
for a non-modifying version.
Base.size
— Methodsize(g, i)
Return the number of vertices in g
if i
=1 or i
=2, or 1
otherwise.
Examples
julia> using Graphs
julia> g = cycle_graph(4);
julia> size(g, 1)
4
julia> size(g, 2)
4
julia> size(g, 3)
1
Base.sum
— Methodsum(g, i)
Return a vector of indegree (i
=1) or outdegree (i
=2) values for graph g
.
Examples
julia> using Graphs
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> sum(g, 2)
5-element Vector{Int64}:
1
1
2
1
1
julia> sum(g, 1)
5-element Vector{Int64}:
1
1
1
2
1
Base.sum
— Methodsum(g)
Return the number of edges in g
.
Examples
julia> using Graphs
julia> g = SimpleGraph([0 1 0; 1 0 1; 0 1 0]);
julia> sum(g)
2
Base.union
— Methodunion(g, h)
Return a graph that combines graphs g
and h
by taking the set union of all vertices and edges.
Implementation Notes
Preserves the eltype of the input graph. Will error if the number of vertices in the generated graph exceeds the eltype.
Examples
julia> using Graphs
julia> g = SimpleGraph(3); h = SimpleGraph(5);
julia> add_edge!(g, 1, 2);
julia> add_edge!(g, 1, 3);
julia> add_edge!(h, 3, 4);
julia> add_edge!(h, 3, 5);
julia> add_edge!(h, 4, 5);
julia> f = union(g, h);
julia> collect(edges(f))
5-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
Edge 1 => 3
Edge 3 => 4
Edge 3 => 5
Edge 4 => 5
Graphs.cartesian_product
— Methodcartesian_product(g, h)
Return the cartesian product of g
and h
.
Implementation Notes
Preserves the eltype of the input graph. Will error if the number of vertices in the generated graph exceeds the eltype.
Examples
julia> using Graphs
julia> g = cartesian_product(star_graph(3), path_graph(3))
{9, 12} undirected simple Int64 graph
julia> collect(edges(g))
12-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
Edge 1 => 4
Edge 1 => 7
Edge 2 => 3
Edge 2 => 5
Edge 2 => 8
Edge 3 => 6
Edge 3 => 9
Edge 4 => 5
Edge 5 => 6
Edge 7 => 8
Edge 8 => 9
Graphs.complement
— Methodcomplement(g)
Return the graph complement of a graph
Implementation Notes
Preserves the eltype
of the input graph.
Examples
julia> using Graphs
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> foreach(println, edges(complement(g)))
Edge 1 => 3
Edge 1 => 4
Edge 1 => 5
Edge 2 => 1
Edge 2 => 4
Edge 2 => 5
Edge 3 => 2
Edge 3 => 5
Edge 4 => 1
Edge 4 => 2
Edge 4 => 3
Edge 5 => 1
Edge 5 => 2
Edge 5 => 3
Graphs.compute_shifts
— Methodcompute_shifts(n::Int, x::AbstractArray)
Determine how many elements of x
are less than i
for all i
in 1:n
.
Graphs.crosspath
— Functioncrosspath(len::Integer, g::Graph)
Return a graph that duplicates g
len
times and connects each vertex with its copies in a path.
Implementation Notes
Preserves the eltype of the input graph. Will error if the number of vertices in the generated graph exceeds the eltype.
Examples
julia> using Graphs
julia> g = crosspath(3, path_graph(3))
{9, 12} undirected simple Int64 graph
julia> collect(edges(g))
12-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
Edge 1 => 4
Edge 2 => 3
Edge 2 => 5
Edge 3 => 6
Edge 4 => 5
Edge 4 => 7
Edge 5 => 6
Edge 5 => 8
Edge 6 => 9
Edge 7 => 8
Edge 8 => 9
Graphs.difference
— Methoddifference(g, h)
Return a graph with edges in graph g
that are not in graph h
.
Implementation Notes
Note that this function may produce a graph with 0-degree vertices. Preserves the eltype
of the input graph.
Examples
julia> using Graphs
julia> g1 = 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> g2 = SimpleDiGraph([0 1 0; 0 0 1; 1 0 0]);
julia> foreach(println, edges(difference(g1, g2)))
Edge 3 => 4
Edge 4 => 5
Edge 5 => 4
Graphs.egonet
— Methodegonet(g, v, d, distmx=weights(g))
Return the subgraph of g
induced by the neighbors of v
up to distance d
, using weights (optionally) provided by distmx
. This is equivalent to induced_subgraph
(g, neighborhood(g, v, d, dir=dir))[1].
Optional Arguments
dir=:out
: ifg
is directed, this argument specifies the edge direction
with respect to v
(i.e. :in
or :out
).
Graphs.induced_subgraph
— Methodinduced_subgraph(g, vlist)
induced_subgraph(g, elist)
Return the subgraph of g
induced by the vertices in vlist
or edges in elist
along with a vector mapping the new vertices to the old ones (the vertex i
in the subgraph corresponds to the vertex vmap[i]
in g
.)
The returned graph has length(vlist)
vertices, with the new vertex i
corresponding to the vertex of the original graph in the i
-th position of vlist
.
Usage Examples
julia> g = complete_graph(10)
julia> sg, vmap = induced_subgraph(g, 5:8)
julia> @assert g[5:8] == sg
julia> @assert nv(sg) == 4
julia> @assert ne(sg) == 6
julia> @assert vm[4] == 8
julia> sg, vmap = induced_subgraph(g, [2,8,3,4])
julia> @assert sg == g[[2,8,3,4]]
julia> elist = [Edge(1,2), Edge(3,4), Edge(4,8)]
julia> sg, vmap = induced_subgraph(g, elist)
julia> @assert sg == g[elist]
Graphs.merge_vertices!
— Methodmerge_vertices!(g, vs)
Combine vertices specified in vs
into single vertex whose index will be the lowest value in vs
. All edges connected to vertices in vs
connect to the new merged vertex.
Return a vector with new vertex values are indexed by the original vertex indices.
Implementation Notes
Supports SimpleGraph
only.
Examples
julia> using Graphs
julia> g = path_graph(5);
julia> collect(edges(g))
4-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
Edge 2 => 3
Edge 3 => 4
Edge 4 => 5
julia> merge_vertices!(g, [2, 3])
5-element Vector{Int64}:
1
2
2
3
4
julia> collect(edges(g))
3-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
Edge 2 => 3
Edge 3 => 4
Graphs.merge_vertices
— Methodmerge_vertices(g::AbstractGraph, vs)
Create a new graph where all vertices in vs
have been aliased to the same vertex minimum(vs)
.
Examples
julia> using Graphs
julia> g = path_graph(5);
julia> collect(edges(g))
4-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
Edge 2 => 3
Edge 3 => 4
Edge 4 => 5
julia> h = merge_vertices(g, [2, 3]);
julia> collect(edges(h))
3-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
Edge 2 => 3
Edge 3 => 4
Graphs.symmetric_difference
— Methodsymmetric_difference(g, h)
Return a graph with edges from graph g
that do not exist in graph h
, and vice versa.
Implementation Notes
Note that this function may produce a graph with 0-degree vertices. Preserves the eltype of the input graph. Will error if the number of vertices in the generated graph exceeds the eltype.
Examples
julia> using Graphs
julia> g = SimpleGraph(3); h = SimpleGraph(3);
julia> add_edge!(g, 1, 2);
julia> add_edge!(h, 1, 3);
julia> add_edge!(h, 2, 3);
julia> f = symmetric_difference(g, h);
julia> collect(edges(f))
3-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
Edge 1 => 3
Edge 2 => 3
Graphs.tensor_product
— Methodtensor_product(g, h)
Return the tensor product of g
and h
.
Implementation Notes
Preserves the eltype of the input graph. Will error if the number of vertices in the generated graph exceeds the eltype.
Examples
julia> using Graphs
julia> g = tensor_product(star_graph(3), path_graph(3))
{9, 8} undirected simple Int64 graph
julia> collect(edges(g))
8-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 5
Edge 1 => 8
Edge 2 => 4
Edge 2 => 6
Edge 2 => 7
Edge 2 => 9
Edge 3 => 5
Edge 3 => 8
SparseArrays.blockdiag
— Methodblockdiag(g, h)
Return a graph with $|V(g)| + |V(h)|$ vertices and $|E(g)| + |E(h)|$ edges where the vertices and edges from graph h
are appended to graph g
.
Implementation Notes
Preserves the eltype of the input graph. Will error if the number of vertices in the generated graph exceeds the eltype
.
Examples
julia> using Graphs
julia> g1 = 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> g2 = SimpleDiGraph([0 1 0; 0 0 1; 1 0 0]);
julia> blockdiag(g1, g2)
{8, 9} directed simple Int64 graph
julia> foreach(println, edges(blockdiag(g1, g2)))
Edge 1 => 2
Edge 2 => 3
Edge 3 => 1
Edge 3 => 4
Edge 4 => 5
Edge 5 => 4
Edge 6 => 7
Edge 7 => 8
Edge 8 => 6
SparseArrays.sparse
— Methodsparse(g)
Return the default adjacency matrix of g
.