Graph Algorithms

As of Version 10, most of the functionality of the Combinatorica package is built into the Wolfram System. »

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