Graphs

graph(::Type{T}, nverts::Int64) where {T <: Union{Directed, Mixed, Undirected}}

Construct a graph on nverts vertices and no edges. T indicates whether the graph should be Directed, Undirected or Mixed.

Examples

Make a directed graph with 5 vertices and print the number of nodes and edges.

julia> g = graph(Directed, 5);

julia> n_vertices(g)
5

julia> n_edges(g)
0

dual_graph(p::Polyhedron)

Return the dual graph of a Polyhedron, vertices of the graph correspond to facets of the polyhedron and there is an edge between two vertices if the corresponding facets are neighboring, meaning their intersection is a codimension 2 face of the polyhedron.

For bounded polyhedra containing 0 in the interior this is the same as the edge graph the polar dual polyhedron.

Examples

Construct the dual graph of the cube. This is the same as the edge graph of the octahedron, so it has 6 vertices and 12 edges.

julia> c = cube(3);

julia> g = dual_graph(c);

julia> n_vertices(g)
6

julia> n_edges(g)
12

vertex_edge_graph(p::Polyhedron)

Return the edge graph of a Polyhedron, vertices of the graph correspond to vertices of the polyhedron, there is an edge between two vertices if the polyhedron has an edge between the corresponding vertices. The resulting graph is Undirected. If the polyhedron has lineality, then it has no vertices or bounded edges, so the vertex_edge_graph will be the empty graph. In this case, the keyword argument can be used to consider the polyhedron modulo its lineality space.

Examples

Construct the edge graph of the cube. Like the cube it has 8 vertices and 12 edges.

julia> c = cube(3);

julia> g = vertex_edge_graph(c);

julia> n_vertices(g)
8

julia> n_edges(g)
12

graph_from_adjacency_matrix(::Type{T}, G) where {T <:Union{Directed, Undirected}}

Return the graph with adjacency matrix G.

This means that the nodes $i, j$ are connected by an edge if and only if $G_{i,j}$ is one. In the undirected case, it is assumed that $i > j$ i.e. the upper triangular part of $G$ is ignored.

Examples

julia> G = ZZ[0 0; 1 0]
[0   0]
[1   0]

julia> graph_from_adjacency_matrix(Directed, G)
Directed graph with 2 nodes and the following edges:
(2, 1)

julia> graph_from_adjacency_matrix(Undirected, G)
Undirected graph with 2 nodes and the following edges:
(2, 1)

graph_from_edges(edges::Vector{Vector{Int}})
graph_from_edges(::Type{T}, edges::Vector{Vector{Int}}, n_vertices::Int=-1) where {T <:Union{Directed, Undirected}}
graph_from_edges(::Type{Mixed}, directed_edges::Vector{Vector{Int}}, undirected_edges::Vector{Vector{Int}}; n_vertices=-1)
graph_from_edges(::Type{Mixed}, directed_edges::Vector{Edge}, undirected_edges::Vector{Edge}; n_vertices=-1)

Create a graph from a vector of edges. There is an optional input for number of vertices, graph_from_edges will ignore any negative integers and throw an error when the input is less than the maximum vertex index in edges.

Examples

julia> G = graph_from_edges([[1,3],[3,5],[4,5],[2,4],[2,3]])
Undirected graph with 5 nodes and the following edges:
(3, 1)(3, 2)(4, 2)(5, 3)(5, 4)

julia> G = graph_from_edges(Directed, [[1,3]], 4)
Directed graph with 4 nodes and the following edges:
(1, 3)

julia> g = graph_from_edges(Mixed, [[1,3],[3,5]],[[4,5],[2,4],[2,3]])
Mixed graph with 5 nodes and the following
Directed edges:
(1, 3)(3, 5)
Undirected edges:
(3, 2)(4, 2)(5, 4)

julia> g1 = graph_from_edges(Directed, [[1, 2], [3, 4]])
Directed graph with 4 nodes and the following edges:
(1, 2)(3, 4)

julia> g2 = graph_from_edges(Undirected, [[1, 4], [3, 2]])
Undirected graph with 4 nodes and the following edges:
(3, 2)(4, 1)

julia> graph_from_edges(Mixed, edges(g1), edges(g2))
Mixed graph with 4 nodes and the following
Directed edges:
(1, 2)(3, 4)
Undirected edges:
(3, 2)(4, 1)

graph_from_labeled_edges(edge_labels::Dict{NTuple{Int}, S}, vertex_labels::Union{Nothing, Dict{Int, S}}=nothing; name::Symbol=:label, n_vertices::Int=-1)
graph_from_labeled_edges(::Type{T}, edge_labels::Dict{NTuple{Int}, S}, vertex_labels::Union{Nothing, Dict{Int, S}}=nothing; name::Symbol=:label, n_vertices::Int=-1) where {T <:Union{Directed, Undirected}, S, U}

Create a graph with a labeling on the edges and optionally vertices. The graph is constructed from the edges and an optional number of vertices, see graph_from_edges. The default name of the labeling on the graph is label but any Symbol can be passed using the name keyword argument. The labeling can be accessed as a property of the graph, the property is exactly the name passed to the name keyword argument. See label! to add additional labels to the graph.

Examples

julia> G = graph_from_labeled_edges(Directed, Dict((1, 2) => 1, (2, 3) => 4))
Directed graph with 3 nodes and the following labeling(s):
label: label
(1, 2) -> 1
(2, 3) -> 4

julia> G.label[1, 2]
1

julia> edge = collect(edges(G))[2]
Edge(2, 3)

julia> G.label[edge]
4

julia> K = graph_from_labeled_edges(Dict((1, 2) => "blue", (2, 3) => "green"),
                                    Dict(1 => "red", 2 => "red", 3 => "yellow"); name=:color)
Undirected graph with 3 nodes and the following labeling(s):
label: color
(2, 1) -> blue
(3, 2) -> green
1 -> red
2 -> red
3 -> yellow

julia> K.color[1]
"red"

induced_subgraph(g::Graph{T}, v::AbstractVector{<:IntegerUnion}; copy_labelings::Bool=true) where {T <: Union{Directed, Undirected}}

Create a new graph induced by g on the given subset of vertices. Please note that the subset of vertices will be sorted ascending before being used. The original vertices can be identified with the vertexlabels labeling.

Unless the keyword argument copy_labelings is set to false, all labelings will be transformed and copied to the subgraph.

Examples

julia> g = graph_from_edges([[1, 2], [2, 3], [1, 3], [2, 4], [3, 4]])
Undirected graph with 4 nodes and the following edges:
(2, 1)(3, 1)(3, 2)(4, 2)(4, 3)

julia> induced_subgraph(g, 2:4)
Undirected graph with 3 nodes and the following edges:
(2, 1)(3, 1)(3, 2)
and the following labeling(s):
label: vertexlabels
1 -> 2
2 -> 3
3 -> 4

add_edge!(g::Graph{T}, s::Int64, t::Int64) where {T <: Union{Directed, Undirected}}
add_edge!(mg::MixedGraph, ::Type{T}, s::Int64, t::Int64) where {T <: Union{Directed, Undirected}}

Add edge (s,t) to the graph g. Return true if a new edge (s,t) was added, false otherwise. For MixedGraph the second input determines which component to apply the operation to.

Examples

julia> g = Graph{Directed}(2);

julia> add_edge!(g, 1, 2)
true

julia> add_edge!(g, 1, 2)
false

julia> n_edges(g)
1

julia> mg = graph(Mixed, 3)
Mixed graph with 3 nodes and no edges

julia> add_edge!(mg, Directed, 1, 2)
true

julia> add_edge!(mg, Directed, 1, 2)
false

julia> n_edges(mg)
1

julia> add_edge!(mg, Undirected, 1, 3)
true

julia> n_edges(mg)
2

add_vertices!(g::Graph{T}, n::Int64) where {T <: Union{Directed, Undirected}}
add_vertices!(mg::MixedGraph, n::Int64)

Add a n new vertices to the graph g. Return the number of vertices that were actually added to the graph g.

Examples

julia> g = Graph{Directed}(2);

julia> n_vertices(g)
2

julia> add_vertices!(g, 5);

julia> n_vertices(g)
7

add_vertex!(g::Graph{T}) where {T <: Union{Directed, Undirected}}
add_vertex!(mg::MixedGraph)

Add a vertex to the graph g. Return true if there a new vertex was actually added.

Examples

julia> g = Graph{Directed}(2);

julia> n_vertices(g)
2

julia> add_vertex!(g)
true

julia> n_vertices(g)
3

rem_edge!(g::Graph{T}, s::Int64, t::Int64) where {T <: Union{Directed, Undirected}}
rem_edge!(g::Graph{T}, e::Edge) where {T <: Union{Directed, Undirected}}
rem_edge!(g::MixedGraph, ::Type{T}, s::Int64, t::Int64) where {T <: Union{Directed, Undirected}}
rem_edge!(g::MixedGraph, ::Type{T}, e::Edge) where {T <: Union{Directed, Undirected}}

Remove edge (s,t) from the graph g. Return true if there was an edge from s to t and it got removed, false otherwise. For MixedGraph the second input determines which component to apply the operation to.

Examples

julia> g = Graph{Directed}(2);

julia> add_edge!(g, 1, 2)
true

julia> n_edges(g)
1

julia> rem_edge!(g, 1, 2)
true

julia> n_edges(g)
0

julia> mg = graph(Mixed, 2);

julia> add_edge!(mg, Directed, 1, 2)
true

julia> n_edges(mg)
1

julia> rem_edge!(mg, Directed, 1, 2)
true

julia> add_edge!(mg, Undirected, 1, 2)
true

julia> n_edges(mg)
1

julia> rem_edge!(mg, Undirected, 1, 2)
true

julia> n_edges(mg)
0

rem_vertex!(g::Graph{T}, v::Int64) where {T <: Union{Directed, Undirected}}
rem_vertex!(mg::MixedGraph, v::Int64)

Remove the vertex v from the graph g. Return true if node v existed and was actually removed, false otherwise. Please note that this will shift the indices of the vertices with index larger than v, but it will preserve the vertex ordering.

Examples

julia> g = Graph{Directed}(2);

julia> n_vertices(g)
2

julia> rem_vertex!(g, 1)
true

julia> n_vertices(g)
1

rem_vertices!(g::Graph{T}, a::AbstractArray{Int64}) where {T <: Union{Directed, Undirected}}
rem_vertices!(mg::MixedGraph, a::AbstractVector)

Remove the vertices in a from the graph g. Return true if at least one vertex was removed. Please note that this will shift the indices of some of the remaining vertices, but it will preserve the vertex ordering.

Examples

julia> g = Graph{Directed}(2);

julia> n_vertices(g)
2

julia> rem_vertices!(g, [1, 2])
true

julia> n_vertices(g)
0

label!(G::Graph{T}, edge_labels::Union{Dict{Tuple{Int, Int}, Union{String, Int}}, Nothing}, vertex_labels::Union{Dict{Int, Union{String, Int}}, Nothing}=nothing; name::Symbol=:label) where {T <: Union{Directed, Undirected}}

Given a graph G, add labels to the edges and optionally to the vertices with the given name.

julia> G = graph_from_edges(Directed, [[1, 2], [2, 3]])
Directed graph with 3 nodes and the following edges:
(1, 2)(2, 3)

julia> label!(G, Dict((1, 2) => 1), nothing; name=:color)
Directed graph with 3 nodes and the following labeling(s):
label: color
(1, 2) -> 1
(2, 3) -> 0

julia> G = graph_from_labeled_edges(Undirected, Dict((1, 2) => 1, (2, 3) => 2, (1, 3) => 1), nothing; name=:color)
Undirected graph with 3 nodes and the following labeling(s):
label: color
(2, 1) -> 1
(3, 1) -> 1
(3, 2) -> 2

julia> label!(G, nothing, Dict(1 => 1); name=:shading)
Undirected graph with 3 nodes and the following labeling(s):
label: color
(2, 1) -> 1
(3, 1) -> 1
(3, 2) -> 2
label: shading
1 -> 1
2 -> 0
3 -> 0

degree(g::Graph{T} [, v::Int64]) where {T <: Union{Directed, Undirected}}

Return the degree of the vertex v in the graph g. If v is missing, return the list of degrees of all vertices. If the graph is directed, only neighbors reachable via outgoing edges are counted.

See also indegree and outdegree for directed graphs.

Examples

julia> g = vertex_edge_graph(icosahedron());

julia> degree(g, 1)
5

indegree(g::Graph{Directed} [, v::Int64])

Return the indegree of the vertex v in the directed graph g. If v is missing, return the list of indegrees of all vertices.

Examples

julia> g = Graph{Directed}(5);

julia> add_edge!(g, 1, 3);

julia> add_edge!(g, 3, 4);

julia> indegree(g, 1)
0

julia> indegree(g)
5-element Vector{Int64}:
 0
 0
 1
 1
 0

outdegree(g::Graph{Directed} [, v::Int64])

Return the outdegree of the vertex v in the directed graph g. If v is missing, return the list of outdegrees of all vertices.

Examples

julia> g = Graph{Directed}(5);

julia> add_edge!(g, 1, 3);

julia> add_edge!(g, 3, 4);

julia> outdegree(g, 1)
1

julia> outdegree(g)
5-element Vector{Int64}:
 1
 0
 1
 0
 0

leaves(G::Graph{Directed})

Return the indices of the leaves of the a Directed{Graph}.

Examples

julia> G = graph_from_edges(Directed, [[1, 2], [1, 3], [1, 4]]);

julia> leaves(G)
3-element Vector{Int64}:
 2
 3
 4

is_connected(g::Graph{Undirected})

Check if the undirected graph g is connected.

Examples

julia> g = Graph{Undirected}(3);

julia> is_connected(g)
false

julia> add_edge!(g, 1, 2);

julia> add_edge!(g, 2, 3);

julia> is_connected(g)
true

connected_components(g::Graph{Undirected})

Return the connected components of an undirected graph g.

Examples

julia> g = Graph{Undirected}(2);

julia> add_edge!(g, 1, 2);

julia> connected_components(g)
1-element Vector{Vector{Int64}}:
 [1, 2]

connectivity(g::Graph{Undirected})

Return the connectivity of the undirected graph g.

Examples

julia> g = complete_graph(3);

julia> connectivity(g)
2

julia> rem_edge!(g, 2, 3);

julia> connectivity(g)
1

julia> rem_edge!(g, 1, 3);

julia> connectivity(g)
0

is_weakly_connected(g::Graph{Directed})

Check if the directed graph g is weakly connected.

Examples

julia> g = Graph{Directed}(2);

julia> add_edge!(g, 1, 2);

julia> is_weakly_connected(g)
true

is_strongly_connected(g::Graph{Directed})

Check if the directed graph g is strongly connected.

Examples

julia> g = Graph{Directed}(2);

julia> add_edge!(g, 1, 2);

julia> is_strongly_connected(g)
false

julia> add_edge!(g, 2, 1);

julia> is_strongly_connected(g)
true

weakly_connected_components(g::Graph{Directed})

Return the weakly connected components of a directed graph g.

Examples

julia> g = Graph{Directed}(2);

julia> add_edge!(g, 1, 2);

julia> weakly_connected_components(g)
1-element Vector{Vector{Int64}}:
 [1, 2]

diameter(g::Graph{T}) where {T <: Union{Directed, Undirected}}

Return the diameter of a (strongly) connected (di-)graph g.

Examples

julia> g = Graph{Directed}(2);

julia> add_edge!(g, 1, 2);

julia> weakly_connected_components(g)
1-element Vector{Vector{Int64}}:
 [1, 2]

complete_graph(n::Int64)

Assemble the undirected complete graph on n nodes.

Examples

julia> g = complete_graph(3);

julia> collect(edges(g))
3-element Vector{Edge}:
 Edge(2, 1)
 Edge(3, 1)
 Edge(3, 2)

complete_bipartite_graph(n::Int64, m::Int64)

Assemble the undirected complete bipartite graph between n and m nodes.

Examples

julia> g = complete_bipartite_graph(2,2);

julia> collect(edges(g))
4-element Vector{Edge}:
 Edge(3, 1)
 Edge(3, 2)
 Edge(4, 1)
 Edge(4, 2)

petersen_graph()

Construct and return the Petersen graph as a simple undirected graph.

clebsch_graph()

Construct and return the 5-regular Clebsch graph.

The Clebsch graph is a strongly regular graph with 16 vertices and 40 edges. It is triangle-free and has degree 5.