有向无环图#

有向无环图算法。

请注意,这些函数中的大多数只保证对DAG有效。一般来说,这些函数不检查非循环性,因此由用户来检查。

ancestors(G, source)

返回具有以下路径的所有节点 source 在里面 G .

descendants(G, source)

返回可从中访问的所有节点 source 在里面 G .

topological_sort(G)

返回拓扑排序顺序的节点生成器。

topological_generations(G)

将一个DAG分成几代。

all_topological_sorts(G)

返回的生成器 _all_ 有向图G的拓扑类。

lexicographical_topological_sort(G[, key])

返回按字典拓扑排序顺序的节点生成器。

is_directed_acyclic_graph(G)

如果图表 G 是有向非循环图(DAG),否则为假。

is_aperiodic(G)

返回true G 是非周期性的。

transitive_closure(G[, reflexive])

返回图的传递闭包

transitive_closure_dag(G[, topo_order])

返回有向无环图的传递闭包。

transitive_reduction(G)

返回有向图的传递约简

antichains(G[, topo_order])

从有向无环图(DAG)生成反链。

dag_longest_path(G[, weight, ...])

返回有向非循环图(DAG)中的最长路径。

dag_longest_path_length(G[, weight, ...])

返回DAG中最长的路径长度

dag_to_branching(G)

返回一个分支,表示给定有向非循环图中从根节点到叶节点的所有(重叠)路径。