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