Name		Name	Last commit message	Last commit date
parent directory ..
csharp		csharp
java		java
python		python
samples		samples
BUILD.bazel		BUILD.bazel
CMakeLists.txt		CMakeLists.txt
README.md		README.md
__init__.py		__init__.py
assignment.cc		assignment.cc
assignment.h		assignment.h
astar.cc		astar.cc
bellman_ford.cc		bellman_ford.cc
christofides.h		christofides.h
cliques.cc		cliques.cc
cliques.h		cliques.h
connected_components.cc		connected_components.cc
connected_components.h		connected_components.h
dijkstra.cc		dijkstra.cc
ebert_graph.h		ebert_graph.h
eulerian_path.h		eulerian_path.h
flow_problem.proto		flow_problem.proto
graph.h		graph.h
graphs.h		graphs.h
hamiltonian_path.h		hamiltonian_path.h
io.h		io.h
iterators.h		iterators.h
linear_assignment.cc		linear_assignment.cc
linear_assignment.h		linear_assignment.h
max_flow.cc		max_flow.cc
max_flow.h		max_flow.h
min_cost_flow.cc		min_cost_flow.cc
min_cost_flow.h		min_cost_flow.h
minimum_spanning_tree.h		minimum_spanning_tree.h
one_tree_lower_bound.h		one_tree_lower_bound.h
perfect_matching.cc		perfect_matching.cc
perfect_matching.h		perfect_matching.h
shortestpaths.cc		shortestpaths.cc
shortestpaths.h		shortestpaths.h
strongly_connected_components.h		strongly_connected_components.h
topologicalsorter.cc		topologicalsorter.cc
topologicalsorter.h		topologicalsorter.h
util.cc		util.cc
util.h		util.h

README.md

Graph and Network Flows

This directory contains data structures and algorithms for graph and network flow problems.

It contains in particular:

a compact and efficient graph representation (EbertGraph), which is used for most of the algorithms herein, unless specified otherwise.
well-tuned algorithms (for example shortest paths and Hamiltonian paths.)
hard-to-find algorithms (Hamiltonian paths, push-relabel flow algorithms.)
other, more common algorithm, that are useful to use with EbertGraph.

Graph representations:

ebert_graph.h: Entry point for a directed graph class.
digraph.h: Entry point for a directed graph class. To be deprecated by ebert_graph.h.

Paths:

shortestpaths.h: Entry point for shortest path computations. Includes Dijkstra and Bellman-Ford algorithms.
hamiltonian_path.h: Entry point for computing minimum Hamiltonian paths and cycles on directed graphs with costs on arcs, using a dynamic-programming algorithm (Does not need ebert_graph.h or digraph.h.)

Graph decompositions:

connected_components.h: Entry point for computing connected components in an undirected graph. (Does not need ebert_graph.h or digraph.h.)
strongly_connected_components.h: Entry point for computing the strongly connected components of a directed graph, based on an algorithm of Tarjan.
cliques.h: Entry point for computing maximum cliques and clique covers in a directed graph, based on the Bron-Kerbosch algorithm. (Does not need ebert_graph.h or digraph.h.)

Flow algorithms:

linear_assignment.h: Entry point for solving linear sum assignment problems (classical assignment problems where the total cost is the sum of the costs of each arc used) on directed graphs with arc costs, based on a push-relabel algorithm of Goldberg and Kennedy.
max_flow.h: Entry point for computing maximum flows on directed graphs with arc capacities, based on a push-relabel algorithm of Goldberg and Tarjan.
min_cost_flow.h: Entry point for computing minimum-cost flows on directed graphs with arc capacities, arc costs, and supplies/demands at nodes, based on a push-relabel algorithm of Goldberg and Tarjan.

python: the SWIG code that makes the wrapper available in Python, and its unit tests.
java: the SWIG code that makes the wrapper available in Java, and its unit tests.
csharp: the SWIG code that makes the wrapper available in C#, and its unit tests.

You can find some canonical examples in samples