123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463 |
- #include "pch.h"
- #include "GraphView.h"
- #include "RunData.h"
- #include <QDebug>
- #include <QString>
- #include <regex>
- #include <algorithm>
- RunData::RunData()
- {
- }
- RunData::RunData(std::string filePath) : fileStream(filePath), filePath(filePath)
- {
-
- std::string file = filePath.substr(filePath.find_last_of("/\\") + 1);
- name = file.substr(0, file.rfind("."));
- if (!fileStream.is_open())
- {
- //Cant open file
- badFileFlag = true;
- return;
- }
- std::string buffer;
- getLine(buffer);
- qDebug() << QString::fromStdString(buffer);
- /*bool retflag;
- metalogFile(retflag);
- if (retflag) return;*/
- std::string integerRegexString = "([\\+\\-]?\\d+)";
- std::string doubleRegexString = "([\\+\\-]?\\d+(?:\\.\\d+(?:E[\\+\\-]\\d+)?)?)";
- std::string binaryRegexString = "([01]+)";
- std::string seperator = ",";
- std::regex regexLine(integerRegexString
- + seperator + integerRegexString
- + seperator + integerRegexString
- + seperator + doubleRegexString
- + seperator + binaryRegexString);
- while (fileStream.peek() != EOF) {
- std::string buffer;
- getLine(buffer);
- SolutionPointData sol;
- std::smatch match;
- if (!std::regex_search(buffer, match, regexLine)) {
- qDebug() << "Bad formatatted Line[" << actualLine << "].";
- qDebug() << "Failed to matched:";
- qDebug() << QString::fromStdString(buffer);
- return;
- }
- sol.round = std::stoi(match[1]);
- sol.iteration = std::stoi(match[2]);
- sol.particleNumber = std::stoi(match[3]);
- sol.objectiveFunction = std::stod(match[4]);
- sol.bitVec.resize(match[5].length());
- std::string binaryString = match[5];
- for (std::string::size_type i = 0; i < binaryString.size(); ++i) {
- sol.bitVec[i] = (binaryString[i] == '1');
- }
- solutionVec.push_back(sol);
- }
- fileStream.close();
- qDebug() << "Import done";
-
- //Set Runs apart
- int count = 0;
- std::vector<SolutionPointData>::iterator begin = solutionVec.begin();
- for (auto iter = solutionVec.begin(); iter != solutionVec.end(); iter++) {
- if (iter->round != begin->round) {
- std::string endString("[");
- endString += std::to_string(count++);
- endString += "]";
- singleRunList.push_back(SingleRun(name, begin, iter, name + endString));
- begin = iter;
- }
- }
- std::string endString("[");
- endString += std::to_string(count);
- endString += "]";
- singleRunList.push_back(SingleRun(name, begin, solutionVec.end(), name + endString));
- //Generate PascalTriangle
- std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();
- int amountOfBits = begin->bitVec.size();
- int lines = amountOfBits + 1;
- std::vector<boost::multiprecision::cpp_int> pascalTriangleVec(((lines + 1) / 2 * (lines / 2 + 1)));
- for (int line = 0; line < lines; line++) {
- for (int number = 0; number < line + 1; number++) {
- if (number > line / 2) break;
- if (number == 0 || number == line) {
- pascalTriangleVec[binominalIndex(line, number)] = 1;
- }
- else {
- pascalTriangleVec[binominalIndex(line, number)] = pascalTriangleVec[binominalIndex(line - 1, number)] + pascalTriangleVec[binominalIndex(line - 1, number - 1)];
- }
- }
- }
- std::chrono::high_resolution_clock::time_point endPoint = std::chrono::high_resolution_clock::now();
- std::chrono::milliseconds time = std::chrono::duration_cast<std::chrono::milliseconds>(endPoint - start);
- qDebug() << "PascalTriangle: " << time.count() << "ms";
- //Calculate Additional Data
- for (SingleRun& srun : singleRunList) {
- srun.calculateAdditionalData(pascalTriangleVec, amountOfBits);
- }
- calculateAverageOverRuns();
- }
- void RunData::metalogFile(bool& retflag)
- {
- retflag = true;
- /* Start extracting */
- while (fileStream.peek() != EOF) {
- std::string buffer;
- getLine(buffer);
- SolutionPointData sol;
- std::regex regexIter("i:([\\+\\-]?\\d+)");
- std::regex regexObjectiveFunction("of:([\\+\\-]?\\d+\\.\\d+(?:E[\\+\\-]\\d+)?)");
- std::smatch match;
- if (!std::regex_search(buffer, match, regexIter)) {
- qDebug() << "Bad formatatted Line[" << actualLine << "].";
- qDebug() << "Failed to matched:";
- qDebug() << QString::fromStdString(buffer);
- return;
- }
- sol.iteration = std::stoi(match[1]);
- if (!std::regex_search(buffer, match, regexObjectiveFunction)) {
- qDebug() << "Bad formatatted Line[" << actualLine << "].";
- qDebug() << "Failed to matched:";
- qDebug() << QString::fromStdString(buffer);
- return;
- }
- sol.objectiveFunction = std::stod(match[1]);
- std::regex regexParticleNumber("pN:([\\+\\-]?\\d+)");
- if (!std::regex_search(buffer, match, regexParticleNumber)) {
- qDebug() << "Bad formatatted Line[" << actualLine << "].";
- qDebug() << "Failed to matched:";
- qDebug() << QString::fromStdString(buffer);
- return;
- }
- sol.particleNumber = std::stoi(match[1]);
- std::regex regexBitVec("b:([01]+)");
- if (!std::regex_search(buffer, match, regexBitVec)) {
- qDebug() << "Bad formatatted Line[" << actualLine << "].";
- qDebug() << "Failed to matched:";
- qDebug() << QString::fromStdString(buffer);
- return;
- }
- sol.bitVec.resize(match[1].length());
- int count = 0;
- std::string str = match[1];
- for (std::string::size_type i = 0; i < str.size(); ++i) {
- sol.bitVec[i] = (str[i] == '1');
- }
- solutionVec.push_back(sol);
- }
- retflag = false;
- }
- void RunData::getLine(std::string& bufferString)
- {
- std::getline(fileStream, bufferString);
- actualLine++;
- }
- void RunData::calculateAverageOverRuns()
- {
- qDebug() << "calculateAverageOverRuns";
- {
- std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();
- int iter = singleRunList.begin()->bestMaxSolutionFoundPerIteration.size();
- double n = singleRunList.size();
- bestAverageMaxSolutionFoundPerIteration.resize(iter);
- for (int i = 0; i < iter; i++) {
- double average = std::accumulate(singleRunList.begin(), singleRunList.end(), 0.0, [i](double a, const SingleRun& b) -> double
- {return a + b.bestMaxSolutionFoundPerIteration[i].y; }) / n;
- bestAverageMaxSolutionFoundPerIteration[i] = GraphDataPoint((double)i, average);
- }
- std::chrono::high_resolution_clock::time_point endPoint = std::chrono::high_resolution_clock::now();
- std::chrono::milliseconds time = std::chrono::duration_cast<std::chrono::milliseconds>(endPoint - start);
- qDebug() << "Time" << time.count() << "ms";
- }
- }
- SingleRun::SingleRun(std::string uniqueName, const std::vector<SolutionPointData>::iterator begin, const std::vector<SolutionPointData>::iterator end, std::string name = "")
- :begin(begin), end(end), name(name), runDataName(uniqueName)
- {
- }
- void SingleRun::calculateAdditionalData(std::vector<boost::multiprecision::cpp_int>& pascalTriangleVec, int amountOfBits)
- {
- calculateBestAndAverageIter();
- calculateParticleSolution();
- calculateDotsForDistribution();
- calculateBitFieldData(pascalTriangleVec, amountOfBits);
- calculateMeanHammingDistance();
- }
- void SingleRun::calculateBestAndAverageIter()
- {
- if (begin == end) {
- return;
- }
- double minObjectiveFunctionInIter = begin->objectiveFunction;
- double maxObjectiveFunctionInIter = begin->objectiveFunction;
- double bestMinObjectiveFunctionFound = begin->objectiveFunction;
- double bestMaxObjectiveFunctionFound = begin->objectiveFunction;
- double actualIterObjectiveFunctionAggregate = begin->objectiveFunction;
- int actualIter = begin->iteration;
- int foundSolutionInIteration = 1;
- for (auto iter = begin; iter != end; iter++) {
- SolutionPointData& nextData = *iter;
- if (nextData.iteration != actualIter) {
- //save last
- bestMinSolutionFoundPerIteration.push_back(GraphDataPoint((double)actualIter, bestMinObjectiveFunctionFound));
- bestMaxSolutionFoundPerIteration.push_back(GraphDataPoint((double)actualIter, bestMaxObjectiveFunctionFound));
- averageSolutionPerItertion.push_back(GraphDataPoint((double)actualIter, actualIterObjectiveFunctionAggregate / (double)foundSolutionInIteration));
- minSolutionPerItertion.push_back(GraphDataPoint((double)actualIter, minObjectiveFunctionInIter));
- maxSolutionPerItertion.push_back(GraphDataPoint((double)actualIter, maxObjectiveFunctionInIter));
- //init new iteration
- actualIter = nextData.iteration;
- foundSolutionInIteration = 1;
- actualIterObjectiveFunctionAggregate = nextData.objectiveFunction;
- minObjectiveFunctionInIter = nextData.objectiveFunction;
- maxObjectiveFunctionInIter = nextData.objectiveFunction;
- }
- else {
- //increae aggregate
- foundSolutionInIteration++;
- actualIterObjectiveFunctionAggregate += nextData.objectiveFunction;
- }
- //update best min and max if better
- if (nextData.objectiveFunction < bestMinObjectiveFunctionFound) {
- bestMinObjectiveFunctionFound = nextData.objectiveFunction;
- }
- if (nextData.objectiveFunction > bestMaxObjectiveFunctionFound) {
- bestMaxObjectiveFunctionFound = nextData.objectiveFunction;
- }
- if (nextData.objectiveFunction < minObjectiveFunctionInIter) {
- minObjectiveFunctionInIter = nextData.objectiveFunction;
- }
- if (nextData.objectiveFunction > maxObjectiveFunctionInIter) {
- maxObjectiveFunctionInIter = nextData.objectiveFunction;
- }
- }
- //save last iteration
- bestMinSolutionFoundPerIteration.push_back(GraphDataPoint((double)actualIter, bestMinObjectiveFunctionFound));
- bestMaxSolutionFoundPerIteration.push_back(GraphDataPoint((double)actualIter, bestMaxObjectiveFunctionFound));
- averageSolutionPerItertion.push_back(GraphDataPoint((double)actualIter, actualIterObjectiveFunctionAggregate / (double)foundSolutionInIteration));
- minSolutionPerItertion.push_back(GraphDataPoint((double)actualIter, minObjectiveFunctionInIter));
- maxSolutionPerItertion.push_back(GraphDataPoint((double)actualIter, maxObjectiveFunctionInIter));
- }
- void SingleRun::calculateParticleSolution()
- {
- for (auto iter = begin; iter != end; iter++) {
- GraphDataPoint point(iter->iteration, iter->objectiveFunction, &*iter);
- auto treeIter = particleMap.find(iter->particleNumber);
- if (treeIter == particleMap.end()) {
- //create new Entry
- std::vector<GraphDataPoint> vec;
- vec.push_back(point);
- particleMap.insert({ iter->particleNumber, vec});
- }
- else {
- //append to vector in Entry
- treeIter->second.push_back(point);
- }
- }
- }
- void SingleRun::calculateDotsForDistribution()
- {
- for (std::vector<SolutionPointData>::iterator it = begin; it != end; ++it) {
- dotsForDistribution.push_back(GraphDataPoint((double)it->iteration, it->objectiveFunction, &*it));
- }
- }
- boost::multiprecision::cpp_int positionInPermutation2(std::vector<boost::multiprecision::cpp_int>& pascalTriangleVec, std::vector<bool>::iterator begin, std::vector<bool>::iterator end, int amountOfUnsetBits)
- {
- //recursion base
- if (amountOfUnsetBits == 0) return 1;
- int amountOfBits = end - begin;
- std::vector<bool>::iterator indexIter = std::find(begin, end, false);
- int index = indexIter - begin;
- int amountOfBitsAfterIndex = (amountOfBits - 1) - index;
- //recursion base
- if (amountOfUnsetBits == 1) return (amountOfBits - 1) - index;
- //Step 1 the amount of permutations with the rest amountOfBitsAfterIndex
- boost::multiprecision::cpp_int before = (amountOfUnsetBits <= amountOfBitsAfterIndex) ? pascalTriangleVec[RunData::binominalIndex(amountOfBitsAfterIndex, amountOfUnsetBits)] : 0;
- //Step 2 the actual position of the rest
- boost::multiprecision::cpp_int after = positionInPermutation2(pascalTriangleVec, ++indexIter, end, amountOfUnsetBits - 1);
- //Step 3 add Step 1 and Step 2
- return before + after;
- }
- void SingleRun::calculateBitFieldData(std::vector<boost::multiprecision::cpp_int>& pascalTriangleVec, int amountOfBits)
- {
-
- std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();
- for (std::vector<SolutionPointData>::iterator it = begin; it != end; ++it) {
- int amountOfSetBits = std::count(it->bitVec.begin(), it->bitVec.end(), true);
- int amountOfUnsetBits = it->bitVec.size() - amountOfSetBits;
- boost::multiprecision::cpp_dec_float_100 position(positionInPermutation2(pascalTriangleVec, it->bitVec.begin(), it->bitVec.end(), amountOfUnsetBits));
- boost::multiprecision::cpp_dec_float_100 maxAmountOfPermutaions (pascalTriangleVec[RunData::binominalIndex(amountOfBits, amountOfSetBits)] - 1);
- dotsForBitField.push_back(GraphDataPoint((position / maxAmountOfPermutaions).convert_to<double>(), amountOfSetBits, &*it));
- }
- std::chrono::high_resolution_clock::time_point endPoint = std::chrono::high_resolution_clock::now();
- std::chrono::milliseconds time = std::chrono::duration_cast<std::chrono::milliseconds>(endPoint - start);
- qDebug() << "BitFieldBerechnung: " << time.count() << "ms";
- }
- void SingleRun::calculateMeanHammingDistance()
- {
- std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();
- std::vector<SolutionPointData>::iterator iterBegin = begin;
- for (std::vector<SolutionPointData>::iterator iter = begin; iter != end; iter++) {
- if (iter->iteration != iterBegin->iteration) {
- double mean = RunData::meanHammingDistance(iterBegin, iter);
- meanHammingDistancePerIteration.push_back(GraphDataPoint(iterBegin->iteration, mean));
- iterBegin = iter;
- }
- }
- std::chrono::high_resolution_clock::time_point endPoint = std::chrono::high_resolution_clock::now();
- std::chrono::milliseconds time = std::chrono::duration_cast<std::chrono::milliseconds>(endPoint - start);
- qDebug() << "Mean: " << time.count() << "ms";
- }
- int RunData::binominalIndex(const int n, int k)
- {
- if (k > n / 2) k = n - k;
- return ((n + 1) / 2) * (n / 2 + 1) + k;
- }
- int RunData::hammingdistance(std::vector<bool>& bitVecA, std::vector<bool>& bitVecB)
- {
- //assert((bitVecA.size() == bitVecB.size()));
- int count = 0;
- auto iterB = bitVecB.begin();
- for (auto iterA = bitVecA.begin(); iterA != bitVecA.end(); iterA++) {
- if (*iterA != *iterB) {
- count++;
- }
- iterB++;
- }
- return count;
- }
- double RunData::meanHammingDistance(std::vector<SolutionPointData>::iterator begin, std::vector<SolutionPointData>::iterator end)
- {
- if (std::distance(begin, end) <= 1) {
- return 0.0;
- }
- std::vector<SolutionPointData>::iterator startParticle(begin);
- double hammingValuesAccumulated = 0.0;
- int count = 0;
- for (std::vector<SolutionPointData>::iterator iter = begin; iter != end; iter++) {
- for (std::vector<SolutionPointData>::iterator iterParticle = iter + 1; iterParticle != end; iterParticle++) {
- hammingValuesAccumulated += hammingdistance(iter->bitVec, iterParticle->bitVec);
- count++;
- }
- }
- return hammingValuesAccumulated / (double) count;
- }
- boost::multiprecision::cpp_int RunData::binominal(const int n,int k)
- {
- boost::multiprecision::cpp_int value(1);
- if (k > n / 2) k = n - k;
- for (int i = 0; i < k; i++) {
- value *= boost::multiprecision::cpp_int(n - i);
- value /= boost::multiprecision::cpp_int(i + 1);
- }
- return value;
- }
- boost::multiprecision::cpp_int RunData::positionInPermutation(std::vector<bool>::iterator begin, std::vector<bool>::iterator end, int setBits)
- {
- int amountOfBits = end - begin;
- //recursion base
- if (setBits == 0) return 1;
- std::vector<bool>::iterator indexIter = std::find(begin, end, true);//TODO:false könnte andersrum sortieren!
- int index = indexIter - begin;
- int bitsAfterIndex = (amountOfBits - 1) - index;
- //recursion base
- if (setBits == 1) return (amountOfBits - 1) - index;
- //Step 1 the amount of permutations with the rest amountOfBitsAfterIndex
- boost::multiprecision::cpp_int before = binominal(bitsAfterIndex, setBits);
- //Step 2 teh actual position of the rest
- boost::multiprecision::cpp_int after = positionInPermutation(++indexIter, end, setBits - 1);
- //setp 3 add Step 1 and Step 2
- return before + after;
- }
- boost::multiprecision::cpp_int RunData::positionInPermutation_reversed(std::vector<bool>::iterator begin, std::vector<bool>::iterator end, int amountOfUnsetBits)
- {
- qDebug() << "Method()";
- int amountOfBits = end - begin;
- //recursion base
- if (amountOfUnsetBits == 0) return 1;
- std::vector<bool>::iterator indexIter = std::find(begin, end, false);
- int index = indexIter - begin;
- qDebug() << "index: " << index;
- int bitsAfterIndex = (amountOfBits - 1) - index;
- //recursion base
- if (amountOfUnsetBits == 1) return (amountOfBits - 1) - index;
- //Step 1 the amount of permutations with the rest amountOfBitsAfterIndex
- boost::multiprecision::cpp_int before = (amountOfUnsetBits <= bitsAfterIndex)? binominal(bitsAfterIndex, amountOfUnsetBits):0;
- qDebug() << "before: " << "binominal("<< bitsAfterIndex << "," << amountOfUnsetBits << ")" << before.convert_to<int>();
- //Step 2 teh actual position of the rest
- boost::multiprecision::cpp_int after = positionInPermutation_reversed(++indexIter, end, amountOfUnsetBits - 1);
- qDebug() << "after: " << after.convert_to<int>();
- qDebug() << "return:" << before.convert_to<int>() << "+" << after.convert_to<int>();
- //setp 3 add Step 1 and Step 2
- return before + after;
- }
- GraphDataPoint::GraphDataPoint(double x, double y, SolutionPointData* orginalPoint) : x(x), y(y), orginalPoint(orginalPoint)
- {
- }
- GraphDataPoint::GraphDataPoint(double x, double y, QColor color, SolutionPointData* orginalPoint)
- : x(x), y(y), orginalPoint(orginalPoint), color(color)
- {
- }
- bool GraphDataPoint::existLink() const
- {
- return orginalPoint != nullptr;
- }
- QPointF GraphDataPoint::toQPointF() const
- {
- return QPointF(x, y);
- }
- double GraphDataPoint::squaredDistance(QPointF& graphPoint) const
- {
- return std::pow(graphPoint.x() - x, 2) + std::pow(graphPoint.y() - y, 2);
- }
- std::string SolutionPointData::bitstringToStdString()
- {
- std::string str(bitVec.size(), 0);
- std::transform(bitVec.begin(), bitVec.end(), str.begin(),
- [](bool b) -> char { return b ? '1' : '0'; });
- return str;
- }
|