Package: SFS 0.1.4

Utz-Uwe Haus

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.

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

SFS_0.1.4.tar.gz
SFS_0.1.4.tar.gz(r-4.5-noble)SFS_0.1.4.tar.gz(r-4.4-noble)
SFS_0.1.4.tgz(r-4.4-emscripten)SFS_0.1.4.tgz(r-4.3-emscripten)
SFS.pdf |SFS.html✨
SFS/json (API)

# Install 'SFS' in R:
install.packages('SFS', repos = 'https://cloud.r-project.org')
Uses libs:
  • c++– GNU Standard C++ Library v3

On CRAN:

Conda:

This package does not link to any Github/Gitlab/R-forge repository. No issue tracker or development information is available.

cpp

2.60 score 166 downloads 8 mentions 2 exports 2 dependencies

Last updated 6 years agofrom:59ead1b2ee. Checks:1 OK, 2 NOTE. Indexed: yes.

TargetResultLatest binary
Doc / VignettesOKMar 17 2025
R-4.5-linux-x86_64NOTEMar 17 2025
R-4.4-linux-x86_64NOTEMar 17 2025

Exports:readsfs

Dependencies:RcppRcppArmadillo

Citation

Seminaroti M, Haus U (2019). SFS: Similarity-First Search Seriation Algorithm. R package version 0.1.4, https://CRAN.R-project.org/package=SFS.

Monique Laurent and Matteo Seminaroti. Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition. SIAM Journal on Discrete Mathematics, 31(3):1765-1800, 2017.

Seminaroti M (2016). Combinatorial Algorithms for the Seriation Problem. Ph.D. thesis, Tilburg University, CentER, Center for Economic Research. https://pure.uvt.nl/portal/files/13544298/PhD_thesis_Matteo_Seminaroti_.pdf.

The work was performed at Centrum Wiskunde & Informatica (CWI), Amsterdam.

Corresponding BibTeX entries: 

  @Manual{,
    title = {SFS: Similarity-First Search Seriation Algorithm},
    author = {Matteo Seminaroti and Utz-Uwe Haus},
    year = {2019},
    note = {R package version 0.1.4},
    url = {https://CRAN.R-project.org/package=SFS},
  }

  @Article{,
    title = {Similarity-First Search: A New Algorithm with Application
      to Robinsonian Matrix Recognition},
    author = {Monique Laurent and Matteo Seminaroti},
    year = {2016},
    journal = {SIAM Journal on Discrete Mathematics},
    colume = {31},
    number = {3},
    year = {2016},
    pages = {1765-1800},
  }

  @PhdThesis{,
    author = {Matteo Seminaroti},
    title = {Combinatorial Algorithms for the Seriation Problem},
    school = {Tilburg University},
    year = {2016},
    address = {CentER, Center for Economic Research},
    month = {12},
    url =
      {https://pure.uvt.nl/portal/files/13544298/PhD_thesis_Matteo_Seminaroti_.pdf},
  }

Readme and manuals

SFS

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.