Graphs

Introduction

Graphs are a fundamental object within all of mathematics and computer science. A graph consists of two sets of data:

• a finite set $V := \{1,\ldots,n\}$ of vertices; and
• a finite set $E \subseteq V\times V$ of edges.

There are two types of graphs, directed and undirected. For a directed graph the elements of $E$ are considered to be ordered pairs, for an undirected graph the elements of $E$ are unordered pairs or rather sets with two elements.

The interface is modeled alongside the Graphs.jl interface to allow for easier integration elsewhere.

Warning

The mechanism for removing a vertex is slightly different in out implementation to the Graphs.jl implementation: In Graphs.jl first the vertex to be removed is swapped with the last vertex, then the last vertex is removed. In our implementation, the vertex is removed and all subsequent vertices have their labels changed. Hence edges can be different in the two implementations after removing a vertex.

Construction

GraphMethod
Graph{T}(nverts::Int64) where {T <: Union{Directed, Undirected}}

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

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
source
dual_graphMethod
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
source
vertex_edge_graphMethod
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
source
graph_from_adjacency_matrixFunction
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]

Directed graph with 2 nodes and the following edges:
(2, 1)

Undirected graph with 2 nodes and the following edges:
(2, 1)

source
graph_from_edgesFunction
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}}

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

Modifying graphs

add_edge!Method
add_edge!(g::Graph{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.

Examples

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

true

false

julia> n_edges(g)
1
source
add_vertices!Method
add_vertices!(g::Graph{T}, n::Int64) where {T <: Union{Directed, Undirected}}

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> n_vertices(g)
7
source
add_vertex!Method
add_vertex!(g::Graph{T}) where {T <: Union{Directed, Undirected}}

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

true

julia> n_vertices(g)
3
source
rem_edge!Method
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}}

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.

Examples

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

true

julia> n_edges(g)
1

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

julia> n_edges(g)
0
source
rem_vertex!Method
rem_vertex!(g::Graph{T}, v::Int64) where {T <: Union{Directed, Undirected}}

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
source
rem_vertices!Method
rem_vertices!(g::Graph{T}, a::AbstractArray{Int64}) where {T <: Union{Directed, Undirected}}

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
source

Auxiliary functions

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

Return an unsigned (boolean) adjacency matrix representing a graph g. If g is undirected, the adjacency matrix will be symmetric. For g being directed, the adjacency matrix has a 1 at (u,v) if there is an edge u->v.

Examples

Adjacency matrix for a directed graph:

julia> G = Graph{Directed}(3)
Directed graph with 3 nodes and no edges

true

true

3×3 IncidenceMatrix
[2, 3]
[]
[]

[0   1   1]
[0   0   0]
[0   0   0]

Adjacency matrix for an undirected graph:

julia> G = vertex_edge_graph(cube(2))
Undirected graph with 4 nodes and the following edges:
(2, 1)(3, 1)(4, 2)(4, 3)

4×4 IncidenceMatrix
[2, 3]
[1, 4]
[1, 4]
[2, 3]

[0   1   1   0]
[1   0   0   1]
[1   0   0   1]
[0   1   1   0]
source
all_neighborsMethod
all_neighbors(g::Graph{T}, v::Int64) where {T <: Union{Directed, Undirected}}

Return all vertices of a graph g that are connected to the vertex v via an edge, independent of the edge direction.

Examples

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

julia> all_neighbors(g, 3)
2-element Vector{Int64}:
1
4

julia> all_neighbors(g, 4)
1-element Vector{Int64}:
3
source
automorphism_group_generatorsMethod
automorphism_group_generators(g::Graph{T}) where {T <: Union{Directed, Undirected}}

Return generators of the automorphism group of the graph g.

Examples

julia> g = complete_graph(4);

julia> automorphism_group_generators(g)
3-element Vector{PermGroupElem}:
(3,4)
(2,3)
(1,2)
source
complete_graphMethod
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)
source
complete_bipartite_graphMethod
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)
source
degreeMethod
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.

Examples

julia> g = vertex_edge_graph(icosahedron());

julia> degree(g, 1)
5
source
edgesMethod
edges(g::Graph{T}) where {T <: Union{Directed, Undirected}}

Return an iterator over the edges of the graph g.

Examples

A triangle has three edges.

julia> triangle = simplex(2);

julia> g = vertex_edge_graph(triangle);

julia> collect(edges(g))
3-element Vector{Edge}:
Edge(2, 1)
Edge(3, 1)
Edge(3, 2)
source
has_edgeMethod
has_edge(g::Graph{T}, source::Int64, target::Int64) where {T <: Union{Directed, Undirected}}

Check for an edge in a graph.

Examples

Check for the edge $1\to 2$ in the edge graph of a triangle.

julia> triangle = simplex(2);

julia> g = vertex_edge_graph(triangle);

julia> has_edge(g, 1, 2)
true
source
has_vertexMethod
has_vertex(g::Graph{T}, v::Int64) where {T <: Union{Directed, Undirected}}

Check for a vertex in a graph.

Examples

The edge graph of a triangle only has 3 vertices.

julia> triangle = simplex(2);

julia> g = vertex_edge_graph(triangle);

julia> has_vertex(g, 1)
true

julia> has_vertex(g, 4)
false
source
laplacian_matrixMethod
laplacian_matrix(g::Graph{T}) where {T <: Union{Directed, Undirected}}

Return the Laplacian matrix of the graph g. The Laplacian matrix of a graph can be written as the difference of D, where D is a quadratic matrix with the degrees of g on the diagonal, and the adjacency matrix of g. For an undirected graph, the Laplacian matrix is symmetric.

Examples

julia> G = vertex_edge_graph(cube(2))
Undirected graph with 4 nodes and the following edges:
(2, 1)(3, 1)(4, 2)(4, 3)

julia> laplacian_matrix(G)
[ 2   -1   -1    0]
[-1    2    0   -1]
[-1    0    2   -1]
[ 0   -1   -1    2]
source
n_edgesMethod
n_edges(g::Graph{T}) where {T <: Union{Directed, Undirected}}

Return the number of edges of a graph.

Examples

The edge graph of the cube has 12 edges just like the cube itself.

julia> c = cube(3);

julia> g = vertex_edge_graph(c);

julia> n_edges(g)
12
source
n_verticesMethod
n_vertices(g::Graph{T}) where {T <: Union{Directed, Undirected}}

Return the number of vertices of a graph.

Examples

The edge graph of the cube has eight vertices, just like the cube itself.

julia> c = cube(3);

julia> g = vertex_edge_graph(c);

julia> n_vertices(g)
8
source
inneighborsMethod
inneighbors(g::Graph{T}, v::Int64) where {T <: Union{Directed, Undirected}}

Return the vertices of a graph g that have an edge going towards v. For an undirected graph, all neighboring vertices are returned.

Examples

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

julia> inneighbors(g, 3)
1-element Vector{Int64}:
1

julia> inneighbors(g, 1)
Int64[]
source
neighborsMethod
neighbors(g::Graph{T}, v::Int64) where {T <: Union{Directed, Undirected}}

Return the neighboring vertices of a vertex v in a graph g. If the graph is directed, the neighbors reachable via outgoing edges are returned.

Examples

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

julia> neighbors(g, 3)
1-element Vector{Int64}:
4
source
outneighborsMethod
outneighbors(g::Graph{T}, v::Int64) where {T <: Union{Directed, Undirected}}

Return the vertices of a graph g that are target of an edge coming from v. For an undirected graph, all neighboring vertices are returned.

Examples

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

julia> outneighbors(g, 3)
1-element Vector{Int64}:
4

julia> outneighbors(g, 4)
Int64[]
source
shortest_path_dijkstraFunction
shortest_path_dijkstra(g::Graph{T}, s::Int64, t::Int64; reverse::Bool=false) where {T <: Union{Directed, Undirected}}

Compute the shortest path between two vertices in a graph using Dijkstra's algorithm. All edges are set to have a length of 1. The optional parameter indicates whether the edges should be considered reversed.

Examples

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

julia> shortest_path_dijkstra(g, 3, 1)
2-element Vector{Int64}:
3
1

julia> shortest_path_dijkstra(g, 1, 3)
3-element Vector{Int64}:
1
2
3

julia> shortest_path_dijkstra(g, 3, 1; reverse=true)
3-element Vector{Int64}:
3
2
1
source
is_isomorphicMethod
is_isomorphic(g1::Graph{T}, g2::Graph{T}) where {T <: Union{Directed, Undirected}}

Checks if the graph g1 is isomorphic to the graph g2.

Examples

julia> is_isomorphic(vertex_edge_graph(simplex(3)), dual_graph(simplex(3)))
true

julia> is_isomorphic(vertex_edge_graph(cube(3)), dual_graph(cube(3)))
false
source
is_isomorphic_with_permutationMethod
is_isomorphic_with_permutation(G1::Graph, G2::Graph) -> Bool, Vector{Int}

Return whether G1 is isomorphic to G2 as well as a permutation of the nodes of G1 such that both graphs agree.

Examples

julia> is_isomorphic_with_permutation(vertex_edge_graph(simplex(3)), dual_graph(simplex(3)))
(true, [1, 2, 3, 4])

source

Edges

dstMethod
dst(e::Edge)

Return the destination of an edge.

Examples

julia> g = complete_graph(2);

julia> E = collect(edges(g));

julia> e = E[1]
Edge(2, 1)

julia> dst(e)
1
source
reverseMethod
reverse(e::Edge)

Return the edge in the opposite direction of the edge e.

Examples

julia> g = complete_graph(2);

julia> E = collect(edges(g));

julia> e = E[1]
Edge(2, 1)

julia> reverse(e)
Edge(1, 2)
source
srcMethod
src(e::Edge)

Return the source of an edge.

Examples

julia> g = complete_graph(2);

julia> E = collect(edges(g));

julia> e = E[1]
Edge(2, 1)

julia> src(e)
2
source

Objects of type Graph can be saved to a file and loaded with the methods load and save. The file is in JSON format and contains the underlying polymake object. In particular, this file can now be read by both polymake and OSCAR.

Quantum Automorphisms

quantum_automorphism_groupMethod
quantum_automorphism_group(G::Graph{Undirected})

Return the ideal that defines the quantum automorphism group of the undirected graph G.

Examples

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

julia> qAut = quantum_automorphism_group(G);

julia> length(gens(qAut))
184
source