<commit_before>/*
 * DynamicHyperbolicGenerator.cpp
 *
 *  Created on: 29.07.2014
 *      Author: moritzl
 */

#include <cmath>

#include "DynamicHyperbolicGenerator.h"
#include "HyperbolicGenerator.h"
#include "../geometric/HyperbolicSpace.h"

using std::vector;
namespace NetworKit {

DynamicHyperbolicGenerator::DynamicHyperbolicGenerator() {
	// TODO Auto-generated constructor stub

}

DynamicHyperbolicGenerator::DynamicHyperbolicGenerator(count n, double initialFactor, double alpha, double stretch, double moveEachStep, double factorgrowth, double moveDistance) {
	nodes = n;
	currentfactor = initialFactor;
	this->alpha = alpha;
	this->stretch = stretch;
	this->moveEachStep = moveEachStep;
	this->factorgrowth = factorgrowth;
	this->moveDistance = moveDistance;
	this->initialized = false;
}

DynamicHyperbolicGenerator::DynamicHyperbolicGenerator(vector<double> &angles, vector<double> &radii, double R, double initialFactor, double moveEachStep, double factorgrowth, double moveDistance) {


	this->angles = angles;
	this->radii = radii;
	this->nodes = angles.size();
	assert(radii.size() == nodes);
	double r = HyperbolicSpace::hyperbolicRadiusToEuclidean(R);
	quad = Quadtree<index>(r);
	currentfactor = initialFactor;
	this->alpha = 1;//not needed any more
	this->stretch = 1;//not needed any more
	this->moveEachStep = moveEachStep;
	this->factorgrowth = factorgrowth;
	this->moveDistance = moveDistance;
	this->initialized = true;
	for (index i = 0; i < nodes; i++) {
		assert(radii[i] < r);
		quad.addContent(i, angles[i], radii[i]);
	}
	INFO("Filled Quadtree");
}

DynamicHyperbolicGenerator::~DynamicHyperbolicGenerator() {
	// TODO Auto-generated destructor stub
}

void DynamicHyperbolicGenerator::initializeQuadTree() {
	if (initialized) return;
	else initialized = true;
	double R = stretch*acosh((double)nodes/(2*M_PI)+1);
	angles.resize(nodes);
	radii.resize(nodes);
	double rad_nom = (cosh(R)-1);
	double rad_denom = (cosh(R)+1);
	double r = sqrt(rad_nom/rad_denom);
	quad = Quadtree<index>(r);
	HyperbolicSpace::fillPoints(&angles, &radii, stretch, alpha);
	INFO("Generated Points");
	for (index i = 0; i < nodes; i++) {
		assert(radii[i] < R);
		quad.addContent(i, angles[i], radii[i]);
	}
	INFO("Filled Quadtree");
}

Graph DynamicHyperbolicGenerator::getGraph() {
	if (!initialized) initializeQuadTree();//this is horribly expensive, since it constructs a new Quadtree
	double R = stretch*acosh((double)nodes/(2*M_PI)+1);
	double r = HyperbolicSpace::hyperbolicRadiusToEuclidean(R);
	/**
	 * The next call is unnecessarily expensive, since it constructs a new QuadTree.
	 * Reduces code duplication, though.
	 */
	return HyperbolicGenerator::generate(&angles, &radii, r, currentfactor*R);
}

std::vector<GraphEvent> DynamicHyperbolicGenerator::generate(count nSteps) {
	if (!initialized) initializeQuadTree();
	assert(quad.size() == nodes);
	vector<GraphEvent> result;
	double R = stretch*acosh((double)nodes/(2*M_PI)+1);

	for (index step = 0; step < nSteps; step++) {
		count oldStreamMarker = result.size();
		assert(factorgrowth == 0 || moveEachStep == 0 || moveDistance == 0);
		if (factorgrowth != 0) {
			//nodes are stationary, growing factors
			double newfactor = currentfactor + factorgrowth;
/**
 * most efficient way: get all neighbours in the beginning, sort them by hyperbolic distance, move along edge array. TODO: implement
 */
			//#pragma omp parallel for
			for (index i = 0; i < nodes; i++) {
				assert(R*newfactor > R*currentfactor);
				vector<index> oldset = quad.getCloseElements(HyperbolicSpace::polarToCartesian(angles[i], radii[i]), R*currentfactor);
				//we only add new edges, don't remove any. The order of the points should be the same
				vector<index> newset = quad.getCloseElements(HyperbolicSpace::polarToCartesian(angles[i], radii[i]), R*newfactor);
				assert(newset.size() >= oldset.size());

				std::sort(oldset.begin(), oldset.end());
				std::sort(newset.begin(), newset.end());
				vector<index> difference(newset.size());
				auto it = std::set_difference(newset.begin(), newset.end(), oldset.begin(), oldset.end(), difference.begin());
				difference.resize(it - difference.begin());

				//#pragma omp critical
				{
					for (auto edge : difference) {
						if (i < edge) {
							result.push_back(GraphEvent(GraphEvent::EDGE_ADDITION, i, edge));
						}
					}
				}

			}
			currentfactor = newfactor;
		}
		else {
			vector<index> toWiggle;
			vector<vector<index> > oldNeighbours;
			for (index i = 0; i < nodes; i++) {
				if (Aux::Random::real(1) < moveEachStep) {
					toWiggle.push_back(i);
					oldNeighbours.push_back(quad.getCloseElements(HyperbolicSpace::polarToCartesian(angles[i], radii[i]), R*currentfactor));
				}
			}
			for (index j = 0; j < toWiggle.size(); j++) {
				//wiggle this node!
				double hyperbolicRadius = HyperbolicSpace::EuclideanRadiusToHyperbolic(radii[toWiggle[j]]);
<commit_msg>reenabled parallelization in dynamic hyperbolic generator<commit_after>/*
 * DynamicHyperbolicGenerator.cpp
 *
 *  Created on: 29.07.2014
 *      Author: moritzl
 */

#include <cmath>

#include "DynamicHyperbolicGenerator.h"
#include "HyperbolicGenerator.h"
#include "../geometric/HyperbolicSpace.h"

using std::vector;
namespace NetworKit {

DynamicHyperbolicGenerator::DynamicHyperbolicGenerator() {
	// TODO Auto-generated constructor stub

}

DynamicHyperbolicGenerator::DynamicHyperbolicGenerator(count n, double initialFactor, double alpha, double stretch, double moveEachStep, double factorgrowth, double moveDistance) {
	nodes = n;
	currentfactor = initialFactor;
	this->alpha = alpha;
	this->stretch = stretch;
	this->moveEachStep = moveEachStep;
	this->factorgrowth = factorgrowth;
	this->moveDistance = moveDistance;
	this->initialized = false;
}

DynamicHyperbolicGenerator::DynamicHyperbolicGenerator(vector<double> &angles, vector<double> &radii, double R, double initialFactor, double moveEachStep, double factorgrowth, double moveDistance) {


	this->angles = angles;
	this->radii = radii;
	this->nodes = angles.size();
	assert(radii.size() == nodes);
	double r = HyperbolicSpace::hyperbolicRadiusToEuclidean(R);
	quad = Quadtree<index>(r);
	currentfactor = initialFactor;
	this->alpha = 1;//not needed any more
	this->stretch = 1;//not needed any more
	this->moveEachStep = moveEachStep;
	this->factorgrowth = factorgrowth;
	this->moveDistance = moveDistance;
	this->initialized = true;
	for (index i = 0; i < nodes; i++) {
		assert(radii[i] < r);
		quad.addContent(i, angles[i], radii[i]);
	}
	INFO("Filled Quadtree");
}

DynamicHyperbolicGenerator::~DynamicHyperbolicGenerator() {
	// TODO Auto-generated destructor stub
}

void DynamicHyperbolicGenerator::initializeQuadTree() {
	if (initialized) return;
	else initialized = true;
	double R = stretch*acosh((double)nodes/(2*M_PI)+1);
	angles.resize(nodes);
	radii.resize(nodes);
	double rad_nom = (cosh(R)-1);
	double rad_denom = (cosh(R)+1);
	double r = sqrt(rad_nom/rad_denom);
	quad = Quadtree<index>(r);
	HyperbolicSpace::fillPoints(&angles, &radii, stretch, alpha);
	INFO("Generated Points");
	for (index i = 0; i < nodes; i++) {
		assert(radii[i] < R);
		quad.addContent(i, angles[i], radii[i]);
	}
	INFO("Filled Quadtree");
}

Graph DynamicHyperbolicGenerator::getGraph() {
	if (!initialized) initializeQuadTree();//this is horribly expensive, since it constructs a new Quadtree
	double R = stretch*acosh((double)nodes/(2*M_PI)+1);
	double r = HyperbolicSpace::hyperbolicRadiusToEuclidean(R);
	/**
	 * The next call is unnecessarily expensive, since it constructs a new QuadTree.
	 * Reduces code duplication, though.
	 */
	return HyperbolicGenerator::generate(&angles, &radii, r, currentfactor*R);
}

std::vector<GraphEvent> DynamicHyperbolicGenerator::generate(count nSteps) {
	if (!initialized) initializeQuadTree();
	assert(quad.size() == nodes);
	vector<GraphEvent> result;
	double R = stretch*acosh((double)nodes/(2*M_PI)+1);

	for (index step = 0; step < nSteps; step++) {
		count oldStreamMarker = result.size();
		assert(factorgrowth == 0 || moveEachStep == 0 || moveDistance == 0);
		if (factorgrowth != 0) {
			//nodes are stationary, growing factors
			double newfactor = currentfactor + factorgrowth;
/**
 * most efficient way: get all neighbours in the beginning, sort them by hyperbolic distance, move along edge array. TODO: implement
 */
			#pragma omp parallel for
			for (index i = 0; i < nodes; i++) {
				assert(R*newfactor > R*currentfactor);
				vector<index> oldset = quad.getCloseElements(HyperbolicSpace::polarToCartesian(angles[i], radii[i]), R*currentfactor);
				//we only add new edges, don't remove any. The order of the points should be the same
				vector<index> newset = quad.getCloseElements(HyperbolicSpace::polarToCartesian(angles[i], radii[i]), R*newfactor);
				assert(newset.size() >= oldset.size());
				std::sort(oldset.begin(), oldset.end());
				std::sort(newset.begin(), newset.end());
				vector<index> difference(newset.size());
				auto it = std::set_difference(newset.begin(), newset.end(), oldset.begin(), oldset.end(), difference.begin());
				difference.resize(it - difference.begin());

				#pragma omp critical
				{
					for (auto edge : difference) {
						if (i < edge) {
							result.emplace_back(GraphEvent::EDGE_ADDITION, i, edge);
						}
					}
				}

			}
			currentfactor = newfactor;
		}
		else {
			vector<index> toWiggle;
			vector<vector<index> > oldNeighbours;
			for (index i = 0; i < nodes; i++) {
				if (Aux::Random::real(1) < moveEachStep) {
					toWiggle.push_back(i);
					oldNeighbours.push_back(quad.getCloseElements(HyperbolicSpace::polarToCartesian(angles[i], radii[i]), R*currentfactor));
				}
			}
			for (index j = 0; j < toWiggle.size(); j++) {
				//wiggle this node!
				double hyperbolicRadius = HyperbolicSpace::EuclideanRadiusToHyperbolic(radii[toWiggle[j]]);

{'fraction_non_alphanumeric': 0.14125788723794017, 'fraction_numerical': 0.005902707103602686, 'mean_word_length': 4.981132075471698, 'pattern_counts': {'":': 0, '<': 49, '<?xml version=': 0, '>': 63, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3011870', 'n_tokens_mistral': 3589, 'n_tokens_neox': 3155, 'n_words': 745}