有向无环图

有向无环图算法。

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

ancestors \(G,来源)

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

descendants \(G,来源)

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

topological_sort (g)

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

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_reduction (g)

返回有向图的传递约简

antichains (g) [, topo_order] )

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

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

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

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

返回DAG中最长的路径长度

dag_to_branching (g)

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