Graphs

Algae implements a complete framework for working with and creating custom graph-related data-structures. These efforts are generally split between a directed and undirected instance of a graph, using a trait to describe common behaviors.

Graphs

A graph is a non-linear data-structure created from a collection of nodes paired together to form edges that store an optional edge value.

Directed

Undirected

Algorithms

Cycles

Cycle Detection

• Brent's Cycle Detection algorithm
• Floyd Cycle Detection Algorithm

Paths

Shortest Path

• Bellman-Ford
• Dijkstra's Shortest path algorithm

Search

Breadth-First Search (BFS)

A breadth-first search starts at a particular vertex and explores all of its neighbors at the present depth before moving on to the vertices in the next level.

Depth-First Search (DFS)

In depth-first search, the given vertex is explored as far as possible along each branch before retracing back. To do so, a stack data-structure is used to support backtracking.

Sort

Topological Sorting

• Kahn's algorithm
• Depth-First Search based algorithm

Misc

Matching

• Blossom algorithm
• Hopcroft-Karp algorithm
• Hungarian algorithm

Maximum Flow

• Dinic's algorithm
• Edmonds algorithm
• Ford-Flukerson algorithm

Minimum Spanning Tree

• Kruskal's Algorithm
• Prim's Algorithm

Strongly Connected Components

• Kosaraju's algorithm
• Tarjan's algorithm