Module algorithms_edu::algo::graph

Graph Theory Algorithms

This module contains implementations of graph and tree representations and algorithms.

I highly recommend watching William Fiset's video series on graph theory algorithms While following along, try implementing the algorithms yourself before comparing them to implementations presented here or William's original Java implementations.

Modules

bfs	Breadth First Search
bipartite_check	This mod shows you how to determine if a graph is bipartite or not. This can be achieved in linear time by coloring the visited nodes.
dfs
eulerian_path	Implementation of finding an Eulerian Path on a graph. This implementation verifies that the input graph is fully connected and supports self loops and repeated edges between nodes.
minimum_spanning_tree
network_flow
shortest_path
tarjan_scc	An implementation of Tarjan's Strongly Connected Components algorithm using an adjacency list.
topological_sort	Topological Sort
tree	This module contains tree representations and related algorithms.

Structs

Edge	The Edge type used in WeightedAdjacencyList. A from field is not required because it's implied by its position in the adjacency list.
UnweightedAdjacencyList	An unweighted graph represented by an unweighted adjacency list. This is in principle the same as WeightedAdjacencyList, except that no weights are involved and thus a simple usize is able to represent an outgoing edge.
WeightedAdjacencyList	A graph represented by a weighted adjacency list. Under the hood, a weighted adjacency list is a Vec of Vec of Edges. For an adjacency list g, g[i] is a Vec of edges pointing from i to other nodes (vertices). Thus, the number of nodes is implied by the len of the (outer) Vec. For each node i that do not have outgoing edges, g[i] is an empty vector.
WeightedAdjacencyMatrix	Dense graphs, are sometimes more efficient to be represented as adjacency matrices. A WeightedAdjacencyMatrix is based on a Matrix of size n * n where n is the number of nodes (vertices) in the graph. For a WeightedAdjacencyMatrix g, g[i][j] is the weight of the edge pointing from node i to node j. By convention, for two nodes i and j that are not connected, g[i][j] = INFINITY, and each node by default has a weight of 0 to point to itself (i.e. g[i][i] = 0).
WeightedUndirectedAdjacencyMatrixCondensed	An adjacency matrix representing an undirected graph is symmetric with respect to the main diagonal, i.e. g[i][j] = g[j][i]. Thus, only half of the values in the matrix need to be stored. In addition, The assumption that g[i][i] = 0 works fine in most cases, so weights representing these self-pointing edges are also not stored.