Graphs [HB 108]

With the introduction of multigraphs, the conventions for labelling edges in simple graphs were extended so that they are consistent across the two graph types.

Changes:

• Edges of a simple graph can be assigned a capacity and/or weight, in addition to a label.

• Flow-based algorithms and shortest-paths algorithms aplly to simple graphs (which may be capacitated and/or weighted).

• Graph equality and subgraph testing now take account of the structure of the graph and, if applicable, of the graph support, the vertex/edge labels, and the edge capacities.

• Incremental graph construction (using the sub<> constructor, or by adding/removing vertices/edges) retains the support and vertex/edge decoration of the original graph.

New Features:

• Shortest path computation between two vertices in a (weighted) graph.

• Existence of a negative weight cycle in a (weighted) graph.

• All-pairs shortest paths computation.

• Minimum weight tree rooted at some vertex.