seqwish 0.1.0

A variation graph inducer - build pangenome graphs from pairwise alignments
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

#include "BooPHF.h"

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <sys/types.h>
#include <random>
#include <algorithm>

using namespace std;



//example with user provided custom hasher for uint64_t type :

class Custom_uint64_Hasher
{
public:
	// the class should have operator () with this signature :
	// BBhash will use the 'seed' paramater to generate two different hash values form this key.
     //then it will generate internally a sequence of hash values using xorshifts, using these two first hash values as starting point.
	uint64_t operator ()   (uint64_t key, uint64_t seed=0) const
	{
		
		key ^= key >> 33;
		key *= 0xff51afd7ed558ccd;
		key ^= key >> 33;
		key *= 0xc4ceb9fe1a85ec53;
		key ^= key >> 33;
		
		key ^= seed;
		
		return key;
	}
};


//then tell BBhash to use this custom hash : (also appears below, line 104)
typedef boomphf::mphf<  u_int64_t, Custom_uint64_Hasher  > boophf_t;


int main (int argc, char* argv[]){
	
	//PARAMETERS
	u_int64_t nelem = 1000000;
	uint nthreads = 1;

	if(argc !=3 ){
		printf("Usage :\n");
		printf("%s <nelem> <nthreads> \n",argv[0]);
		return EXIT_FAILURE;
	}
	
	if(argc ==3 ){
		nelem = strtoul(argv[1], NULL,0);
		nthreads = atoi(argv[2]);
	}
	
	uint64_t ii, jj;
	u_int64_t *data;

	/////  generation of random keys
	uint64_t rab = 100;
	static std::mt19937_64 rng;
	rng.seed(std::mt19937_64::default_seed); //default seed
	
	//rng.seed(seed2); //random seed from timer
	data = (u_int64_t * ) calloc(nelem+rab,sizeof(u_int64_t));
	
	for (u_int64_t i = 1; i < nelem+rab; i++){
		data[i] = rng();
	}
	printf("de-duplicating items \n");
	
	std::sort(data,data+nelem+rab);
	
	for (ii = 1, jj = 0; ii < nelem+rab; ii++) {
		if (data[ii] != data[jj])
			data[++jj] = data[ii];
	}
	printf("found %lli duplicated items  \n",nelem+rab-(jj + 1) );
	
	//////////////////
	// at this point, array data contains a set of nelem random unique keys
	
	
	boophf_t * bphf = NULL;
	double t_begin,t_end; struct timeval timet;
	
	
	printf("Construct a BooPHF with  %lli elements  \n",nelem);
	
	gettimeofday(&timet, NULL); t_begin = timet.tv_sec +(timet.tv_usec/1000000.0);
	
	// mphf takes as input a c++ range. A simple array of keys can be wrapped with boomphf::range
	// but could be from a user defined iterator (enabling keys to be read from a file or from some complex non-contiguous structure)
	auto data_iterator = boomphf::range(static_cast<const u_int64_t*>(data), static_cast<const u_int64_t*>(data+nelem));
	
	double gammaFactor = 2.0; // lowest bit/elem is achieved with gamma=1, higher values lead to larger mphf but faster construction/query
	// gamma = 2 is a good tradeoff (leads to approx 3.7 bits/key )

	//build the mphf
	bphf = new boomphf::mphf<u_int64_t,Custom_uint64_Hasher>(nelem,data_iterator,nthreads,gammaFactor);
	
	gettimeofday(&timet, NULL); t_end = timet.tv_sec +(timet.tv_usec/1000000.0);
	double elapsed = t_end - t_begin;
	
	
	printf("BooPHF constructed perfect hash for %llu keys in %.2fs\n", nelem,elapsed);
	printf("boophf  bits/elem : %f\n",(float) (bphf->totalBitSize())/nelem);
	
	//query mphf like this
	uint64_t  idx = bphf->lookup(data[0]);
	printf(" example query  %lli ----->  %llu \n",data[0],idx);
	
	free(data);
	delete bphf;
	return EXIT_SUCCESS;
}