find_odd_cycle

// Version with a colormap to retrieve the bipartition
template <typename Graph, typename IndexMap, typename PartitionMap, typename OutputIterator>
OutputIterator find_odd_cycle (const Graph& graph, const IndexMap index_map, PartitionMap partition_map, OutputIterator result)

template <typename Graph, typename IndexMap, typename OutputIterator>
OutputIterator find_odd_cycle (const Graph& graph, const IndexMap index_map, OutputIterator result)

// Version which uses the internal index map
template <typename Graph, typename OutputIterator>
OutputIterator find_odd_cycle (const Graph& graph, OutputIterator result)

该find_odd_cycle该函数使用基于 DFS 的着色方法测试给定图是否是二分的。

一个无向图是二分的，如果可以将其顶点集划分为两个集合“左”和“右”，使得每条边都从一侧连接到另一侧。显然，图的二着色与二划分完全相同。is_bipartite()测试是否可能进行这种二着色，并可以在给定的属性映射中返回它。

另一个等价的刻画是长度为奇数的环不存在，这意味着一个图是二分的当且仅当它不包含长度为奇数的环作为子图。find_odd_cycle()的功能与 is_bipartite() 几乎相同，但如果发现图不是二分的，还会额外构造一个长度为奇数的环。

二分性记录在颜色映射中partition_map，其中将包含图的二着色，即为顶点分配黑色和白色，使得没有边是单色的。长度为奇数的环被写入输出迭代器result如果存在。函数返回最终的最终迭代器。

定义位置

boost/graph/bipartite.hpp

参数

INconst Graph& graph

无向图。图类型必须是顶点列表图和关联图的模型。

INconst IndexMap index_map

此映射将每个顶点映射到一个范围内的整数[0, num_vertices(graph))，distance_compare(d, distance_infinity) == true。其类型VertexIndexMap必须是 Readable Property Map 的模型。该映射的值类型必须是整数类型。图的顶点描述符类型需要可以用作该映射的键类型。

OUTPartitionMap partition_map

该算法测试图是否为二分的，并根据划分将每个顶点分配为白色或黑色。该PartitionMap类型必须是 Readable Property Map 和 Writable Property Map 的模型。值类型必须是 ColorValue 的模型。

OUTOutputIterator result

该find_odd_cycle函数在图不是二分的情况下查找长度为奇数的环。产生这种环的顶点序列被写入此迭代器。该OutputIterator类型必须是 OutputIterator 的模型。图的顶点描述符类型必须在迭代器的值类型集中。函数返回最终值。如果图是二分的（即不存在长度为奇数的环），则不写入任何内容，因此给定的迭代器与返回值匹配。

复杂度

该算法的时间复杂度为 O(V + E)。

另请参阅

is_bipartite()

示例

文件 example/bipartite_example.cpp 包含一个测试无向图二分性的示例。

Copyright © 2010 Matthias Walter (xammy@xammy.homelinux.net)