Graph Algorithms

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

• Cycles and Connectivity
• Graph Construction and Representation
• Subsets and Permutations
• Permutation Groups