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.


Similarity-First Search

Documentation is available for the R functions SFS::read and SFS::sfs.

Development is happening on http://github.com:seminaro/SFS.git.

SFS is available on CRAN, at https://cran.r-project.org/package=SFS


Developer notes

If you change any interface wrapping C++ code for R, regenerate the wrapper code by

    R> library(Rcpp)
    R> compileAttributes() 

and if you change the set of exported functions (or import from other packages)

    R> library(devtools)
    R> devtools::document("../SFS")

To prepare a CRAN upload, do

    R> library(devtools)
    R> devtools::check("../SFS")

and also consider uploading to https://win-builder.r-project.org/upload.aspx to see if the code works on Windows.

News

Reference manual

It appears you don't have a PDF plugin for this browser. You can click here to download the reference manual.

install.packages("SFS")

0.1.2 by Utz-Uwe Haus, 2 years ago


Browse source code at https://github.com/cran/SFS


Authors: Matteo Seminaroti [aut, cph] , Utz-Uwe Haus [aut, cre, cph] , Monique Laurent [ctb]


Documentation:   PDF Manual  


GPL-3 license


Imports Rcpp

Suggests seriation

Linking to Rcpp, RcppArmadillo

System requirements: C++11


See at CRAN