Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.
C++ Boost

(Python) king_ordering

Graphs: undirected
Properties: color, degree
Complexity: time: O(m2log(m)|E|) where m = max { degree(v) | v in V }
  (1)
  template <class IncidenceGraph, class OutputIterator,
            class ColorMap, class DegreeMap, class VertexIndexMap>
  OutputIterator
  king_ordering(const IncidenceGraph& g,
                typename graph_traits<Graph>::vertex_descriptor s,
                OutputIterator inverse_permutation, 
                ColorMap color, DegreeMap degree, VertexIndexMap index_map);

  (2)
  template <class IncidenceGraph, class OutputIterator>
  OutputIterator
  king_ordering(const IncidenceGraph& g, OutputIterator inverse_permutation);

  template <class IncidenceGraph, class OutputItrator, class VertexIndexMap>
  OutputIterator
  king_ordering(const IncidenceGraph& g, OutputIterator inverse_permutation,
                VertexIndexMap index_map);

  template <class VertexListGraph, class OutputIterator, 
            class ColorMap, class DegreeMap, class VertexIndexMap>
  OutputIterator
  king_ordering(const VertexListGraph& G, OutputIterator inverse_permutation, 
                ColorMap color, DegreeMap degree, VertexIndexMap index_map);
                         
  (3)
  template <class IncidenceGraph, class OutputIterator,
            class ColorMap, class DegreeMap, class VertexIndexMap>
  OutputIterator
  king_ordering(const IncidenceGraph& g,
    		std::deque< typename
		graph_traits<Graph>::vertex_descriptor > vertex_queue,
                OutputIterator permutation, 
                ColorMap color, DegreeMap degree, VertexIndexMap index_map);
The goal of the King ordering algorithm [62]is to reduce the bandwidth of a graph by reordering the indices assigned to each vertex. The King ordering algorithm works by a local minimization of the i-th bandwidths. The vertices are basically assigned a breadth-first search order, except that at each step, the adjacent vertices are placed in the queue in order of increasing pseudo-degree, where pseudo-degree is defined as the number of outgoing edges with white endpoints (vertices yet to be examined).

Version 1 of the algorithm lets the user choose the ``starting vertex'', version 2 finds a good starting vertex using the pseudo-peripheral pair heuristic (among each component), while version 3 contains the starting nodes for each vertex in the deque. The choice of the ``starting vertex'' can have a significant effect on the quality of the ordering.

The output of the algorithm are the vertices in the new ordering. Storing the output into a vector gives you the permutation from the new ordering to the old ordering.

  inv_perm[new_index[u]] == u

Often times, 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;

Parameters

For version 1: For version 2: For version 3:

Example

See example/king_ordering.cpp.

See Also

bandwidth, and degree_property_map in boost/graph/properties.hpp.

Copyright © 2000-2001 Jeremy Siek, Indiana University (jsiek@osl.iu.edu)