Skip to content

Latest commit

 

History

History
 
 

graph

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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:

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.

Wrappers

  • 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.

Samples

You can find some canonical examples in samples