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

Graph — Method

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

dual_graph — Method

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 — Method

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 — Function

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 — Function

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)

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

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

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

julia> n_edges(g)
1

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> add_vertices!(g, 5);

julia> n_vertices(g)
7

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

julia> add_vertex!(g)
true

julia> n_vertices(g)
3

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

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

julia> n_edges(g)
1

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

julia> n_edges(g)
0

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

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

Auxiliary functions

adjacency_matrix — Method

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

julia> add_edge!(G,1,3)
true

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

julia> adjacency_matrix(G)
3×3 IncidenceMatrix
[2, 3]
[]
[]


julia> matrix(ZZ, adjacency_matrix(G))
[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)

julia> adjacency_matrix(G)
4×4 IncidenceMatrix
[2, 3]
[1, 4]
[1, 4]
[2, 3]


julia> matrix(ZZ, adjacency_matrix(G))
[0   1   1   0]
[1   0   0   1]
[1   0   0   1]
[0   1   1   0]

all_neighbors — Method

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> add_edge!(g, 1, 3);

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

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

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

automorphism_group_generators — Method

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)

complete_graph — Method

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 — Method

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)

degree — Method

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

edges — Method

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)

has_edge — Method

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

has_vertex — Method

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

laplacian_matrix — Method

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]

n_edges — Method

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

n_vertices — Method

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

inneighbors — Method

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> add_edge!(g, 1, 3);

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

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

julia> inneighbors(g, 1)
Int64[]

neighbors — Method

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> add_edge!(g, 1, 3);

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

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

outneighbors — Method

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> add_edge!(g, 1, 3);

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

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

julia> outneighbors(g, 4)
Int64[]

shortest_path_dijkstra — Function

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> add_edge!(g, 1, 2);

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

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

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

is_isomorphic — Method

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

is_isomorphic_with_permutation — Method

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

Edges

dst — Method

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

reverse — Method

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)

src — Method

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

Saving and loading

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_group — Method

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