Skip to content

Latest commit

 

History

History
 
 

graph

Folders and files

NameName
Last commit message
Last commit date

parent directory

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

It contains in particular:
- a compact and efficient graph representation (EbertGraph, see ebert_graph.h),
  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.
</summary>

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:
- connectivity.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 minimun-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.

- flow.swig: SWIG instructions to wrap the C++ library in Python and Java.

C++ examples are available in the examples directory alongside the
graph directory.

Python examples are available in the python directory alongside the
graph library.

Java examples are available in the examples/com/google/ortools directory.