# All topological sorting arrangements of a DAG

**URL:** <https://igraph.discourse.group/t/all-topological-sorting-arrangements-of-a-dag/1151>\
**Category:** Usage\
**Tags:** R\
**Created:** [22 March 2022 12:59 UTC](https://igraph.discourse.group/t/all-topological-sorting-arrangements-of-a-dag/1151 "2022-03-22T12:59:39Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![mb208](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/mb208/32/724_2.png) [@mb208](https://igraph.discourse.group/u/mb208)\
**Post date:** [22 March 2022 12:59 UTC](https://igraph.discourse.group/t/all-topological-sorting-arrangements-of-a-dag/1151/1 "2022-03-22T12:59:39Z")

</div>

Hi all,

I noticed that there is a topological sort method that gives a topological sorting of the vertices of a DAG, but this seems to only return 1 arrangement. I was wondering if there was a method that returns all possible arrangements or a way to use the previously mentioned method to find all possible arrangements.

Thanks!

Marc

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [22 March 2022 18:26 UTC](https://igraph.discourse.group/t/all-topological-sorting-arrangements-of-a-dag/1151/2 "2022-03-22T18:26:45Z")

</div>

igraph does not have an algorithm to generate all topological sorts, and off-hand I can’t recommend one either. If you research this topic and possible algorithms, feel free to [open a feature request for igraph’s C core](https://github.com/igraph/igraph/issues/new/choose), filling out all sections, and including any extra information that can help us implement it.

---

<div class="post-metadata">

**Author:** ![M-crypto645](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/m-crypto645/32/1213_2.png) [@M-crypto645](https://igraph.discourse.group/u/M-crypto645)\
**Post date:** [29 June 2025 17:17 UTC](https://igraph.discourse.group/t/all-topological-sorting-arrangements-of-a-dag/1151/3 "2025-06-29T17:17:21Z")

</div>

An algorithm for this is implemented in the R-package thamesmix under the function alltopsorts\_recursion (of which I am the maintainer). It takes the adjacency list of a directed acyclic graph as an argument.

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [1 July 2025 23:47 UTC](https://igraph.discourse.group/t/all-topological-sorting-arrangements-of-a-dag/1151/4 "2025-07-01T23:47:20Z")

</div>

@M-crypto645 Are you interested in contributing a performant C port to igraph?