Package pygraph :: Package algorithms :: Module minmax

# Module minmax

Minimization and maximization algorithms.

Functions

list

heuristic_search(graph, start, goal, heuristic) A* search algorithm. |

dictionary

minimal_spanning_tree(graph, root=None) Minimal spanning tree. |

tuple

shortest_path(graph, source) Return the shortest path distance between source and all other nodes using Dijkstra's algorithm. |

tuple

shortest_path_bellman_ford(graph, source) Return the shortest path distance between the source node and all other nodes in the graph using Bellman-Ford's algorithm. |

tuple

maximum_flow(graph, source, sink, caps=None) Find a maximum flow and minimum cut of a directed graph by the Edmonds-Karp algorithm. |

float

cut_value(graph, flow, cut) Calculate the value of a cut. |

dictionary

cut_tree(igraph, caps=None) Construct a Gomory-Hu cut tree by applying the algorithm of Gusfield. |

Variables
| __package__ = ``'``pygraph.algorithms``'``

Function Details

### heuristic_search(graph, start, goal, heuristic)

A* search algorithm.

A set of heuristics is available under `graph.algorithms.heuristics`. User-created heuristics are allowed too.

Parameters:
  - `graph` (graph, digraph) - Graph
  - `start` (node) - Start node
  - `goal` (node) - Goal node
  - `heuristic` (function) - Heuristic function
Returns: list
  Optimized path from start to goal node

### minimal_spanning_tree(graph, root=None)

Minimal spanning tree.

Parameters:
  - `graph` (graph) - Graph.
  - `root` (node) - Optional root node (will explore only root's connected component)
Returns: dictionary
  Generated spanning tree.

Attention: Minimal spanning tree is meaningful only for weighted graphs.

### shortest_path(graph, source)

Return the shortest path distance between source and all other nodes using Dijkstra's algorithm.

Parameters:
  - `graph` (graph, digraph) - Graph.
  - `source` (node) - Node from which to start the search.
Returns: tuple
  A tuple containing two dictionaries, each keyed by target nodes.
  1. Shortest path spanning tree
  2. Shortest distance from given source to each target node

  Inaccessible target nodes do not appear in either dictionary.

Attention: All weights must be nonnegative.

See Also: shortest_path_bellman_ford

### shortest_path_bellman_ford(graph, source)

Return the shortest path distance between the source node and all other nodes in the graph using Bellman-Ford's algorithm.

This algorithm is useful when you have a weighted (and obviously a directed) graph with negative weights.

Parameters:
  - `graph` (digraph) - Digraph
  - `source` (node) - Source node of the graph
Returns: tuple
  A tuple containing two dictionaries, each keyed by target nodes. (same as shortest_path function that implements Dijkstra's algorithm)
  1. Shortest path spanning tree
  2. Shortest distance from given source to each target node
Raises:
  - `NegativeWeightCycleError` - raises if it finds a negative weight cycle. If this condition is met d(v) > d(u) + W(u, v) then raise the error.

Attention: The algorithm can detect negative weight cycles and will raise an exception. It's meaningful only for directed weighted graphs.

See Also: shortest_path

### maximum_flow(graph, source, sink, caps=None)

Find a maximum flow and minimum cut of a directed graph by the Edmonds-Karp algorithm.

Parameters:
  - `graph` (digraph) - Graph
  - `source` (node) - Source of the flow
  - `sink` (node) - Sink of the flow
  - `caps` (dictionary) - Dictionary specifying a maximum capacity for each edge. If not given, the weight of the edge will be used as its capacity. Otherwise, for each edge (a,b), caps[(a,b)] should be given.
Returns: tuple
  A tuple containing two dictionaries
  1. contains the flow through each edge for a maximal flow through the graph
  2. contains to which component of a minimum cut each node belongs

### cut_value(graph, flow, cut)

Calculate the value of a cut.

Parameters:
  - `graph` (digraph) - Graph
  - `flow` (dictionary) - Dictionary containing a flow for each edge.
  - `cut` (dictionary) - Dictionary mapping each node to a subset index. The function only considers the flow between nodes with 0 and 1.
Returns: float
  The value of the flow between the subsets 0 and 1

### cut_tree(igraph, caps=None)

Construct a Gomory-Hu cut tree by applying the algorithm of Gusfield.

Parameters:
  - `igraph` (graph) - Graph
  - `caps` (dictionary) - Dictionary specifying a maximum capacity for each edge. If not given, the weight of the edge will be used as its capacity. Otherwise, for each edge (a,b), caps[(a,b)] should be given.
Returns: dictionary
  Gomory-Hu cut tree as a dictionary, where each edge is associated with its weight