C++ Boost

sloan_start_end_vertices

Graphs: undirected
Properties: color, degree
Complexity:  
  (1)
  template <class Graph, class ColorMap, class DegreeMap>
  typename graph_traits<Graph>::vertex_descriptor
  sloan_start_end_vertices(Graph& G,
                           typename graph_traits<Graph>::vertex_descriptor &s,
                           ColorMap color,
                           DegreeMap degree )

The goal of the sloan_start_end_vertices algorithm[1, 2] is to find good start- and end-vertices for the profile and wavefront reduction algorithm sloan_ordering. The algorithm is similar to pseudo_peripheral_pair and also based on breadth_first_search. With this breadth_first_search function a so-called rooted level structure (RLS) is formed, where the vertices with the same distance to the starting vertex are grouped together. The maximum number of vertices in one group is called the width of the RLS. Sloan_start_end_vertices tries to find a pseudoperipheral pair with a minimum RLS-width.

Parameters

For version 1:

 

Example

See example/sloan_ordering.cpp.

See Also

sloan_start_end_vertices, bandwidth, profile, wavefront and degree_property_map in boost/graph/properties.hpp.

[1] S. W. Sloan, An algorithm for profile and wavefront reduction of sparse matrices, Int. j. numer. methods eng., 23, 239 - 251 (1986)

[2] S. W. Sloan, A fortran program for profile and wavefront reduction, Int. j. numer. methods eng., 28, 2651 - 2679 (1989)


Copyright © 2001-2002 Marc Wintermantel, ETH Zurich(wintermantel@imes.mavt.ethz.ch)