ahmadyan

// Fastest implementation of the BFS algorithm with std::vector, if we don't care about the ordering
int bfs_vector_no_order(Graph* g){
	int sig=0;
	vector<bool> visited(g->getSize(), false);
	vector<int> q; 
	q.reserve(10);
	auto init = rand()%g->getSize();
	q.push_back(init);
	visited[init]=true;
	while(!q.empty()){

ahmadyan

// This is the optimal implementation of BFS with deque
int bfs_deque(Graph* g){
	int sig=0;
	vector<bool> visited(g->getSize(), false);
	deque<int> q; 
	auto init = rand()%g->getSize();
	q.push_back(init);
	visited[init]=true;
	while(!q.empty()){
		auto u = q.front(); 

ahmadyan

int bfs_deque(Graph* g){
	int sig=0;
	vector<bool> visited(g->getSize(), false);
	deque<int> q; 
	auto init = rand()%g->getSize();
	q.push_back(init);
	visited[init]=true;
	while(!q.empty()){
		auto u = q.front(); 

ahmadyan

//list is basically a linked-list
int bfs_list(Graph* g){
  int sig=0;
  vector<bool> visited(g->getSize(), false);
  list<int> q; 
  auto init = rand()%g->getSize();
  q.push_back(init);
  visited[init]=true;
  while(!q.empty()){
    auto u = q.front(); 

ahmadyan

size_t count() const
{   // count number of set bits
  static char _Bitsperhex[] = "\0\1\1\2\1\2\2\3\1\2\2\3\2\3\3\4";
  size_t _Val = 0;
  for (int _Wpos = _Words; 0 <= _Wpos; --_Wpos)
      for (_Ty _Wordval = _Array[_Wpos]; _Wordval != 0; _Wordval >>= 4)
          _Val += _Bitsperhex[_Wordval & 0xF];
  return (_Val);
}

ahmadyan

#include<bitset>
unsigned long long int v;
bitset<64> n(v);
int count = n.count();
auto v2 = n.to_ullong();

ahmadyan

unsigned long long int v; //counts the number of bits set in v
unsigned int count=0;     // counts is the total bits set in v
while(v){
	v &= v-1;
	c++;
}

ahmadyan

void mc(double r, double** samples){
    cout << "Monte Carlo simulation" << endl ;
    using namespace boost::math;
    
    double sample_inside=0;
    cout << "sizeof(sample_count)=" << sizeof(samples) << endl ;
    for(int i=0;i<sample_count;i++){
        double x = samples[i][0];
        double y = samples[i][1];
        

ahmadyan

void verify(double r, double** samples){
    DT dt2;
    VD vd;
    Cropped_voronoi_from_delaunay vor;
    
    Iso_rectangle_2 bbox(0,0,1,1);
    vor = Cropped_voronoi_from_delaunay(bbox);
    for(int i=0;i< sample_count;i++){
        vd.insert( Site_2( samples[i][0], samples[i][1] ) );
    }

ahmadyan

void demo(){
    double r = 0.5 ;
    double area = M_PI * r * r;
    double** samples = new double*[sample_count];
    for(int i=0;i<sample_count;i++){
        samples[i] = new double[2];
        samples[i][0] = 1.0*rand()/INT_MAX;
        samples[i][1] = 1.0*rand()/INT_MAX;
    }
    cout << "The exact area is " << area << endl ;