MAGMA Computational Algebra System

Labelled, Capacitated and Weighted Graphs

A vertex labelling of a graph G is a partial map f from the vertex-set V of G into a set L. An edge labelling of a graph G is a partial map f from the edge-set E of G into a set L. A labelled graph is built by assigning labels successively to vertices or edges after the (unlabelled) graph has been constructed.

Similarly, a capacitated graph G is a partial map from its edge-set into Z^ +, and a weighted graph G is a partial map from its edge-set into R, R any ring with a total order. Those two last features are particularly convenient when running shortest-paths and flow algorithms. Edge capacities and edge weights are assigned to edges once the graph has been constructed. Any graph edge may carry a label, together with a capacity and/or a weight.

All the functions for decorating graph vertices and edges are fully documented in Section Vertex and Edge Decorations in Chapter MULTIGRAPHS. A few examples are also given there.