Smallest Last Ordering

Produces a vertex ordering by repeatedly removing the vertex with the smallest degree. This ordering is a good heuristic for graph coloring: using it with sequential_vertex_coloring often produces near-optimal results.

Complexity: O(V + E)
Defined in: <boost/graph/smallest_last_ordering.hpp>

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/smallest_last_ordering.hpp>
#include <boost/property_map/shared_array_property_map.hpp>
#include <iostream>
#include <vector>

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;

int main() {
    Graph g(5);
    boost::add_edge(0, 1, g);
    boost::add_edge(0, 2, g);
    boost::add_edge(1, 2, g);
    boost::add_edge(2, 3, g);
    boost::add_edge(3, 4, g);

    auto order = boost::smallest_last_vertex_ordering(g);
    std::cout << "Smallest-last ordering:\n";
    for (std::size_t i = 0; i < order.size(); ++i) {
        std::cout << "  position " << i << ": vertex " << order[i] << "\n";
    }
}

Smallest-last ordering:
  position 0: vertex 0
  position 1: vertex 1
  position 2: vertex 2
  position 3: vertex 3
  position 4: vertex 4

(1) With full work-map set

template <typename VertexListGraph, typename Order,
          typename Degree, typename Marker>
void smallest_last_vertex_ordering(const VertexListGraph& g,
                                   Order order, Degree degree,
                                   Marker marker);

Allocates a bucket_sorter keyed on degree and delegates to overload (2).

(2) With explicit bucket sorter

template <typename VertexListGraph, typename Order,
          typename Degree, typename Marker, typename BucketSorter>
void smallest_last_vertex_ordering(const VertexListGraph& g,
                                   Order order, Degree degree,
                                   Marker marker,
                                   BucketSorter& degree_buckets);

Useful if you want to reuse a pre-allocated bucket_sorter across multiple runs.

(3) With only the ordering map

template <typename VertexListGraph, typename Order>
void smallest_last_vertex_ordering(const VertexListGraph& g, Order order);

Equivalent to (1) with internally allocated degree and marker property maps built over vertex_index.

(4) Returning a vector

template <typename VertexListGraph>
std::vector<typename graph_traits<VertexListGraph>::vertex_descriptor>
smallest_last_vertex_ordering(const VertexListGraph& g);

Convenience form: returns a std::vector<vertex_descriptor> of length num_vertices(g) holding the ordering.

Parameters

Direction Parameter Description

Direction	Parameter	Description
IN	`const VertexListGraph& g`	Must model Vertex List Graph and Incidence Graph with an internal `vertex_index` property.
OUT	`Order order`	WritablePropertyMap from position (integer) to vertex descriptor — `put(order, i, v)` places vertex `v` at position `i` of the ordering.
UTIL	`Degree degree`	ReadWritePropertyMap from vertex to current (remaining) degree.
UTIL	`Marker marker`	ReadWritePropertyMap from vertex to marker value; used to track removed vertices.
UTIL	`BucketSorter& degree_buckets`	A `bucket_sorter` indexed by current degree. Reused across calls if desired.

const VertexListGraph& g

Must model Vertex List Graph and Incidence Graph with an internal vertex_index property.

OUT

Order order

WritablePropertyMap from position (integer) to vertex descriptor — put(order, i, v) places vertex v at position i of the ordering.

UTIL

Degree degree

ReadWritePropertyMap from vertex to current (remaining) degree.

UTIL

Marker marker

ReadWritePropertyMap from vertex to marker value; used to track removed vertices.

UTIL

BucketSorter& degree_buckets

A bucket_sorter indexed by current degree. Reused across calls if desired.

Combine with sequential_vertex_coloring for a simple but effective graph coloring pipeline.

Edit this Page