Module: Graph
- use Boost Graph Library
- use Lemon Graph Library
- implement our own graph code
- Lemon provides efficient data structures and algorithms that serve our needs.
- Lemon is very stable, even if there are no frequent releases.
- Lemon has Boost license, which is compatible for SeqAn3.
- Lemon can be used header-only.
- Lemon has a good Documentation and Tutorial.
- Boost implements even more data structures and algorithms.
- Boost is header-only as well.
- Boost Graph Library is dependent on other Boost headers: Include size gets huge!
- Own graph code can be most specific, but has to be developed, implemented and maintained.
- We created a header-only fork on Github that contains latest Lemon code (version 1.3.1). This is necessary, because Lemon uses Mercurial version control.
- It will be updated manually, if Lemon developers provide useful extensions or bug-fixes in the future.
- The fork is included as a sub-module in SeqAn3 repository. It is an optional dependency, but it will be downloaded with a recursive clone of SeqAn3 by default.
- The absence of Lemon will disable all graph-dependent modules, like MSA (Multiple Sequence Alignment) and HMM (Hidden Markov Model).
- We manually created the
config.hfile in the Lemon fork to set necessary macros. Platform-specific settings for Lemon can be found ininclude/seqan3/core/platform.hpp.
- Alignment graph in MSA module
- Guide tree, BFS search
- Component search in MSA module
- Maximum Weighted Matching in Lara2
- Hidden Markov Model
