Graph Algorithms¶
Graphs.jl
implements a collection of classic graph algorithms:
- graph traversal with visitor support: BFS, DFS, MAS
- cycle detection
- connected components
- topological sorting
- shortest paths: Dijkstra, Floyd-Warshall, A*
- minimum spanning trees: Prim, Kruskal
- flow: Minimum Cut
- random graph generation
- more algorithms are being implemented
Graph Traversal¶
Graph traversal refers to a process that traverses vertices of a graph following certain order (starting from user-input sources). This package implements three traversal schemes: breadth-first, depth-first, and Maximum-Adjacency.
During traveral, each vertex maintains a status (also called color), which is an integer value defined as below:
color = 0
: the vertex has not been encountered (i.e. discovered)color = 1
: the vertex has been discovered and remains opencolor = 2
: the vertex has been closed (i.e. all its neighbors have been examined)
-
traverse_graph
(graph, alg, source, visitor[, colormap])¶ Parameters: - graph – The input graph, which must implement
vertex_map
andadjacency_list
. - alg – The algorithm of traveral, which can be either
BreadthFirst()
orDepthFirst()
. - source – The source vertex (or vertices). The traversal starts from here.
- visitor – The visitor which performs certain operations along the traversal.
- colormap – An integer vector that indicates the status of each vertex. If this is input by the user, the status will be written to the input vector, otherwise an internal color vector will be created.
- graph – The input graph, which must implement
Here, visitor
must be an instance of a sub-type of AbstractGraphVisitor
. A specific graph visitor type can choose to implement some or all of the following methods.
-
discover_vertex!(visitor, v)
invoked when a vertex
v
is encountered for the first time. This function should return whether to continue traversal.
-
open_vertex!(visitor, v)
invoked when a vertex
v
is about to examinev
‘s neighbors.
-
examine_neighbor!(visitor, u, v, color, ecolor)
invoked when a neighbor/out-going edge is examined. Here
color
is the status ofv
, andecolor
is the status of the outgoing edge. Edge statuses are currently only considered by depth-first search.
-
close_vertex!(visitor, v)
invoked when all neighbors of
v
has been examined.
If a method of these is not implemented, it will automatically fallback to no-op. The package provides some pre-defined visitor types:
TrivialGraphVisitor
: all methods are no-op.VertexListVisitor
: it has a fieldvertices
, which is a vector comprised of vertices in the order of being discovered.LogGraphVisitor
: it prints message to show the progress of the traversal.
Many graph algorithms can be implemented based on graph traversal through certain visitors or by using the colormap in certain ways. For example, in this package, topological sorting, connected components, and cycle detection are all implemented using traverse_graph
with specifically designed visitors.
Cycle detection¶
In graph theory, a cycle is defined to be a path that starts from some vertex v
and ends up at v
.
-
test_cyclic_by_dfs
(g)¶ Tests whether a graph contains a cycle through depth-first search. It returns
true
when it finds a cycle, otherwisefalse
. Here,g
must implementvertex_list
,vertex_map
, andadjacency_list
.
Connected components¶
In graph theory, a connected component (in an undirected graph) refers to a subset of vertices such that there exists a path between any pair of them.
-
connected_components
(g)¶ Returns a vector of components, where each component is represented by a vector of vertices. Here,
g
must be an undirected graph, and implementvertex_list
,vertex_map
, andadjacency_list
.
Cliques¶
In graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. A maximal clique is the largest clique containing a given node.
-
maximal_cliques
(g)¶ Returns a vector of maximal cliques, where each maximal clique is represented by a vector of vertices. Here,
g
must be an undirected graph, and implementvertex_list
andadjacency_list
.
Topological Sorting¶
Topological sorting of an acyclic directed graph is a linear ordering of vertices, such that for each directed edge (u, v)
, u
always comes before v
in the ordering.
-
topological_sort_by_dfs
(g)¶ Returns a topological sorting of the vertices in
g
in the form of a vector of vertices. Here,g
may be directed or undirected, and implementvertex_list
,vertex_map
, andadjacency_list
.
Shortest Paths¶
This package implements three classic algorithms for finding shortest paths: Dijkstra’s algorithm, the Floyd-Warshall algorithm, and the A* algorithm. We plan to implement the Bellman-Ford algorithm and Johnson’s algorithm in the near future.
Dijkstra’s Algorithm¶
-
dijkstra_shortest_paths
(graph, edge_dists, source[, visitor])¶ Performs Dijkstra’s algorithm to find shortest paths to all vertices from input sources.
Parameters: - graph – The input graph
- edge_dists – The vector of edge distances or an edge property inspector.
- source – The source vertex (or vertices)
- visitor – An visitor instance
Returns: An instance of
DijkstraStates
that encapsulates the results.
Here, graph
can be directed or undirected. It must implement
vertex_map
, edge_map
and incidence_list
. edge_dists is optional; if not specified,
default distances of 1 are used for each edge.
The following is an example that shows how to use this function:
# construct a graph and the edge distance vector
g = simple_inclist(5)
inputs = [ # each element is (u, v, dist)
(1, 2, 10.),
(1, 3, 5.),
(2, 3, 2.),
(3, 2, 3.),
(2, 4, 1.),
(3, 5, 2.),
(4, 5, 4.),
(5, 4, 6.),
(5, 1, 7.),
(3, 4, 9.) ]
ne = length(inputs)
dists = zeros(ne)
for i = 1 : ne
a = inputs[i]
add_edge!(g, a[1], a[2]) # add edge
dists[i] = a[3] # set distance
end
r = dijkstra_shortest_paths(g, dists, 1)
@assert r.parents == [1, 3, 1, 2, 3]
@assert r.dists == [0., 8., 5., 9., 7.]
The result has several fields, among which the following are most useful:
parents[i]
: the parent vertex of the i-th vertex. The parent of each source vertex is itself.hasparent[i]
:true
if the i-th vertex has a parent, andfalse
otherwise. Whenhasparent[i] == false
, it means that the vertex at indexi
isn’t reachable from any source. Note thathasparent[i] == true
for all source vertices.dists[i]
: the minimum distance from the i-th vertex to source.
The user can (optionally) provide a visitor that perform operations along with the algorithm. The visitor must be an instance of a sub type of AbstractDijkstraVisitor
, which may implement part of all of the following methods.
-
discover_vertex!(visitor, u, v, d)
Invoked when a new vertex
v
is first discovered (from the parentu
).d
is the initial distance fromv
to source.
-
include_vertex!(visitor, u, v, d)
Invoked when the distance of a vertex is determined (at the point
v
is popped from the heap). This function should return whether to continue the procedure. One can use a visitor to terminate the algorithm earlier by letting this function returnfalse
under certain conditions.
-
update_vertex!(visitor, u, v, d)
Invoked when the distance to a vertex is updated (relaxed).
-
close_vertex!(visitor, u, v, d)
Invoked when a vertex is closed (all its neighbors have been examined).
-
enumerate_paths
(vertices, parent_indices[, dest])¶ Returns an array of vectors (containing vertices), whose
i
-th element corresponds to the path from a source to vertexdest[i]
. Empty vectors indicate vertices that are unreachable from the source.dest
can be a subset of indices, or left unspecified (in which case, all the indices will be considered). Ifdest
is a single index, then the result is just an array of vertices, corresponding to the path from a source todest
.
-
enumerate_indices
(parent_indices[, dest])¶ Returns an array of indices corresponding to the vertices returned by enumerate_paths(vertices, parent_indices[, dest])
The following is an example that shows how to use this function:
julia> g4 = Graphs.inclist([4,5,6,7],is_directed=true)
julia> add_edge!(g4,4,5); add_edge!(g4,4,6); add_edge!(g4,5,6); add_edge!(g4,6,7)
julia> s4 = dijkstra_shortest_paths(g4,5)
julia> sps = enumerate_indices(s4.parent_indices) # dest: all indices
4-element Array{Array{Int64,1},1}:
[]
[2]
[2,3]
[2,3,4]
julia> enumerate_indices(s4.parent_indices, [2,4]) # dest: subset of indices
2-element Array{Array{Int64,1},1}:
[2]
[2,3,4]
julia> enumerate_indices(s4.parent_indices, 4) # dest: single index
3-element Array{Int64,1}:
2
3
4
julia> enumerate_paths(vertices(g4), s4.parent_indices) # dest: all vertices
4-element Array{Array{Int64,1},1}:
[]
[5]
[5,6]
[5,6,7]
julia> enumerate_paths(vertices(g4), s4.parent_indices, [2,4]) # dest: subset of vertices
2-element Array{Array{Int64,1},1}:
[5]
[5,6,7]
julia> enumerate_paths(vertices(g4), s4.parent_indices, 4) # dest: single vertex
3-element Array{Int64,1}:
5
6
7
Remark: enumerate_paths
and enumerate_indices
are applicable to the results from both dijkstra_shortest_paths
and bellman_ford_shortest_paths
.
Bellman Ford Algorithm¶
-
bellman_ford_shortest_paths
(graph, edge_dists, source)¶ Performs Bellman Ford algorithm to find shortest paths to all vertices from input sources.
Parameters: - graph – The input graph
- edge_dists – The vector of edge distances or an edge property inspector.
- source – The source vertex (or vertices)
Returns: An instance of
BellmanFordStates
that encapsulates the results.
Here, graph
can be directed or undirected. Weights can be negative
for a directed graph. It must implement
vertex_map
, edge_map
and incidence_list
. If there is a
negative weight cycle an exception of NegativeCycleError
is thrown.
The result has several fields, among which the following are most useful:
parents[i]
: the parent vertex of the i-th vertex. The parent of each source vertex is itself.dists[i]
: the minimum distance from the i-th vertex to source.
-
has_negative_edge_cycle
(graph, edge_dists)¶ - Tests if the graph has a negative weight cycle.
Parameters: - graph – The input graph
- edge_dists – The vector of edge distances or an edge property inspector.
Returns: true
if there is a negative weight cycle,false
otherwise.e
Floyd-Warshall’s algorithm¶
-
floyd_warshall
(dists)¶ Performs Floyd-Warshall algorithm to compute shortest path lengths between each pair of vertices.
Parameters: dists – The edge distance matrix. Returns: The matrix of shortest path lengths.
-
floyd_warshall!(dists)
Performs Floyd-Warshall algorithm inplace, updating an edge distance matrix into a matrix of shortest path lengths.
-
floyd_warshall!(dists, nexts)
Performs Floyd-Warshall algorithm inplace, and writes the next-hop matrix. When this function finishes,
nexts[i,j]
is the next hop ofi
along the shortest path fromi
toj
. One can reconstruct the shortest path based on this matrix.
A*¶
-
shortest_path
(graph, dists, s, t[, heuristic])¶ Find the shortest path between vertices
s
andt
ofgraph
using Hart, Nilsson and Raphael’s A* algorithm.Parameters: - graph – the input graph
- dists – the edge distance matrix or an edge property inspector
- s – the start vertex
- t – the end vertex
- heuristic – a function underestimating the distance from its input node to
t
.
Returns: an array of edges representing the shortest path.
Minimum Spanning Trees¶
This package implements two algorithm to find a minimum spanning tree of a graph: Prim’s algorithm and Kruskal’s algorithm.
Prim’s algorithm¶
Prim’s algorithm finds a minimum spanning tree by growing from a root vertex, adding one edge at each iteration.
-
prim_minimum_spantree
(graph, eweights, root)¶ Perform Prim’s algorithm to find a minimum spanning tree.
Parameters: - graph – the input graph
- eweights – the edge weights (a vector or an edge property inspector)
- root – the root vertex
Returns: (re, rw)
, wherere
is a vector of edges that constitute the resultant tree, andrw
is the vector of corresponding edge weights.
Kruskal’s algorithm¶
Kruskal’s algorithm finds a minimum spanning tree (or forest) by gradually uniting disjoint trees.
-
kruskal_minimum_spantree
(graph, eweights[, K=1])¶ Parameters: - graph – the input graph
- eweights – the edge weights (a vector or an edge property inspector)
- K – the number of trees in the resultant forest. If
K = 1
, it ends up with a tree. This argument is optional. By default, it is set to1
.
Returns: (re, rw)
, wherere
is a vector of edges that constitute the resultant tree, andrw
is the vector of corresponding edge weights.
Flow¶
This package implements Simple Minimum Cut
Simple Minimum Cut¶
Stoer’s simple minimum cut gets the minimum cut of an undirected graph.
-
min_cut
(graph[, eweights])¶ Parameters: - graph – the input graph
- eweights – the edge weights (a vector or an edge property inspector). This argument is optional. If not given edges are weight “1”
Returns: (parity, bestcut)
, whereparity
is a vector of boolean values that determines the partition andbestcut
is the weight of the cut that makes this partition.
Random Graphs¶
Erdős–Rényi graphs¶
The Erdős–Rényi model sets an edge between each pair of vertices with equal probability, independently of the other edges.
-
erdos_renyi_graph
(g, n, p[; has_self_loops=false])¶ Add edges between vertices 1:n of graph
g
randomly, adding each possible edge with probabilityp
independently of all others.Parameters: - g – the input graph
- n – the number of vertices between which to add edges
- p – the probability with which to add each edge
- has_self_loops – whether to consider edges
v -> v
.
Returns: the graph
g
.
-
erdos_renyi_graph
(n, p[, has_self_loops=false]) Convenience function to construct an
n
-vertex Erdős–Rényi graph as an incidence list.
Watts-Strogatz graphs¶
The Watts–Strogatz model is a random graph generation model that produces graphs with small-world properties, including short average path lengths and high clustering.
-
watts_strogatz_graph
(g, n, k, beta)¶ Adjust the edges between vertices 1:n of the graph
g
in accordance with the Watts-Strogatz model.Parameters: - g – the input graph
- n – the number of vertices between which to adjust edges
- k – the base degree of each vertex (n > k, k >= 2, k must be even.)
- beta – the probability of each edge being “rewired”.
Returns: the graph
g
.
-
watts_strogatz_graph
(n, k, beta) Convenience function to construct an
n
-vertex Watts-Strogatz graph as an incidence list.