| Version: | 0.3-2 |
| Date: | 2017-03-26 |
| Title: | Partial Orders and Relations |
| Author: | Charles J. Geyer <charlie@stat.umn.edu>. |
| Maintainer: | Charles J. Geyer <charlie@stat.umn.edu> |
| Depends: | R (≥ 3.0.2) |
| Description: | Finds equivalence classes corresponding to a symmetric relation or undirected graph. Finds total order consistent with partial order or directed graph (so-called topological sort). |
| License: | MIT + file LICENSE |
| URL: | http://www.stat.umn.edu/geyer/pooh/ |
| NeedsCompilation: | yes |
| Packaged: | 2017-03-26 23:05:48 UTC; geyer |
| Repository: | CRAN |
| Date/Publication: | 2017-03-27 00:00:26 UTC |
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 |
domain |
an atomic vector of the same mode as |
strict |
logical. If |
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).
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).
Examples
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)
Equivalence Classes
Description
Calculates Equivalence Classes
Usage
weak(from, to, domain, markers = FALSE)
Arguments
from |
an atomic vector |
to |
an atomic vector of the same mode and length as |
domain |
an atomic vector of the same mode as |
markers |
controls the type of result; see Values below. |
Details
Pairs (from[i], to[i]) can be though of either as elements of
a symmetric relation on a set or as edges in an undirected graph.
This function calculates the equivalence classes of the transitive
closure of the relation or the components of the graph. If the edges
are thought of as directed, then we calculate the weak components,
meaning the components of the associated undirected graph, rather than
the so-called strong components of the directed graph.
Value
If markers = FALSE,
a list, elements of which are the components (equivalence classes).
If markers = TRUE, an integer vector of the same length as
domain or as union(from, to) if domain is missing,
elements of which are the same if and only if the corresponding elements
of the domain (nodes of the graph) are in the same connected component
(equivalence class).
Examples
to <- sample(1:100, 75, replace = TRUE)
from <- sample(1:100, 75, replace = TRUE)
out <- weak(from, to)
sapply(out, length)