Topological Sorting Algorithms.
toposort
A one stop shop for all your topological sorting needs
Features
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 precedej
vs.i
must followj
) - 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
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
g <- list(
# 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
g <- list(
# 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
g <- rbind(
# 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
Cyclic dependencies
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
g <- list(
# 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")
Installation
You can install the development version of toposort from github:
# install.packages("pak")
pak::pkg_install("tzakharko/toposort")