Boost C++ 库

...全世��最有价值、最精��设计的 C++ 库项目之一。 — Herb Sutter 和 Andrei Alexandrescu, C++ Coding Standards

Boost 图库：传递闭包 - Boost C++ 函数库

(Python) transitive_closure 

template <typename Graph, typename GraphTC,
  typename P, typename T, typename R>
void transitive_closure(const Graph& g, GraphTC& tc,
  const bgl_named_params<P, T, R>& params = all defaults)

template <typename Graph, typename GraphTC,
  typename G_to_TC_VertexMap, typename VertexIndexMap>
void transitive_closure(const Graph& g, GraphTC& tc,
                        G_to_TC_VertexMap g_to_tc_map, VertexIndexMap index_map)
图 G = (V,E) 的传递闭包是一个图 G* = (V,E*)，其中 E* 包含一个边 (u,v) 当且仅当 G 包含一条从 u 到 v 的路径（至少一条边）。transitive_closure()函数将输入图转换为传递闭包图。使用标准和运行时支持库的调试版本。到传递闭包图tc.

感谢 Vladimir Prus 实现此算法！

定义位置

boost/graph/transitive_closure.hpp

参数

INconst Graph& g
有向图，其中图类型必须满足顶点列表图、邻接图和邻接矩阵概念。
Python: 参数名为graph.
OUTGraphTC& tc
有向图，其中GraphTC类型必须满足可变顶点图和可变边图概念。
Python: 该参数在 Python 中未使用。而是返回一个相同类型的新图。

命名参数

UTIL/OUTorig_to_copy(G_to_TC_VertexMap g_to_tc_map)
此映射将输入图中的每个顶点映射到输出传递闭包图中的相应新顶点。
Python: 这必须是一个vertex_vertex_map图的。
INvertex_index_map(VertexIndexMap& index_map)
此映射将每个顶点映射到一个范围内的整数[0, num_vertices(g))。当使用默认颜色属性映射时，此参数是必需的。类型VertexIndexMap必须是 Readable Property Map 的模型。该映射的值类型必须是整数类型。图的顶点描述符类型需要可以用作该映射的键类型。
Default get(vertex_index, g)注意：如果您使用此默认值，请确保您的图具有内部vertex_index属性。例如，adjacency_list带有VertexList=listS没有内部vertex_indexproperty。
Python: 不支持的参数。

复杂度

时间复杂度（最坏情况）为 O(|V||E|)。

示例

以下是示例中的图example/transitive_closure.cpp以及算法计算出的传递闭包。

实现说明

用于实现transitive_closure()函数的算法基于强连通分量的检测[50, 53]。以下讨论描述了算法（以及一些相关的背景理论）。

顶点 v 的后继集，表示为 Succ(v)，是从顶点 v 可以到达的顶点集合。在传递闭包 G* 中与 v 相邻的顶点集与原始图 G 中 v 的后继集相同。计算传递闭包等同于计算 G 中每个顶点的后继集。

同一强连通分量中的所有顶点具有相同的后继集（因为每个顶点都可以从该分量中的所有其他顶点到达）。因此，为强连通分量中的每个顶点计算后继集是冗余的；为每个分量中的一个顶点计算就足够了。

以下是算法大纲

  1. 计算图的强连通分量。
  2. 构造缩点图。一个缩点图是基于图 G=(V,E) 的图 G'=(V',E')，其中 V' 中的每个顶点对应 G 中的一个强连通分量，并且当且仅当存在一条边在 E 中连接 u 的分量中的任意顶点与 v 的分量中的任意顶点时，边 (u,v) 才在 E' 中。
  3. 在缩点图上计算传递闭包。这是使用以下算法完成的
     for each vertex u in G' in reverse topological order
   for each vertex v in Adj[u]
     if (v not in Succ(u))
       Succ(u) = Succ(u) U { v } U Succ(v)   // "U" means set union
    按逆拓扑顺序考虑顶点，以确保在计算顶点 u 的后继集时，Adj[u] 中每个顶点的后继集已计算完毕。

    对集合并运算的优化实现提高了算法的性能。因此，此实现使用链分解[51, 52]。G 的顶点被划分为链 Z1, ..., Zk，其中每个链 Zi 是 G 中的一条路径，并且链中的顶点具有递增的拓扑编号。然后，后继集 S 表示为与链的交集集合，即 S = Ui=1...k (Zi & S)。每个交集可以表示为在 S 中也存在的路径 Zi 的第一个顶点，因为该路径的其余部分保证也存在于 S 中。因此，交集集合由一个长度为 k 的向量表示，其中向量的第 i 个元素存储 S 与 Zi 的交集中的第一个顶点。

    计算两个后继集 S1 和 S2 的并集 S3 = S1 U S2，可以通过以下运算在 O(k) 时间内完成

      for i = 0...k
    S3[i] = min(S1[i], S2[i]) // where min compares the topological number of the vertices
  4. 根据缩点图 G'* 的传递闭包创建图 G*。


版权所有 © 2001 Jeremy Siek, Indiana Univ.(jsiek@cs.indiana.edu)