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"

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

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]

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

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

Return the vertex indices of a graph.

Examples

The edge graph of the cube has eight vertices, numbered 1 to 8.

julia> c = cube(3);

julia> g = vertex_edge_graph(c);

julia> vertices(g)
1:8

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

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)

julia> mg = 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> collect(edges(mg, Directed))
2-element Vector{Edge}:
 Edge(1, 3)
 Edge(3, 5)

has_edge(g::Graph{T}, source::Int64, target::Int64) where {T <: Union{Directed, Undirected}}
has_edge(g::MixedGraph, ::Type{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

julia> mg = 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> has_edge(mg, Directed, 1, 3)
true

julia> has_edge(mg, Undirected, 1, 3)
false

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

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(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(g::Graph{T}) where {T <: Union{Directed, Undirected}}
n_edges(g::MixedGraph)

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

signed_incidence_matrix(g::Graph)

Return a signed incidence matrix representing a graph g. If g is directed, sources will have sign -1 and targest will have sign +1. If g is undirected, vertices of larger index will have sign -1 and vertices of smaller index will have sign +1.

Examples

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

julia> add_edge!(g,1,2); add_edge!(g,2,3); add_edge!(g,3,4); add_edge!(g,4,5); add_edge!(g,5,1);

julia> signed_incidence_matrix(g)
5×5 Matrix{Int64}:
 -1   0   0   0   1
  1  -1   0   0   0
  0   1  -1   0   0
  0   0   1  -1   0
  0   0   0   1  -1

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

julia> add_edge!(g,1,2); add_edge!(g,2,3); add_edge!(g,3,4); add_edge!(g,4,5); add_edge!(g,5,1);

julia> signed_incidence_matrix(g)
5×5 Matrix{Int64}:
  1   0   0   1   0
 -1   1   0   0   0
  0  -1   1   0   0
  0   0  -1   0   1
  0   0   0  -1  -1

is_isomorphic(g1::Graph{T}, g2::Graph{T}) where {T <: Union{Directed, Undirected}}

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

is_bipartite(g::Graph{Undirected})

Return true if the undirected graph g is bipartite.

Examples

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

julia> is_bipartite(g)
true

maximal_cliques(g::Graph{Undirected})

Returns the maximal cliques of a graph g as a Set{Set{Int}}.

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> typeof(maximal_cliques(g))
Set{Set{Int64}}

julia> sort.(collect.(maximal_cliques(g)))
2-element Vector{Vector{Int64}}:
 [1, 2, 3]
 [2, 3, 4]

labelings(G::Graph)

Return the names of all labelings of a graph G as a Vector{Symbol}.

Examples

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

julia> labelings(G)
1-element Vector{Symbol}:
 :color

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

visualize(G::Graph{<:Union{Polymake.Directed, Polymake.Undirected}}; backend::Symbol=:threejs, filename::Union{Nothing, String}=nothing, kwargs...)

Visualize a graph, see visualize for details on the keyword arguments.

The backend keyword argument allows the user to pick between a Three.js visualization by default, or passing :tikz for a TikZ visualization. The filename keyword argument will write visualization code to the filename location, this will be html for :threejs backend or TikZ code for :tikz. If the graph G has a labeling :color (see label!) then the visualization will use these colors to color the graph.

Possible color labelings include RGB values of the form "255 0 255" or "#ff00ff", as well as the following named colors as strings: polymakeorange, polymakegreen, white, purple, cyan, darkolivegreen, indianred, plum1, red, lightslategrey, yellow, orange, salmon1, azure, green, gray, midnightblue, pink, magenta, blue, lavenderblush, chocolate1, lightgreen, black.

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