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 包含 deque 中每个顶点的起始节点。“起始顶点”的选择会对排序的质量产生重大影响。对于版本 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.
• OutputIterator 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 （输入）
  包含每个组件起始顶点的 deque。
  Python：不支持的参数。
• OutputIterator inverse_permutation （输出）
  新的顶点排序。顶点以其新顺序写入输出迭代器。
  Python：此参数在 Python 中未使用。新的顶点排序作为 Python 返回列表.
• ColorMap color_map （工作）
  在内部用于跟踪算法的进度（以避免两次访问同一个顶点）。
  Python：不支持的参数。
• DegreeMap degree_map （输入）
  这必须将顶点映射到它们的度。
  Python：不支持的参数。

示例

另请参阅