or-tools/src/graph/

This is the main page of the auto-generated documentation for directory or-tools/src/graph/.
Please use the tabs just above the title to navigate documentation in this directory.

Readme

From or-tools/src/graph/README:

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.
  

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.)
  
  
• 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
  /java/com/google/wrappers/util/operationsresearch directory.
  

Owners

There is no OWNERS in this directory.