The hardware and bandwidth for this mirror is donated by dogado GmbH, the Webhosting and Full Service-Cloud Provider. Check out our Wordpress Tutorial.
If you wish to report a bug, or if you are interested in having us mirror your free-software or open-source project, please feel free to contact us at mirror[@]dogado.de.

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 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

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")

These binaries (installable software) and packages are in development.
They may not be fully stable and should be used with caution. We make no claims about them.
Health stats visible at Monitor.