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> nv(g)
5

julia> ne(g)
0

dualgraph — Method

dualgraph(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 = dualgraph(c);

julia> nv(g)
6

julia> ne(g)
12

edgegraph — Method

edgegraph(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.

Examples

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

julia> c = cube(3);

julia> g = edgegraph(c);

julia> nv(g)
8

julia> ne(g)
12

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.

Examples

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

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

julia> ne(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.

Examples

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

julia> nv(g)
2

julia> add_vertices!(g, 5);

julia> nv(g)
7

add_vertex! — Method

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

Add a vertex to the graph g. The return value is the new vertex.

Examples

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

julia> nv(g)
2

julia> add_vertex!(g)
3

julia> nv(g)
3

rem_edge! — Method

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

Remove edge (s,t) from the graph g.

Examples

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

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

julia> ne(g)
1

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

julia> ne(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.

Examples

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

julia> nv(g)
2

julia> rem_vertex!(g, 1)

julia> nv(g)
1

Auxiliary functions

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)

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 = edgegraph(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 = edgegraph(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 = edgegraph(triangle);

julia> has_vertex(g, 1)
true

julia> has_vertex(g, 4)
false

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

ne — Method

ne(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 = edgegraph(c);

julia> ne(g)
12

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

nv — Method

nv(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 = edgegraph(c);

julia> nv(g)
8

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

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.