Shortest Paths

Dijkstra — find single-source shortest paths

AllPairsShortestPath — find shortest paths simultaneously for all pairs

ShortestPath — sequence of vertices that define the shortest path

BellmanFord  ▪  Eccentricity  ▪  Radius  ▪  Diameter  ▪  Girth

ParentsToPaths  ▪  GraphCenter  ▪  GraphPower

Minimum Spanning Trees

MinimumSpanningTree — find a minimum spanning tree of a graph

NumberOfSpanningTrees — number of spanning trees

InitializeUnionFind  ▪  FindSet  ▪  UnionSet

Cofactor  ▪  ShortestPathSpanningTree  ▪  MaximumSpanningTree

NetworkFlow — maximum flow through a graph

ResidualFlowGraph — construct a directed graph for a graph with respect to flow

StableMarriage — optimal stable marriage defined by lists of permutations

MaximalMatching — compute maximal matching of a graph

BipartiteMatching — find a maximum bipartite matching

NoPerfectMatchingGraph  ▪  AlternatingPaths  ▪  BipartiteMatchingAndCover

PartialOrderQ  ▪  TopologicalSort  ▪  TransitiveClosure  ▪  TransitiveReduction

Graph Traversals

DepthFirstTraversal — depth-first traversal of a graph

BreadthFirstTraversal — breadth-first traversal of a graph

Partial Orders

HasseDiagram  ▪  BooleanAlgebra  ▪  IsomorphicQ  ▪  InversionPoset

DominatingIntegerPartitionQ  ▪  DominationLattice  ▪  PartitionLattice

MinimumChainPartition  ▪  MaximumAntichain

Graph Isomorphism

Isomorphism — find isomorphism between two graphs

Equivalences — vertex equivalence classes between two graphs

IdenticalQ  ▪  IsomorphismQ  ▪  Neighborhood  ▪  Distances  ▪  SelfComplementaryQ

DegreesOf2Neighborhood  ▪  NumberOf2Paths  ▪  NumberOfKPaths