jermp / fulgor

Fulgor is a fast and space-efficient colored de Bruijn graph index.

Fulgor

Fulgor is a (meta-) colored compacted de Bruijn graph index for large-scale matching and color queries, powered by SSHash and GGCAT.

The Fulgor index is described in the following papers:

• Fulgor: A Fast and Compact k-mer Index for Large-Scale Matching and Color Queries (Algorithms for Molecular Biology, ALMOB 2024), and

• Meta-colored compacted de Bruijn graphs (International Conference on Research in Computational Molecular Biology, RECOMB 2024).

Please, cite these papers if you use Fulgor.

Table of contents

• Dependencies
• Compiling the code
• Tools and usage
• Quick start
• Indexing an example Salmonella pangenome
• Pseudoalignment output format

Dependencies

GGCAT

The code uses the GGCAT Rust library, so make sure you have Rust installed. If not, Rust can be installed as recommended here, with

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

zlib

If you do not have zlib installed, you can do

sudo apt-get install zlib1g

if you are on Linux/Ubuntu, or

brew install zlib

if you are using MacOS.

Compiling the code

The code is tested on Linux with gcc and on MacOS with clang. To build the code, CMake is required.

First clone the repository with

git clone https://github.com/jermp/fulgor.git

and then do

git submodule update --init --recursive

to pull all necessary submodules before compilation.

To compile the code for a release environment (see file CMakeLists.txt for the used compilation flags), it is sufficient to do the following, within the parent fulgor directory:

mkdir build
cd build
cmake ..
make -j

For a testing environment, use the following instead:

mkdir debug_build
cd debug_build
cmake .. -D CMAKE_BUILD_TYPE=Debug -D FULGOR_USE_SANITIZERS=On
make -j

Tools and usage

There is one executable called fulgor after the compilation, which can be used to run a tool. Run ./fulgor to see a list of available tools.

== Fulgor: a (meta-) colored compacted de Bruijn graph index =============================

Usage: ./fulgor <tool> ...

Tools:
  build              build a Fulgor index
  pseudoalign        pseudoalign reads to references
  stats              print index statistics
  print-filenames    print all reference filenames

Advanced tools:
  partition          partition a Fulgor index and build a meta-colored Fulgor index
  dump-colors        write colors to an output file in text format

For large-scale indexing, it could be necessary to increase the number of file descriptors that can be opened simultaneously:

ulimit -n 2048

Quick start

This short demo shows how to index the 10-genome collection in the folder test_data/salmonella_10 with Fulgor. We will use the standard value k = 31.

First create a list of filenames (with absolute paths) for the files in test_data/salmonella_10. From fulgor/test_data, do

find $(pwd)/salmonella_10/* > salmonella_10_filenames.txt

Then, from fulgor/build, run

./fulgor build -l ../test_data/salmonella_10_filenames.txt -o ../test_data/salmonella_10 -k 31 -m 19 -d tmp_dir -g 1 -t 1 --verbose --check

to build an index that will be serialized to the file test_data/salmonella_10.fur.

Indexing an example Salmonella pangenome

In this example, we will build a Fulgor index, with k = 31, for the 4,546 Salmonella genomes that can be downloaded from here.

We assume all commands are issue from within the home (~/) directory.

After download, create a list of all .fasta filenames with

find $(pwd)/Salmonella_enterica/Genomes/*.fasta > salmonella_4546_filenames.txt

and, from fulgor/build, run

./fulgor build -l ~/salmonella_4546_filenames.txt -o ~/Salmonella_enterica/salmonella_4546 -k 31 -m 20 -d tmp_dir -g 8 -t 8 --verbose --check

which will create an index named ~/Salmonella_enterica/salmonella_4546.fur of 0.266 GB.

We can now pseudoalign the reads from SRR801268, as follows.

First, download the reads in ~/ with (assuming you have wget installed):

cd
wget ftp://ftp.sra.ebi.ac.uk/vol1/fastq/SRR801/SRR801268/SRR801268_1.fastq.gz

and then process them with:

./fulgor pseudoalign -i ~/Salmonella_enterica/salmonella_4546.fur -q ~/SRR801268_1.fastq.gz -t 8 -o /dev/null

mapped 6584304 reads
elapsed = 130133 millisec / 130.133 sec / 2.16888 min / 19.7641 musec/read
num_mapped_reads 5796427/6584304 (88.034%)

using 8 parallel threads and writing the mapping output to /dev/null.

To partition the index to obtain a meta-colored Fulgor index, then do:

./fulgor partition -i ~/Salmonella_enterica/salmonella_4546.fur -d tmp_dir --check

The meta-colored index will be serialized to the file ~/Salmonella_enterica/salmonella_4546.mfur and will take 0.104 GB (2.55X smaller than the .fur index).

Pseudoalignment output format

The tool pseudoalign writes the result to an output file, in plain text format, specified with the option -o [output-filename].

This file has one line for each mapped read, formatted as follows:

[read-name][TAB][list-lenght][TAB][list]

where [list] is a TAB-separated list of increasing integers, of length [list-length], representing the list of reference identifiers to which the read is mapped. ([TAB] is the character \t.)

Example

NODE_11_length_149361_cov_9.71634_ID_21 1       0
NODE_3406_length_341_cov_20.0437_ID_681	1       0
NODE_4745_length_118_cov_12.7931_ID_949	3       0       3       7
NODE_102_length_2047_cov_18.1471_ID_203 1       0
NODE_477_length_1163_cov_22.0531_ID_953 2       0       8
NODE_9_length_173161_cov_9.33695_ID_17  1       0
NODE_22_length_45757_cov_12.1361_ID_43  1       0

Important note

If pseudoalignment is performed against a meta-colored Fulgor index, the reference identifiers in the pseudoalignment output might not correspond to the ones assigned following the input-file order as specified with option -l during index construction. This is because the meta-colored index re-assignes identifiers to references to improve index compression.

In this case, the reference identifiers in the pseudoalignment output are consistent with the ones returned by the print-filenames tool.

fulgor's Issues

Consistent terminology

Not urgent and not performance/correctness related, but rather stylistic: use consistent terminology between code and papers.

Examples: color_class --> color; the query colors() --> color(); k2u --> dictionary; u2c() --> unitig_id_to_color_id(); etc.

Add a note in the README

Add a note in the README specifying that, in case a meta colored dBG is built with the partition tool, the ref-ids in the pseudoalignment output are those returned by the print-filenames tool and not necessarily assigned in the input-file order specified with the option -l.

Missing -lrt linker flag on Ubuntu

Hi @jermp ,

When I compile Fulgor on my machine (Kubuntu 22.04) the compilation fails with some errors that boil down to:
ggcat_api.18b922c2ecd02292-cgu.03:(.text._ZN3std10sys_common9backtrace28__rust_begin_short_backtrace17hf5334377f827e0d6E+0x4d4): undefined reference to clock_gettime'`

I think this is due to the linker flag -lrt missing when building on linux.
Note that on macOS adding -lrt throws errors since macOS does not require the library to be explicitly linked.

Best regards,
Yoshihiro Shibuya

Warning due to 64-bit hash codes

Hi, I'm trying to index a large and diverse collection of bacterial genomes (~300k sequences from ~4000 different species) but keep getting the following error:

fulgor build -k 31 -m 20 -l multifasta_paths.txt -o index -d tmp-fulgor -g 780 -t 20 --verbose
terminate called after throwing an instance of 'std::runtime_error'
  what():  Using 64-bit hash codes with more than 2^30 keys can be dangerous due to collisions: use 128-bit hash codes instead.
/var/spool/slurmd/job273252918/slurm_script: line 35: 2880844 Aborted                 (core dumped)

I found a fix for this in sshash (jermp/sshash#16) but even after uncommenting the relevant line in a fresh clone of fulgor after running git submodule update --init --recursive I keep getting the same error.

Even better build pipeline for meta colored dBG

• When building a meta colored dBG, currently we first build a Fulgor index and then partition it with the partition tool.
  This is useful when we want to test different partition methods. But for end-to-end users, it's likely more handy to just have an option to the build tool, say --meta-colored, which does build+partition in one go.

• Also, hide the permute tool under a --advanced flag options. (It is not meant to be used by common users.)

Build fails due to missing header

Hi, I'm trying to build fulgor on Fedora 36 and getting an issue related to a missing include for <memory> in the sshash submodule. This seems to be because sshash is pulling an old version of https://github.com/jermp/essentials which is missing the include statement in the essentials.hpp file. The newest version of the essentials submodule seems to have fixed this. I can work around this by adding the include manually but just letting you know.

Log from build

temaklin@xps13 build]$ make
[ 14%] Building CXX object CMakeFiles/sshash_static.dir/external/sshash/include/dictionary.cpp.o
In file included from /home/temaklin/software/fulgor/external/sshash/include/../external/pthash/include/encoders/compact_vector.hpp:6,
                 from /home/temaklin/software/fulgor/external/sshash/include/../external/pthash/include/encoders/encoders.hpp:3,
                 from /home/temaklin/software/fulgor/external/sshash/include/../external/pthash/include/pthash.hpp:3,
                 from /home/temaklin/software/fulgor/external/sshash/include/hash_util.hpp:3,
                 from /home/temaklin/software/fulgor/external/sshash/include/util.hpp:8,
                 from /home/temaklin/software/fulgor/external/sshash/include/dictionary.hpp:3,
                 from /home/temaklin/software/fulgor/external/sshash/include/dictionary.cpp:1:
/home/temaklin/software/fulgor/external/sshash/include/../external/pthash/include/encoders/../../external/essentials/include/essentials.hpp: In function ‘std::string essentials::demangle(const char*)’:
/home/temaklin/software/fulgor/external/sshash/include/../external/pthash/include/encoders/../../external/essentials/include/essentials.hpp:371:10: error: ‘unique_ptr’ is not a member of ‘std’
  371 |     std::unique_ptr<char, decltype(&std::free)> ptr(
      |          ^~~~~~~~~~
/home/temaklin/software/fulgor/external/sshash/include/../external/pthash/include/encoders/../../external/essentials/include/essentials.hpp:22:1: note: ‘std::unique_ptr’ is defined in header ‘<memory>’; did you forget to ‘#include <memory>’?
   21 | #include <cxxabi.h>  // for name demangling
  +++ |+#include <memory>
   22 | #endif
/home/temaklin/software/fulgor/external/sshash/include/../external/pthash/include/encoders/../../external/essentials/include/essentials.hpp:371:21: error: expected primary-expression before ‘char’
  371 |     std::unique_ptr<char, decltype(&std::free)> ptr(
      |                     ^~~~
/home/temaklin/software/fulgor/external/sshash/include/../external/pthash/include/encoders/../../external/essentials/include/essentials.hpp:373:12: error: ‘ptr’ was not declared in this scope
  373 |     return ptr.get();
      |            ^~~
/home/temaklin/software/fulgor/external/sshash/include/../external/pthash/include/encoders/../../external/essentials/include/essentials.hpp:369:12: warning: unused variable ‘len’ [-Wunused-variable]
  369 |     size_t len = 0;
      |            ^~~
/home/temaklin/software/fulgor/external/sshash/include/../external/pthash/include/encoders/../../external/essentials/include/essentials.hpp:370:9: warning: unused variable ‘status’ [-Wunused-variable]
  370 |     int status = 0;
      |         ^~~~~~
/home/temaklin/software/fulgor/external/sshash/include/../external/pthash/include/encoders/../../external/essentials/include/essentials.hpp:368:58: warning: unused parameter ‘mangled_name’ [-Wunused-parameter]
  368 | [[maybe_unused]] static std::string demangle(char const* mangled_name) {
      |                                              ~~~~~~~~~~~~^~~~~~~~~~~~
At global scope:
cc1plus: note: unrecognized command-line option ‘-Wno-unknown-attributes’ may have been intended to silence earlier diagnostics
make[2]: *** [CMakeFiles/sshash_static.dir/build.make:90: CMakeFiles/sshash_static.dir/external/sshash/include/dictionary.cpp.o] Error 1
make[1]: *** [CMakeFiles/Makefile2:112: CMakeFiles/sshash_static.dir/all] Error 2
make: *** [Makefile:91: all] Error 2

Feature request: creates a distinct color for each sequence in the input file

Hi @jermp !
Could you provide some option similar to Themisto one to handle one fasta file that contain many sequence that should be considered of different colors?

-e, --sequence-colors Default if the input has just a single sequence
file. Creates a distinct color 0,1,2,... for
each sequence in the input.

How does fulgor handle multi-mappers?

Hi-
I was curious if you could help me understand what happens in the case of multi-mappers, ie a given sequence that appears multiple times in the same reference. In your example with 4,546 Salmonella genomes, my guess is that there are repetitive sequences within a given genome - is the pseudo-alignment only capable of saying whether or not a given sequence occurred (n >= 1 times) or is it possible to know the exact number of times there was a match within a genome, or even more specifically, where the match(es) occurred?

Num_contigs must be less than 2^32 Aborted (core dumped)

Hey!

I was trying to build a graph of 400K bacterial genomes and got the following error:

terminate called after throwing an instance of 'std::runtime_error'
  what():  num_contigs must be less than 2^32
Aborted (core dumped)

1. I'm a bit confused by the error message with num_contigs as the number of contigs I have is much less (99,645,800) So I guess this refers to the number of unitigs in the graph instead?

2. If Yes, any ideas to still make it work? Could it use 2^64 since we have sufficient memory? Any other ideas ? :)

Thanks for another cool tool!

Fulgor build failed because of 128bits integers

Hello @jermp!
I'm trying to build fulgor and I got such compilation problem on several machines using gcc11 and 12

In file included from /home/malfoy/devel/fulgor/tools/../include/index.hpp:6,
from /home/malfoy/devel/fulgor/tools/../include/index_types.hpp:3,
from /home/malfoy/devel/fulgor/tools/fulgor.cpp:4:
/home/malfoy/devel/fulgor/tools/../include/util.hpp: In function ‘__int128 unsigned fulgor::util::hash128(const char*, uint64_t, uint64_t)’:
/home/malfoy/devel/fulgor/tools/../include/util.hpp:143:41: warning: dereferencing type-punned pointer will break strict-aliasing rules [-Wstrict-aliasing]
143 | (reinterpret_cast<uint64_t>(&out) + 0) = ret.first;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
In file included from /usr/include/c++/12/bits/hashtable.h:35,
from /usr/include/c++/12/unordered_map:46,
from /home/malfoy/devel/fulgor/tools/../include/../external/sshash/include/../external/pthash/include/encoders/encoders.hpp:8,
from /home/malfoy/devel/fulgor/tools/../include/../external/sshash/include/../external/pthash/include/pthash.hpp:3,
from /home/malfoy/devel/fulgor/tools/../include/../external/sshash/include/hash_util.hpp:3,
from /home/malfoy/devel/fulgor/tools/../include/../external/sshash/include/util.hpp:8,
from /home/malfoy/devel/fulgor/tools/../include/../external/sshash/include/dictionary.hpp:3,
from /home/malfoy/devel/fulgor/tools/../include/index.hpp:3:
/usr/include/c++/12/bits/hashtable_policy.h: In instantiation of ‘std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::__hash_code std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_M_hash_code(const _Key&) const [with _Key = __int128 unsigned; _Value = std::pair<const __int128 unsigned, unsigned int>; _ExtractKey = std::__detail::_Select1st; _Hash = std::hash<__int128 unsigned>; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true; __hash_code = long unsigned int]’:
/usr/include/c++/12/bits/hashtable.h:1653:46: required from ‘std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::iterator std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::find(const key_type&) [with _Key = __int128 unsigned; _Value = std::pair<const __int128 unsigned, unsigned int>; _Alloc = std::allocator<std::pair<const __int128 unsigned, unsigned int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<__int128 unsigned>; _Hash = std::hash<__int128 unsigned>; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>; iterator = std::__detail::_Insert_base<__int128 unsigned, std::pair<const __int128 unsigned, unsigned int>, std::allocator<std::pair<const __int128 unsigned, unsigned int> >, std::__detail::_Select1st, std::equal_to<__int128 unsigned>, std::hash<__int128 unsigned>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::iterator; key_type = __int128 unsigned]’
/usr/include/c++/12/bits/unordered_map.h:869:25: required from ‘std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::find(const key_type&) [with _Key = __int128 unsigned; _Tp = unsigned int; _Hash = std::hash<__int128 unsigned>; _Pred = std::equal_to<__int128 unsigned>; _Alloc = std::allocator<std::pair<const __int128 unsigned, unsigned int> >; iterator = std::__detail::_Insert_base<__int128 unsigned, std::pair<const __int128 unsigned, unsigned int>, std::allocator<std::pair<const __int128 unsigned, unsigned int> >, std::__detail::_Select1st, std::equal_to<__int128 unsigned>, std::hash<__int128 unsigned>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::iterator; key_type = __int128 unsigned]’
/home/malfoy/devel/fulgor/tools/../include/meta_builder.hpp:187:52: required from ‘void fulgor::index::meta_builder::build(fulgor::index&) [with ColorClasses = fulgor::metafulgor::hybrid]’
/home/malfoy/devel/fulgor/tools/build.cpp:9:18: required from here
/usr/include/c++/12/bits/hashtable_policy.h:1268:23: error: static assertion failed: hash function must be invocable with an argument of key type
1268 | static_assert(__is_invocable<const _Hash&, const _Key&>{},
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/12/bits/hashtable_policy.h:1268:23: note: ‘std::__is_invocable<const std::hash<__int128 unsigned>&, const __int128 unsigned&>()’ evaluates to false
/usr/include/c++/12/bits/hashtable_policy.h:1270:25: error: no match for call to ‘(const std::hash<__int128 unsigned>) (const __int128 unsigned&)’
1270 | return _M_hash()(__k);
| ~~~~~~~~~^~~~~
/usr/include/c++/12/bits/hashtable.h: In instantiation of ‘std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_Hashtable() [with _Key = __int128 unsigned; _Value = std::pair<const __int128 unsigned, unsigned int>; _Alloc = std::allocator<std::pair<const __int128 unsigned, unsigned int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<__int128 unsigned>; _Hash = std::hash<__int128 unsigned>; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>]’:
/usr/include/c++/12/bits/unordered_map.h:102:11: required from ‘constexpr void std::_Destroy(_Tp*) [with _Tp = unordered_map<__int128 unsigned, unsigned int>]’
/usr/include/c++/12/bits/stl_construct.h:163:19: required from ‘static void std::_Destroy_aux< >::__destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = std::unordered_map<__int128 unsigned, unsigned int>; bool = false]’
/usr/include/c++/12/bits/stl_construct.h:196:11: required from ‘void std::_Destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = unordered_map<__int128 unsigned, unsigned int>]’
/usr/include/c++/12/bits/alloc_traits.h:850:15: required from ‘void std::_Destroy(_ForwardIterator, _ForwardIterator, allocator<_T2>&) [with _ForwardIterator = unordered_map<__int128 unsigned, unsigned int>*; _Tp = unordered_map<__int128 unsigned, unsigned int>]’
/usr/include/c++/12/bits/stl_vector.h:730:15: required from ‘std::vector<_Tp, _Alloc>::vector() [with _Tp = std::unordered_map<__int128 unsigned, unsigned int>; _Alloc = std::allocator<std::unordered_map<__int128 unsigned, unsigned int> >]’
/home/malfoy/devel/fulgor/tools/../include/meta_builder.hpp:179:68: required from ‘void fulgor::index::meta_builder::build(fulgor::index&) [with ColorClasses = fulgor::metafulgor::hybrid]’
/home/malfoy/devel/fulgor/tools/build.cpp:9:18: required from here
/usr/include/c++/12/bits/hashtable.h:1586:5: error: use of deleted function ‘std::__detail::_Hashtable_base<__int128 unsigned, std::pair<const __int128 unsigned, unsigned int>, std::__detail::_Select1st, std::equal_to<__int128 unsigned>, std::hash<__int128 unsigned>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, false, true> >::_Hashtable_base()’
1586 | }
| ^
/usr/include/c++/12/bits/hashtable_policy.h:1631:12: note: ‘std::__detail::_Hashtable_base<__int128 unsigned, std::pair<const __int128 unsigned, unsigned int>, std::__detail::_Select1st, std::equal_to<__int128 unsigned>, std::hash<__int128 unsigned>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, false, true> >::_Hashtable_base()’ is implicitly deleted because the default definition would be ill-formed:
1631 | struct _Hashtable_base
| ^~~~~~~~~~~~~~~
/usr/include/c++/12/bits/hashtable_policy.h:1631:12: error: use of deleted function ‘std::__detail::_Hash_code_base<__int128 unsigned, std::pair<const __int128 unsigned, unsigned int>, std::__detail::_Select1st, std::hash<__int128 unsigned>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>::_Hash_code_base()’
/usr/include/c++/12/bits/hashtable_policy.h:1239:12: note: ‘std::__detail::_Hash_code_base<__int128 unsigned, std::pair<const __int128 unsigned, unsigned int>, std::__detail::_Select1st, std::hash<__int128 unsigned>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>::_Hash_code_base()’ is implicitly deleted because the default definition would be ill-formed:
1239 | struct _Hash_code_base
| ^~~~~~~~~~~~~~~
/usr/include/c++/12/bits/hashtable_policy.h:1239:12: error: use of deleted function ‘std::__detail::_Hashtable_ebo_helper<1, std::hash<__int128 unsigned>, true>::_Hashtable_ebo_helper()’
/usr/include/c++/12/bits/hashtable_policy.h:1175:12: note: ‘std::__detail::_Hashtable_ebo_helper<1, std::hash<__int128 unsigned>, true>::_Hashtable_ebo_helper()’ is implicitly deleted because the default definition would be ill-formed:
1175 | struct _Hashtable_ebo_helper<_Nm, _Tp, true>
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/12/bits/hashtable_policy.h:1175:12: error: use of deleted function ‘std::hash<__int128 unsigned>::hash()’
In file included from /usr/include/c++/12/string_view:43,
from /usr/include/c++/12/bits/basic_string.h:47,
from /usr/include/c++/12/string:53,
from /usr/include/c++/12/bits/locale_classes.h:40,
from /usr/include/c++/12/bits/ios_base.h:41,
from /usr/include/c++/12/ios:42,
from /usr/include/c++/12/ostream:38,
from /usr/include/c++/12/iostream:39,
from /home/malfoy/devel/fulgor/tools/fulgor.cpp:1:
/usr/include/c++/12/bits/functional_hash.h:102:12: note: ‘std::hash<__int128 unsigned>::hash()’ is implicitly deleted because the default definition would be ill-formed:
102 | struct hash : __hash_enum<_Tp>
| ^~~~
/usr/include/c++/12/bits/functional_hash.h:102:12: error: ‘std::__hash_enum<_Tp, >::__hash_enum() [with _Tp = __int128 unsigned; bool = false]’ is private within this context
/usr/include/c++/12/bits/functional_hash.h:84:7: note: declared private here
84 | __hash_enum();
| ^
In file included from /usr/include/c++/12/bits/alloc_traits.h:33,
from /usr/include/c++/12/ext/alloc_traits.h:34,
from /usr/include/c++/12/bits/basic_string.h:39:
/usr/include/c++/12/bits/stl_construct.h: In instantiation of ‘void std::_Construct(_Tp*, _Args&& ...) [with _Tp = unordered_map<__int128 unsigned, unsigned int>; _Args = {}]’:
/usr/include/c++/12/bits/stl_uninitialized.h:638:18: required from ‘static _ForwardIterator std::__uninitialized_default_n_1<_TrivialValueType>::__uninit_default_n(_ForwardIterator, _Size) [with _ForwardIterator = std::unordered_map<__int128 unsigned, unsigned int>; _Size = long unsigned int; bool _TrivialValueType = false]’
/usr/include/c++/12/bits/stl_uninitialized.h:701:20: required from ‘_ForwardIterator std::__uninitialized_default_n(_ForwardIterator, _Size) [with _ForwardIterator = unordered_map<__int128 unsigned, unsigned int>; _Size = long unsigned int]’
/usr/include/c++/12/bits/stl_uninitialized.h:766:44: required from ‘_ForwardIterator std::__uninitialized_default_n_a(_ForwardIterator, _Size, allocator<_Tp>&) [with _ForwardIterator = unordered_map<__int128 unsigned, unsigned int>; _Size = long unsigned int; _Tp = unordered_map<__int128 unsigned, unsigned int>]’
/usr/include/c++/12/bits/vector.tcc:644:35: required from ‘void std::vector<_Tp, _Alloc>::_M_default_append(size_type) [with _Tp = std::unordered_map<__int128 unsigned, unsigned int>; _Alloc = std::allocator<std::unordered_map<__int128 unsigned, unsigned int> >; size_type = long unsigned int]’
/usr/include/c++/12/bits/stl_vector.h:1011:4: required from ‘void std::vector<_Tp, _Alloc>::resize(size_type) [with _Tp = std::unordered_map<__int128 unsigned, unsigned int>; _Alloc = std::allocator<std::unordered_map<__int128 unsigned, unsigned int> >; size_type = long unsigned int]’
/home/malfoy/devel/fulgor/tools/../include/meta_builder.hpp:180:26: required from ‘void fulgor::index::meta_builder::build(fulgor::index&) [with ColorClasses = fulgor::metafulgor::hybrid]’
/home/malfoy/devel/fulgor/tools/build.cpp:9:18: required from here
/usr/include/c++/12/bits/stl_construct.h:119:7: error: use of deleted function ‘std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = __int128 unsigned; _Tp = unsigned int; _Hash = std::hash<__int128 unsigned>; _Pred = std::equal_to<__int128 unsigned>; _Alloc = std::allocator<std::pair<const __int128 unsigned, unsigned int> >]’
119 | ::new((void)__p) _Tp(std::forward<_Args>(__args)...);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/12/unordered_map:47:
/usr/include/c++/12/bits/unordered_map.h:141:7: note: ‘std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = __int128 unsigned; _Tp = unsigned int; _Hash = std::hash<__int128 unsigned>; _Pred = std::equal_to<__int128 unsigned>; _Alloc = std::allocator<std::pair<const __int128 unsigned, unsigned int> >]’ is implicitly deleted because the default definition would be ill-formed:
141 | unordered_map() = default;
| ^~~~~~~~~~~~~
/usr/include/c++/12/bits/unordered_map.h:141:7: error: use of deleted function ‘std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_Hashtable() [with _Key = __int128 unsigned; _Value = std::pair<const __int128 unsigned, unsigned int>; _Alloc = std::allocator<std::pair<const __int128 unsigned, unsigned int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<__int128 unsigned>; _Hash = std::hash<__int128 unsigned>; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>]’
/usr/include/c++/12/bits/hashtable.h:531:7: note: ‘std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_Hashtable() [with _Key = __int128 unsigned; _Value = std::pair<const __int128 unsigned, unsigned int>; _Alloc = std::allocator<std::pair<const __int128 unsigned, unsigned int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<__int128 unsigned>; _Hash = std::hash<__int128 unsigned>; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>]’ is implicitly deleted because the default definition would be ill-formed:
531 | _Hashtable() = default;
| ^~~~~~~~~~
/usr/include/c++/12/bits/hashtable.h:531:7: error: use of deleted function ‘std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _Traits>::_Hashtable_base() [with _Key = __int128 unsigned; _Value = std::pair<const __int128 unsigned, unsigned int>; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<__int128 unsigned>; _Hash = std::hash<__int128 unsigned>; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, false, true>]’
/usr/include/c++/12/bits/hashtable_policy.h:1674:7: note: ‘std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _Traits>::_Hashtable_base() [with _Key = __int128 unsigned; _Value = std::pair<const __int128 unsigned, unsigned int>; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<__int128 unsigned>; _Hash = std::hash<__int128 unsigned>; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, false, true>]’ is implicitly deleted because the default definition would be ill-formed:
1674 | _Hashtable_base() = default;
| ^~~~~~~~~~~~~~~
/usr/include/c++/12/bits/hashtable_policy.h:1674:7: error: use of deleted function ‘std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_Hash_code_base() [with _Key = __int128 unsigned; _Value = std::pair<const __int128 unsigned, unsigned int>; _ExtractKey = std::__detail::_Select1st; _Hash = std::hash<__int128 unsigned>; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true]’
/usr/include/c++/12/bits/hashtable_policy.h:1261:7: note: ‘std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_Hash_code_base() [with _Key = __int128 unsigned; _Value = std::pair<const __int128 unsigned, unsigned int>; _ExtractKey = std::__detail::_Select1st; _Hash = std::hash<__int128 unsigned>; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true]’ is implicitly deleted because the default definition would be ill-formed:
1261 | _Hash_code_base() = default;
| ^~~~~~~~~~~~~~~
/usr/include/c++/12/bits/hashtable_policy.h:1261:7: error: use of deleted function ‘std::__detail::_Hashtable_ebo_helper<1, std::hash<__int128 unsigned>, true>::_Hashtable_ebo_helper()’
/usr/include/c++/12/bits/hashtable_policy.h:1674:7: error: use of deleted function ‘std::__detail::_Hash_code_base<__int128 unsigned, std::pair<const __int128 unsigned, unsigned int>, std::__detail::_Select1st, std::hash<__int128 unsigned>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>::_Hash_code_base()’
1674 | _Hashtable_base() = default;
| ^~~~~~~~~~~~~~~
/usr/include/c++/12/bits/hashtable.h:531:7: error: use of deleted function ‘std::__detail::_Hashtable_base<__int128 unsigned, std::pair<const __int128 unsigned, unsigned int>, std::__detail::_Select1st, std::equal_to<__int128 unsigned>, std::hash<__int128 unsigned>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, false, true> >::_Hashtable_base()’
531 | _Hashtable() = default;
| ^~~~~~~~~~
/usr/include/c++/12/bits/hashtable.h:531:7: error: use of deleted function ‘constexpr std::_Enable_default_constructor<false, _Tag>::_Enable_default_constructor() [with _Tag = std::__detail::_Hash_node_base]’
In file included from /usr/include/c++/12/bits/hashtable.h:36:
/usr/include/c++/12/bits/enable_special_members.h:113:15: note: declared here
113 | constexpr _Enable_default_constructor() noexcept = delete;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/12/bits/hashtable.h: In instantiation of ‘std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_Hashtable(const std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>&) [with _Key = __int128 unsigned; _Value = std::pair<const __int128 unsigned, unsigned int>; _Alloc = std::allocator<std::pair<const __int128 unsigned, unsigned int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<__int128 unsigned>; _Hash = std::hash<__int128 unsigned>; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>]’:
/usr/include/c++/12/bits/unordered_map.h:181:7: required from ‘void std::_Construct(_Tp*, _Args&& ...) [with _Tp = unordered_map<__int128 unsigned, unsigned int>; _Args = {const unordered_map<__int128 unsigned, unsigned int, hash<__int128 unsigned>, equal_to<__int128 unsigned>, allocator<pair<const __int128 unsigned, unsigned int> > >&}]’
/usr/include/c++/12/bits/stl_uninitialized.h:120:21: required from ‘_ForwardIterator std::__do_uninit_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = const unordered_map<__int128 unsigned, unsigned int>; _ForwardIterator = unordered_map<__int128 unsigned, unsigned int>]’
/usr/include/c++/12/bits/stl_uninitialized.h:137:32: required from ‘static _ForwardIterator std::__uninitialized_copy<_TrivialValueTypes>::__uninit_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = const std::unordered_map<__int128 unsigned, unsigned int>; _ForwardIterator = std::unordered_map<__int128 unsigned, unsigned int>; bool _TrivialValueTypes = false]’
/usr/include/c++/12/bits/stl_uninitialized.h:185:15: required from ‘_ForwardIterator std::uninitialized_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = const unordered_map<__int128 unsigned, unsigned int>; _ForwardIterator = unordered_map<__int128 unsigned, unsigned int>]’
/usr/include/c++/12/bits/stl_uninitialized.h:372:37: required from ‘_ForwardIterator std::__uninitialized_copy_a(_InputIterator, _InputIterator, _ForwardIterator, allocator<_Tp>&) [with _InputIterator = const unordered_map<__int128 unsigned, unsigned int>; _ForwardIterator = unordered_map<__int128 unsigned, unsigned int>; _Tp = unordered_map<__int128 unsigned, unsigned int>]’
/usr/include/c++/12/bits/stl_uninitialized.h:397:2: required from ‘_ForwardIterator std::__uninitialized_move_if_noexcept_a(_InputIterator, _InputIterator, _ForwardIterator, _Allocator&) [with _InputIterator = unordered_map<__int128 unsigned, unsigned int>; _ForwardIterator = unordered_map<__int128 unsigned, unsigned int>; _Allocator = allocator<unordered_map<__int128 unsigned, unsigned int> >]’
/usr/include/c++/12/bits/vector.tcc:681:48: required from ‘void std::vector<_Tp, _Alloc>::_M_default_append(size_type) [with _Tp = std::unordered_map<__int128 unsigned, unsigned int>; _Alloc = std::allocator<std::unordered_map<__int128 unsigned, unsigned int> >; size_type = long unsigned int]’
/usr/include/c++/12/bits/stl_vector.h:1011:4: required from ‘void std::vector<_Tp, _Alloc>::resize(size_type) [with _Tp = std::unordered_map<__int128 unsigned, unsigned int>; _Alloc = std::allocator<std::unordered_map<__int128 unsigned, unsigned int> >; size_type = long unsigned int]’
/home/malfoy/devel/fulgor/tools/../include/meta_builder.hpp:180:26: required from ‘void fulgor::index::meta_builder::build(fulgor::index&) [with ColorClasses = fulgor::metafulgor::hybrid]’
/home/malfoy/devel/fulgor/tools/build.cpp:9:18: required from here
/usr/include/c++/12/bits/hashtable.h:1461:45: error: use of deleted function ‘std::__detail::_Hashtable_base<__int128 unsigned, std::pair<const __int128 unsigned, unsigned int>, std::__detail::_Select1st, std::equal_to<__int128 unsigned>, std::hash<__int128 unsigned>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, false, true> >::_Hashtable_base(const std::__detail::_Hashtable_base<__int128 unsigned, std::pair<const __int128 unsigned, unsigned int>, std::__detail::_Select1st, std::equal_to<__int128 unsigned>, std::hash<__int128 unsigned>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, false, true> >&)’
1461 | _M_rehash_policy(__ht._M_rehash_policy)
| ^
/usr/include/c++/12/bits/hashtable_policy.h:1631:12: note: ‘std::__detail::_Hashtable_base<__int128 unsigned, std::pair<const __int128 unsigned, unsigned int>, std::__detail::_Select1st, std::equal_to<__int128 unsigned>, std::hash<__int128 unsigned>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, false, true> >::_Hashtable_base(const std::__detail::_Hashtable_base<__int128 unsigned, std::pair<const __int128 unsigned, unsigned int>, std::__detail::_Select1st, std::equal_to<__int128 unsigned>, std::hash<__int128 unsigned>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, false, true> >&)’ is implicitly deleted because the default definition would be ill-formed:
1631 | struct _Hashtable_base
| ^~~~~~~~~~~~~~~
/usr/include/c++/12/bits/hashtable_policy.h:1631:12: error: use of deleted function ‘std::__detail::_Hash_code_base<__int128 unsigned, std::pair<const __int128 unsigned, unsigned int>, std::__detail::_Select1st, std::hash<__int128 unsigned>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>::_Hash_code_base(const std::__detail::_Hash_code_base<__int128 unsigned, std::pair<const __int128 unsigned, unsigned int>, std::__detail::_Select1st, std::hash<__int128 unsigned>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>&)’
/usr/include/c++/12/bits/hashtable_policy.h:1239:12: note: ‘std::__detail::_Hash_code_base<__int128 unsigned, std::pair<const __int128 unsigned, unsigned int>, std::__detail::_Select1st, std::hash<__int128 unsigned>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>::_Hash_code_base(const std::__detail::_Hash_code_base<__int128 unsigned, std::pair<const __int128 unsigned, unsigned int>, std::__detail::_Select1st, std::hash<__int128 unsigned>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>&)’ is implicitly deleted because the default definition would be ill-formed:
1239 | struct _Hash_code_base
| ^~~~~~~~~~~~~~~
/usr/include/c++/12/bits/hashtable_policy.h:1239:12: error: use of deleted function ‘std::__detail::_Hashtable_ebo_helper<1, std::hash<__int128 unsigned>, true>::_Hashtable_ebo_helper(const std::__detail::_Hashtable_ebo_helper<1, std::hash<__int128 unsigned>, true>&)’
/usr/include/c++/12/bits/hashtable_policy.h:1175:12: note: ‘std::__detail::_Hashtable_ebo_helper<1, std::hash<__int128 unsigned>, true>::_Hashtable_ebo_helper(const std::__detail::_Hashtable_ebo_helper<1, std::hash<__int128 unsigned>, true>&)’ is implicitly deleted because the default definition would be ill-formed:
1175 | struct _Hashtable_ebo_helper<_Nm, _Tp, true>
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/12/bits/hashtable_policy.h:1175:12: error: use of deleted function ‘std::hash<__int128 unsigned>::hash(const std::hash<__int128 unsigned>&)’
/usr/include/c++/12/bits/functional_hash.h:102:12: note: ‘std::hash<__int128 unsigned>::hash(const std::hash<__int128 unsigned>&)’ is implicitly deleted because the default definition would be ill-formed:
102 | struct hash : __hash_enum<_Tp>
| ^~~~
/usr/include/c++/12/bits/functional_hash.h:102:12: error: use of deleted function ‘constexpr std::__hash_enum<__int128 unsigned, false>::__hash_enum(const std::__hash_enum<__int128 unsigned, false>&)’
/usr/include/c++/12/bits/functional_hash.h:79:12: note: ‘constexpr std::__hash_enum<__int128 unsigned, false>::__hash_enum(const std::__hash_enum<__int128 unsigned, false>&)’ is implicitly declared as deleted because ‘std::__hash_enum<__int128 unsigned, false>’ declares a move constructor or move assignment operator
79 | struct __hash_enum
| ^~~~~~~~~~~
/usr/include/c++/12/bits/functional_hash.h:102:12: error: ‘std::__hash_enum<_Tp, >::__hash_enum() [with _Tp = __int128 unsigned; bool = false]’ is private within this context
102 | struct hash : __hash_enum<_Tp>
| ^~~~
/usr/include/c++/12/bits/functional_hash.h:84:7: note: declared private here
84 | __hash_enum();
| ^
/usr/include/c++/12/bits/hashtable_policy.h:1175:12: error: use of deleted function ‘std::hash<__int128 unsigned>::hash()’
1175 | struct _Hashtable_ebo_helper<_Nm, _Tp, true>
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/12/bits/hashtable_policy.h:1239:12: error: use of deleted function ‘std::__detail::_Hashtable_ebo_helper<1, std::hash<__int128 unsigned>, true>::_Hashtable_ebo_helper()’
1239 | struct _Hash_code_base
| ^~~~~~~~~~~~~~~
/usr/include/c++/12/bits/hashtable_policy.h:1631:12: error: use of deleted function ‘std::__detail::_Hash_code_base<__int128 unsigned, std::pair<const __int128 unsigned, unsigned int>, std::__detail::_Select1st, std::hash<__int128 unsigned>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>::_Hash_code_base()’
1631 | struct _Hashtable_base
| ^~~~~~~~~~~~~~~
/usr/include/c++/12/bits/hashtable.h:1461:45: error: use of deleted function ‘std::__detail::_Hashtable_base<__int128 unsigned, std::pair<const __int128 unsigned, unsigned int>, std::__detail::_Select1st, std::equal_to<__int128 unsigned>, std::hash<__int128 unsigned>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, false, true> >::~_Hashtable_base()’
1461 | _M_rehash_policy(__ht._M_rehash_policy)

How to interpret the color dump file?

Hello team Fulgor!

I'm trying to dump the color sets out of a Fulgor index. The dump looks like this:

num_references 4896
num_lists_in_color_set 3607699
color_list_0 7 24 405 1442 1561 2243 2767 3402
color_list_1 4 24 405 2243 3402
color_list_2 5 24 272 405 2243 3402
color_list_3 2 737 1312
...

This seems to list all the distinct color sets, but this is missing the information about which color set corresponds to which unitig. Is it possible to somehow easily extract that information from the index? This would let me verify my Themisto indexes against Fulgor, and vice versa.

By the way, this dump is missing a newline at the end of the file :).

Error in ggcat_querier compilation

When installing on a x86_64 Linux system, during the GGCAT API compilation step the following error occurs

error: to use a constant of type `TypeId` in a pattern, `TypeId` must be annotated with `#[derive(PartialEq, Eq)]`

However, if I manually check out GGCAT repo at 793471d, and then proceed with the compilation, everything compiles correctly. (I am using nightly Rust)

It looks that the ggcat repo in the external should be updated to the above version, instead of the one it uses right now.

Compilation error

I get this error when I try to build fulgor. It works when I compile it with “-mpopcnt” flag. Would it be possible to make a commit with “-mpopcnt” flag in the CMakeLists.txt?

I am using FULGOR in one of my projects and it would be easier to integrate it into my pipeline if the flag was added to the CMakeLists.

Thank you.