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

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.