图的顶点拓扑排序

有向无环图的拓扑排序是其节点的线性排序，其中每个节点都出现在所有它有边的节点之前。

用法

topo_sort(graph, mode = c("out", "all", "in"))

参数

graph

输入图，应该是带方向的

mode

指定如何使用边的方向。 对于“out”，排序顺序确保每个节点都出现在所有它有边的节点之前，因此没有入边的节点排在最前面。 对于“in”，则恰恰相反：每个节点都出现在所有它接收边的节点之前。 没有出边的节点排在最前面。

值

一个顶点序列（默认情况下，但请参阅igraph_options()的return.vs.es选项），其中包含按拓扑排序的顶点。

详细信息

每个 DAG 至少有一个拓扑排序，并且可能有多个。 此函数返回它们之间可能的拓扑排序。 如果图不是无环的（它至少有一个环），则返回部分拓扑排序并发出警告。

参见

其他结构属性：bfs()、component_distribution()、connect()、constraint()、coreness()、degree()、dfs()、distance_table()、edge_density()、feedback_arc_set()、feedback_vertex_set()、girth()、is_acyclic()、is_dag()、is_matching()、k_shortest_paths()、knn()、reciprocity()、subcomponent()、subgraph()、transitivity()、unfold_tree()、which_multiple()、which_mutual()

作者

Tamas Nepusz ntamas@gmail.com 和 Gabor Csardi csardi.gabor@gmail.com 为 R 接口

示例

g <- sample_pa(100)
topo_sort(g)
#> + 100/100 vertices, from 1cb8d91:
#>   [1]   3   4  11  13  18  19  24  26  29  33  34  35  37  38  39  40  41  45
#>  [19]  47  48  49  50  52  53  55  57  58  59  60  62  63  64  65  66  68  69
#>  [37]  70  71  72  73  74  75  76  78  79  80  81  82  83  84  85  86  87  88
#>  [55]  89  90  91  92  93  94  95  96  97  98  99 100  25  36  42  46  56  43
#>  [73]  61  10  28  51  44  77  32  12  14  30  22  54  23  21  31   8  67  17
#>  [91]   7  27  16  20   5  15   6   9   2   1