Learn R Programming

pooh (version 0.3-1)

tsort: Topological Sort

Description

Find One Total Order Consistent with Partial Order or With Directed Acyclic Graph

Usage

tsort(from, to, domain, strict = TRUE)

Arguments

from
an atomic vector
to
an atomic vector of the same mode and length as from
domain
an atomic vector of the same mode as from containing all the elements of from and to. If missing, union(from, to) is used. The domain of the relation or the nodes of the graph.
strict
logical. If TRUE then from[i] == to[i] is an error. Otherwise, such edges of the graph are ignored.

Value

A vector that is a reordering of domain so that every element of from appears in the value before the corresponding element of to.Throws an error if there is no consistent total order (the graph has a cycle).

Details

Pairs (from[i], to[i]) can be though of either as elements of a relation on a set or as edges in a directed graph. This function finds one total order on the domain (nodes of the graph) that is consistent with the relation (graph) if one exists (that is if the graph is directed).

Examples

Run this code
from <-   LETTERS[c(1, 1, 1, 1, 2, 2, 6)]
to <- LETTERS[c(2, 3, 4, 5, 3, 5, 7)]
from
to
tsort(from, to)

Run the code above in your browser using DataLab