A one stop shop for all your topological sorting needs

toposort is designed to be a fast, flexible and user-friendly interface to topological sorting. Here are some reasons to try this package out:

- Flexible user interface
- Pass the input data as a list of dependencies or as an adjacency matrix
- Specify the dependency type (
`i`

must precede`j`

vs.`i`

must follow`j`

) - Use item indices or unique character labels

- Stable and unstable topological sort algorithm variants
- Robust error handling and cycle detection
- Input data validation
- Detects and reports cycles in the input data

- Good asymptotic performance
- Reasonably fast on small inputs
- Faster than
`Rfast::topological_sort()`

on large inputs (1000+ items)

Topological sorting of a directed graph is an act of producing a linear sequence of its vertices such that each vertex occurs before any other vertex it dominates. In simpler terms, it is about sorting a set of items in the order of their dependencies on each other. This problem often occurs in practice when we want to process a set of items that are mutually dependent.

Let’s say we want to process three items `a`

,
`b`

and `c`

such that `b`

is a
prerequisite for `a`

and `c`

and `c`

is
prerequisite for `a`

.

```
library(toposort)
# build the graph
<- list(
g # a is not a prerequisite for any other item
a = character(),
# b is a prerequisite for a and c
b = c("a", "c"),
# c is a prerequisite for a
c = c("a")
)# the graph encodes precedence (i must precede all g[[i]])
topological_sort(g, dependency_type = "precedes")
```

toposort offers multiple options to encode the data. For example, instead of a graph that encodes precedence, one can use a graph that encodes dependencies.

```
library(toposort)
# build the graph
<- list(
g # a dependes on b and c
a = c("b", "c"),
# b does not depend on any other item
b = character(),
# c dependes on b
c = c("b")
)# the graph encodes dependency (i must follow all g[[i]])
topological_sort(g, dependency_type = "follows")
```

Or, you can use an adjacency matrix

```
library(toposort)
# build the graph
<- rbind(
g # a dependes on b and c
c(F, T, T),
# b does not depend on any other item
c(F, F, F),
# c dependes on b
c(F, T, F)
)# the graph encodes dependency (i must follow all g[[i]])
topological_sort(g, dependency_type = "follows", labels = c("a", "b", "c"))
```

Check the documentation `?topological_sort`

for more
examples

Topological sorting is only possible if there are no cyclic dependencies. Figuring out such dependencies can be time-consuming, especially on larger inputs, which is why toposort will detect and report them for you.

```
library(toposort)
# build the graph
<- list(
g # a dependes on c
a = c("c"),
# b depends on a (there is a cyclic dependency here!)
b = c("a"),
# c dependes on b
c = c("b")
)# the graph encodes dependency (i must follow all g[[i]])
topological_sort(g, dependency_type = "follows")
```

You can install the development version of toposort from github:

```
# install.packages("pak")
::pkg_install("tzakharko/toposort") pak
```