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 |

Reference manual: | SFS.pdf |

Package source: | SFS_0.1.4.tar.gz |

Windows binaries: | r-devel: SFS_0.1.4.zip, r-release: SFS_0.1.4.zip, r-oldrel: SFS_0.1.4.zip |

OS X binaries: | r-release: SFS_0.1.4.tgz, r-oldrel: SFS_0.1.4.tgz |

Old sources: | SFS archive |

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