Graphs.jl implements a collection of classic graph algorithms:
Graph traversal refers to a process that traverses vertices of a graph following certain order (starting from user-input sources). This package implements two traversal schemes: breadth-first and depth-first.
During traveral, each vertex maintains a status (also called color), which is an integer value defined as below:
| Parameters: |
|
|---|
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.
invoked when a vertex v is encountered for the first time. This function should return whether to continue traversal.
invoked when a vertex v is about to examine v‘s neighbors.
invoked when a neighbor/out-going edge is examined. Here color is the status of 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:
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.
In graph theory, a cycle is defined to be a path that starts from some vertex v and ends up at v.
Tests whether a graph contains a cycle through depth-first search. It returns true when it finds a cycle, otherwise false. Here, g must implement vertex_list, vertex_map, and adjacency_list.
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.
Returns a vector of components, where each component is represented by a vector of vertices. Here, g must be an undirected graph, and implement vertex_list, vertex_map, and adjacency_list.
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.
Returns a topological sorting of the vertices in g in the form of a vector of vertices. Here, g must be a directed graph, and implement vertex_list, vertex_map, and adjacency_list.
This package implements two classic algorithms for finding shortest paths: Dijkstra’s algorithm and Floyd-Warshall algorithm algorithm. We plan to implement Bellman-Ford algorithm and Johnson’s algorithm in near future.
Performs Dijkstra’s algorithm to find shortest paths to all vertices from input sources.
| Parameters: |
|
|---|---|
| Returns: | An instance of DijkstraStates that encapsulates the results. |
Here, graph can be directed or undirected. It must implement vertex_map and incidence_list. 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(g1_wedges)
dists = zeros(ne)
for i = 1 : ne
a = inputs[i]
add_edge!(g1, 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:
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.
Invoked when a new vertex v is first discovered (from the parent u). d is the initial distance from v to source.
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 return false under certain conditions.
Invoked when the distance to a vertex is updated (relaxed).
Invoked when a vertex is closed (all its neighbors have been examined).
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. |
Performs Floyd-Warshall algorithm inplace, updating an edge distance matrix into a matrix of shortest path lengths.
Performs Floyd-Warshall algorithm inplace, and writes the next-hop matrix. When this function finishes, nexts[i,j] is the next hop of i along the shortest path from i to j. One can reconstruct the shortest path based on this matrix.
This package implements two algorithm to find a minimum spanning tree of a graph: Prim’s algorithm and Kruskal’s algorithm.
Prim’s algorithm finds a minimum spanning tree by growing from a root vertex, adding one edge at each iteration.
Perform Prim’s algorithm to find a minimum spanning tree.
| Parameters: |
|
|---|---|
| Returns: | (re, rw), where re is a vector of edges that constitute the resultant tree, and rw is the vector of corresponding edge weights. |
Kruskal’s algorithm finds a minimum spanning tree (or forest) by gradually uniting disjoint trees.
| Parameters: |
|
|---|---|
| Returns: | (re, rw), where re is a vector of edges that constitute the resultant tree, and rw is the vector of corresponding edge weights. |