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 n sweeps for a matrix of size 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.4 |
| Imports: |
Rcpp (≥ 0.12.7) |
| LinkingTo: |
Rcpp, RcppArmadillo |
| Suggests: |
seriation |
| Published: |
2019-05-07 |
| 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 |
Documentation:
Downloads:
Linking:
Please use the canonical form
https://CRAN.R-project.org/package=SFS
to link to this page.