Module 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.