sloan_ordering
Reduces the profile and wavefront of an undirected graph by reordering vertex indices.
Complexity: O(log(m)|E|) where m = max { degree(v) | v in V }
Defined in: <boost/graph/sloan_ordering.hpp>
Example
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/sloan_ordering.hpp>
#include <iostream>
#include <vector>
using namespace boost;
struct VertexData {
default_color_type color{};
int degree = 0;
double priority = 0.0;
};
using Graph = adjacency_list<setS, vecS, undirectedS, VertexData>;
using Vertex = graph_traits<Graph>::vertex_descriptor;
int main() {
Graph g(6);
add_edge(0, 1, g); add_edge(0, 2, g); add_edge(1, 3, g);
add_edge(2, 3, g); add_edge(3, 4, g); add_edge(4, 5, g);
// Populate degrees; sloan_ordering reads them to pick a start vertex.
auto deg = get(&VertexData::degree, g);
for (auto v : make_iterator_range(vertices(g))) {
put(deg, v, static_cast<int>(out_degree(v, g)));
}
// Bundled scratch fields replace the three vertex property tags.
std::vector<Vertex> order(num_vertices(g));
sloan_ordering(g, order.begin(),
get(&VertexData::color, g), deg,
get(&VertexData::priority, g));
std::cout << "Sloan ordering:";
for (auto v : order) { std::cout << " " << v; }
std::cout << "\n";
}Sloan ordering: 5 4 3 2 1 0(1) With start/end vertices and weights
template <class Graph, class OutputIterator,
class ColorMap, class DegreeMap,
class PriorityMap, class Weight>
OutputIterator sloan_ordering(
Graph& g,
typename graph_traits<Graph>::vertex_descriptor s,
typename graph_traits<Graph>::vertex_descriptor e,
OutputIterator permutation,
ColorMap color,
DegreeMap degree,
PriorityMap priority,
Weight W1,
Weight W2);| Direction | Parameter | Description |
|---|---|---|
IN |
|
An undirected graph. The graph’s type must be a model of IncidenceGraph. |
IN |
|
The starting vertex. |
IN |
|
The ending vertex. |
OUT |
|
The new vertex ordering. The vertices are written to the output iterator in their new order. |
WORK |
|
Used internally to keep track of the progress of the algorithm (to avoid visiting the same vertex twice). |
IN |
|
This must map vertices to their degree. |
IN |
|
Used internally to store the priority for renumbering of each vertex. |
IN |
|
First heuristical weight for the Sloan algorithm. |
IN |
|
Second heuristical weight for the Sloan algorithm. |
(2) Without start/end vertices, with weights
template <class Graph, class OutputIterator,
class ColorMap, class DegreeMap,
class PriorityMap, class Weight>
OutputIterator sloan_ordering(
Graph& g,
OutputIterator permutation,
ColorMap color,
DegreeMap degree,
PriorityMap priority,
Weight W1,
Weight W2);| Direction | Parameter | Description |
|---|---|---|
IN |
|
An undirected graph. The graph’s type must be a model of IncidenceGraph. |
OUT |
|
The new vertex ordering. The vertices are written to the output iterator in their new order. |
WORK |
|
Used internally to keep track of the progress of the algorithm (to avoid visiting the same vertex twice). |
IN |
|
This must map vertices to their degree. |
IN |
|
Used internally to store the priority for renumbering of each vertex. |
IN |
|
First heuristical weight for the Sloan algorithm. |
IN |
|
Second heuristical weight for the Sloan algorithm. |
(3) With start/end vertices, default weights
template <class Graph, class OutputIterator,
class ColorMap, class DegreeMap,
class PriorityMap>
OutputIterator sloan_ordering(
Graph& g,
typename graph_traits<Graph>::vertex_descriptor s,
typename graph_traits<Graph>::vertex_descriptor e,
OutputIterator permutation,
ColorMap color,
DegreeMap degree,
PriorityMap priority);| Direction | Parameter | Description |
|---|---|---|
IN |
|
An undirected graph. The graph’s type must be a model of IncidenceGraph. |
IN |
|
The starting vertex. |
IN |
|
The ending vertex. |
OUT |
|
The new vertex ordering. The vertices are written to the output iterator in their new order. |
WORK |
|
Used internally to keep track of the progress of the algorithm (to avoid visiting the same vertex twice). |
IN |
|
This must map vertices to their degree. |
IN |
|
Used internally to store the priority for renumbering of each vertex. |
(4) Without start/end vertices, default weights
template <class Graph, class OutputIterator,
class ColorMap, class DegreeMap,
class PriorityMap>
OutputIterator sloan_ordering(
Graph& g,
OutputIterator permutation,
ColorMap color,
DegreeMap degree,
PriorityMap priority);| Direction | Parameter | Description |
|---|---|---|
IN |
|
An undirected graph. The graph’s type must be a model of IncidenceGraph. |
OUT |
|
The new vertex ordering. The vertices are written to the output iterator in their new order. |
WORK |
|
Used internally to keep track of the progress of the algorithm (to avoid visiting the same vertex twice). |
IN |
|
This must map vertices to their degree. |
IN |
|
Used internally to store the priority for renumbering of each vertex. |
Description
The goal of the Sloan ordering algorithm [77, 78] is to reduce the profile and
the wavefront of a graph by reordering the indices assigned to each vertex.
The Sloan algorithm needs a start and an end vertex. These vertices can be
assigned manually. But there is also an algorithm sloan_starting_nodes that
provides usually quite good start and end vertices. Each vertex is assigned
with a priority. This priority is a weighted sum of the distance of the vertex
to the end vertex (a global criterion) and is called the current degree of
vertex. This current degree basically reflects the status of the renumbering in
the neighborhood of a vertex (a local criterion). Therefore the Sloan
algorithm (in contrast to McKee) takes into account local as well as global
criteria for the renumbering sequence. One can play around with the relative
weights, but the default values proposed by Sloan (weight1/weight2=1/2) turn
out to be pretty good in most cases.
Overload (1) lets the user choose the start and end vertex whereas overload (2)
finds a good starting vertex using the sloan_starting_node algorithm. The
choice of these vertices can have a significant effect on the quality of the
ordering. Overloads (3) and (4) are identical to (1) and (2) respectively,
except that the standard weights W1=1 and W2=2 are used.
The output of the algorithm are the vertices in the new ordering. Depending on what kind of output iterator you use, you can get either the Sloan ordering or the reverse Sloan ordering. For example, if you store the output into a vector using the vector’s reverse iterator, then you get the reverse Sloan ordering.
std::vector<vertex_descriptor> inv_perm(num_vertices(G));
sloan_ordering(G, inv_perm.rbegin());Either way, storing the output into a vector gives you the permutation from the new ordering to the old ordering.
inv_perm[new_index[u]] == u
Sometimes, it is the opposite permutation that you want, the permutation from the old index to the new index. This can easily be computed in the following way.
for (size_type i = 0; i != inv_perm.size(); ++i) perm[old_index[inv_perm[i]]] = i;
Usually you need the reversed ordering with the Cuthill-McKee algorithm and the direct ordering with the Sloan algorithm.