cuthill_mckee_ordering

  (1)
  template <class IncidenceGraph, class OutputIterator,
            class ColorMap, class DegreeMap>
  OutputIterator
  cuthill_mckee_ordering(const IncidenceGraph& g,
                         typename graph_traits<IncidenceGraph>::vertex_descriptor s,
                         OutputIterator inverse_permutation,
                         ColorMap color, DegreeMap degree)

  (2)
  template <class VertexListGraph, class OutputIterator>
  OutputIterator
  cuthill_mckee_ordering(const VertexListGraph& g, OutputIterator inverse_permutation);

  template <class VertexListGraph, class OutputIterator, class VertexIndexMap>
  OutputIterator
  cuthill_mckee_ordering(const VertexListGraph& g, OutputIterator inverse_permutation,
                         VertexIndexMap index_map);

  template <class VertexListGraph, class OutputIterator,
            class ColorMap, class DegreeMap>
  OutputIterator
  cuthill_mckee_ordering(const VertexListGraph& g, OutputIterator inverse_permutation,
                         ColorMap color, DegreeMap degree)

  (3)
  template <class IncidenceGraph, class OutputIterator,
            class ColorMap, class DegreeMap>
  OutputIterator
  cuthill_mckee_ordering(const IncidenceGraph& g,
    			 std::deque< typename
			 graph_traits<IncidenceGraph>::vertex_descriptor > vertex_queue,
                         OutputIterator inverse_permutation,
                         ColorMap color, DegreeMap degree)

算法的版本 1 允许用户选择“起始顶点”，版本 2 使用伪外围对启发式算法（在每个组件中）查找一个好的起始顶点，而版本 3 包含双端队列中每个顶点的起始节点。“起始顶点”的选择会对排序的质量产生重大影响。对于版本 2 和 3，find_starting_vertex将对图中的每个组件调用，从而大大增加运行时间。

算法的输出是以新顺序排列的顶点。根据您使用的输出迭代器的类型，您可以获得 Cuthill-Mckee 排序或反向 Cuthill-McKee 排序。例如，如果您使用向量的反向迭代器将输出存储到向量中，则会得到反向 Cuthill-McKee 排序。

  std::vector<vertex_descriptor> inv_perm(num_vertices(G));
  cuthill_mckee_ordering(G, inv_perm.rbegin(), ...);

无论哪种方式，将输出存储到向量中都会为您提供从新顺序到旧顺序的排列。

  inv_perm[new_index[u]] == u

通常，您需要的是相反的排列，即从旧索引到新索引的排列。这可以用以下方法轻松计算。

  for (size_type i = 0; i != inv_perm.size(); ++i)
    perm[old_index[inv_perm[i]]] = i;

参数

• IncidenceGraph& g (输入)
  一个无向图。图的类型必须是 IncidenceGraph 的模型。
  Python：参数名为graph.
• vertex_descriptor s (输入)
  起始顶点。
  Python：不支持此参数。
• OutputIterator inverse_permutation (输出)
  新的顶点排序。顶点按其新顺序写入输出迭代器。
  Python：此参数在 Python 中未使用。新的顶点排序作为 Python列表.
• ColorMap color_map (工作)
  在内部用于跟踪算法的进度（以避免两次访问同一个顶点）。
  Python：不支持此参数。
• DegreeMap degree_map (输入)
  这必须将顶点映射到它们的度数。
  Python：不支持此参数。

• VertexListGraph& g (输入)
  一个无向图。图的类型必须是 VertexListGraph 和 IncidenceGraph 的模型。
  Python：参数名为graph.
• 输出迭代器 inverse_permutation (输出)
  新的顶点排序。顶点按其新顺序写入输出迭代器。
  Python：此参数在 Python 中未使用。新的顶点排序作为 Python列表.
• ColorMap color_map (工作)
  在内部用于跟踪算法的进度（以避免两次访问同一个顶点）。
  Python：不支持此参数。
• DegreeMap degree_map (输入)
  这必须将顶点映射到它们的度数。
  Python：不支持此参数。

• IncidenceGraph& g (输入)
  一个无向图。图的类型必须是 IncidenceGraph 的模型。
  Python：参数名为graph.
• std::deque< typename graph_traits<Graph>::vertex_descriptor > vertex_queue (输入)
  包含每个组件的起始顶点的双端队列。
  Python：不支持此参数。
• OutputIterator inverse_permutation (输出)
  新的顶点排序。顶点按其新顺序写入输出迭代器。
  Python：此参数在 Python 中未使用。新的顶点排序作为 Python列表.
• ColorMap color_map (工作)
  在内部用于跟踪算法的进度（以避免两次访问同一个顶点）。
  Python：不支持此参数。
• DegreeMap degree_map (输入)
  这必须将顶点映射到它们的度数。
  Python：不支持此参数。

示例

另请参见