Trees might be represented by either the predecessor labels, the subgraph multiplicities or the edge colours. Generally, the predecessor label representation is used. Only the Kruskal method differs: At an intermediate step of adding a tree edge, it does not know the arc orientation in the final rooted tree. The subgraph representation is used instead of the edge colours since sparse subgraphs of complete graphs are represented more economically.
The travelling salesman solver uses the concept of a one-cycle tree exposing an (arbitrary but fixed) node r: This denotes a spanning tree of the nodes other than r, adding the two minimum length edges incident with r. That yields a cycle through r and, when this cycle is contracted to a single node, a spanning tree rooted at the artificial node. Minimum one-cycle trees constitute lower bounds on the length of a Hamiltonian cycle.
The following shows a set of nodes in the Euclidian plane, a minimum one cycle tree exposing the upper left node, and a minimum spanning tree rooted at the same node:
As computing an optimal tour is NP-hard, the library includes construction heuristics, methods to compute lower bounds on the minimum tour length, and a branch & bound scheme.
In the following example, a graph, the length labels and an acoording minimum length tour are shown. The optimality can be concluded from the fact that this tour is also a minimum reduced length one-cycle tree (for the upper left node). The reduced length labels and the node potentials applied for length reduction are also displayed:
