This page provides a comprehensive collection of algorithm implementations for seventy-five of the most fundamental problems in combinatorial algorithms. The problem taxonomy, implementations, and supporting material are all drawn from my book The Algorithm Design Manual. Since the practical person is more often looking for a program than an algorithm, we provide pointers to solid implementations of useful algorithms when they are available.
Because of the volatility of the web, we provide local copies for many of the implementations. We encourage you to get them from the original sites instead of here, because the version on the original site is more likely to be maintained. Further, there are often supporting files and documentation which we did not copy, and which may be of interest to you. The local copies of large implementations are maintained as gzip tar archives and, where available, DOS zip archives. Software for decoding these formats is readily available.
Many of these codes have been made available for research or educational use, so commercial use requires a licensing arrangement with the author. Licensing terms from academic institutions are usually surprisingly modest. The recognition that industry is using a particular code is important to the authors, often more important than the money. This can lead to enhanced support or future releases of the software. Do the right thing and get a license -- information about terms or who to contact is usually available embedded within the documentation, or available at the original source site.
Use at your own risk. The author, Springer, and the State University of New York make no representations, express or implied, with respect to any software or documentation we describe. The authors, Springer, and the State University of New York shall in no event be liable for any indirect, incidental, or consequential damages.
Dictionaries,
Priority Queues,
Suffix Trees and Arrays,
Graph Data Structures,
Set Data Structures,
Kd-Trees
Solving Linear Equations,
Bandwidth Reduction,
Matrix Multiplication,
Determinants and Permanents,
Constrained and Unconstrained Optimization,
Linear Programming,
Random Number Generation,
Factoring and Primality Testing,
Arbitrary-Precision Arithmetic,
Knapsack Problem,
Discrete Fourier Transform
Sorting,
Searching,
Median and Selection,
Generating Permutations,
Generating Subsets,
Generating Partitions,
Generating Graphs,
Calendrical Calculations,
Job Scheduling,
Satisfiability
Connected Components,
Topological Sorting,
Minimum Spanning Tree,
Shortest Path,
Transitive Closure and Reduction,
Matching,
Eulerian Cycle/Chinese Postman,
Edge and Vertex Connectivity,
Network Flow,
Drawing Graphs Nicely,
Drawing Trees,
Planarity Detection and Embedding
Clique,
Independent Set,
Vertex Cover,
Traveling Salesman Problem,
Hamiltonian Cycle,
Graph Partition,
Vertex Coloring,
Edge Coloring,
Graph Isomorphism,
Steiner Tree,
Feedback Edge/Vertex Set
Robust Geometric Primitives,
Convex Hull,
Triangulation,
Voronoi Diagrams,
Nearest Neighbor Search,
Range Search,
Point Location,
Intersection Detection,
Bin Packing,
Medial-Axis Transform,
Polygon Partitioning,
Simplifying Polygons,
Shape Similarity,
Motion Planning,
Maintaining Line Arrangements,
Minkowski Sum
Set Cover,
Set Packing,
String Matching,
Approximate String Matching,
Text Compression,
Cryptography,
Finite State Machine Minimization,
Longest Common Substring/Subsequence,
Shortest Common Superstring
C, Ada, Binary, C++, C#, Fortran, Go, Java, JavaScript, Lisp, Mathematica, Pascal, PHP, Python