SFS: Similarity-First Search Seriation Algorithm

An implementation of the Similarity-First Search algorithm (SFS), a combinatorial algorithm which can be used to solve the seriation problem and to recognize some structured weighted graphs. The SFS algorithm represents a generalization to weighted graphs of the graph search algorithm Lexicographic Breadth-First Search (Lex-BFS), a variant of Breadth-First Search. The SFS algorithm reduces to Lex-BFS when applied to binary matrices (or, equivalently, unweighted graphs). Hence this library can be also considered for Lex-BFS applications such as recognition of graph classes like chordal or unit interval graphs. In fact, the SFS seriation algorithm implemented in this package is a multisweep algorithm, which consists in repeating a finite number of SFS iterations (at most \eqn{n} sweeps for a matrix of size \eqn{n}). If the data matrix has a Robinsonian structure, then the ranking returned by the multistep SFS algorithm is a Robinson ordering of the input matrix. Otherwise the algorithm can be used as a heuristic to return a ranking partially satisfying the Robinson property.

Version: 0.1.2
Imports: Rcpp (≥ 0.12.7)
LinkingTo: Rcpp, RcppArmadillo
Suggests: seriation
Published: 2017-07-10
Author: Matteo Seminaroti [aut, cph], Utz-Uwe Haus [aut, cre, cph], Monique Laurent [ctb]
Maintainer: Utz-Uwe Haus <uhaus at cray.com>
License: GPL-3
NeedsCompilation: yes
SystemRequirements: C++11
Citation: SFS citation info
Materials: README
CRAN checks: SFS results


Reference manual: SFS.pdf
Package source: SFS_0.1.2.tar.gz
Windows binaries: r-devel: SFS_0.1.2.zip, r-release: SFS_0.1.2.zip, r-oldrel: SFS_0.1.2.zip
OS X El Capitan binaries: r-release: SFS_0.1.2.tgz
OS X Mavericks binaries: r-oldrel: SFS_0.1.2.tgz
Old sources: SFS archive


Please use the canonical form https://CRAN.R-project.org/package=SFS to link to this page.