Bucket Graph Creation, C++ (gcc)

Bucket Graph Creation

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <iterator>
#include <chrono>
#include <map>
#include<iomanip>

using namespace std;
using namespace std::chrono;

auto start = high_resolution_clock::now();
int vertexNum = 1; 		//number of vertices

//found online
struct VectorHasher {
    int operator()(const vector<int> &V) const {
        int hash=0;
        for(int i=0;i<V.size();i++) {
            hash+=V[i] + vertexNum; // Can be anything
        }
        return hash;
    }
};

//initializing my functions
void edgeLord();
int bfSearch();

//Input Variables
int bucketNum = 0;
vector<int> buckets;	//passed in buckets

int fillcount = 0;
int emptycount = 0;
int pourcount = 0;
//global variables
int edgeCount = 0;		//number of edges
int GODCOUNT = 0; 		//assists in counting index of Adjaceny List for map
int sumCount = 0;		//counts the sum to place at each vertex
int counter = 0;  		//other counter used for vertx creation
int answerSize = 0;
int answerMoves = 0;

vector<int> temptemp;	//unfortunate requirement
vector<int> temp;		//vector that is constantly replaced
vector<vector<int>> temp2;			//vector<vector> that is constantly replaced
vector<vector<vector<int>>> List; 	//Adjaceny List containing everything

map<vector<int>,int> GOD;
map<int,int> miniGOD;

queue <vector<int>> q;

int main() {
	auto start = high_resolution_clock::now();

buckets.push_back(999);
    buckets.push_back(998);
    bucketNum = 2;
	
	
    
	
	//quick math to calculate the number of vertices
    for(int i = 0; i < bucketNum; i++){
	 vertexNum = vertexNum * (buckets[i] + 1);
	 temp.push_back(0);
	}
	
	temp.push_back(0); 	//secret value for Visisted
    temp.push_back(0);	//secret value for Level
    temp.push_back(0);	//secret value for Sum
	
	temp2.push_back(temp);
	
//	cout << "Vertices are currently being created" << endl;
	
    int j = 0;
	auto potato = high_resolution_clock::now();
	while(j < vertexNum){
	    sumCount = 0;
		
	    for(int i = 0; i < bucketNum; i++){
        sumCount += temp[i];
		}	
		
		temp.at(bucketNum + 2) = sumCount;
		temp2.at(0) = temp;
		List.push_back(temp2);
		
        temptemp = temp;
        temptemp.pop_back();
		temptemp.pop_back();
		temptemp.pop_back();
        GOD[temptemp] = GODCOUNT;
	    GODCOUNT++;
		
		
		
	    temp[counter]++;
	    while(temp[counter] > buckets[counter]){
	        temp[counter] = 0;
	        counter++;
	        if (counter > bucketNum){    
	            break;
	        }
	        temp[counter]++;
	    }
	    counter = 0;
	    j++;
	}
	auto potatostop = high_resolution_clock::now();
	auto potatoduration = duration_cast<microseconds>(potatostop - potato);
	cout << "Vertex Creation Complete: " << List.size() << " " << setw(30) << right << potatoduration.count() << " miliseconds" << endl;
	
//	cout << List.size() << " Vertices have been created" << endl;
//   cout << "Edges are currently being created" << endl;
    edgeLord();	
//   cout << edgeCount << " Edges have been created" << endl;
//	cout << "BFS is currently being calculated" << endl;
	bfSearch();
	
	auto stop = high_resolution_clock::now();
	auto duration = duration_cast<microseconds>(stop - start);
	cout << "Main Program Complete: " << setw(30) << right << duration.count() << " miliseconds" << endl;

cout << fillcount << " " << emptycount << " " << pourcount <<  " = " << edgeCount << endl;
	return 0;
}

//THIS STARTS THE EDGE CREATION PROCESS
void edgeLord(){
	auto start = high_resolution_clock::now(); 
    for(int i = 0; i < List.size(); i++){		
        for(int k = 0; k < bucketNum; k++){
            temp = List.at(i).at(0);
            temp.pop_back();
			temp.pop_back();
			temp.pop_back();
            if(temp.at(k) < buckets.at(k) ){
                temp.at(k) = buckets.at(k);
				List.at(i).push_back(temp);
                temp = List.at(i).at(0);
                temp.pop_back();
				temp.pop_back();
				temp.pop_back();
                edgeCount++;
				fillcount++;
            }
            if(temp.at(k) > 0){
                temp.at(k) = 0;
                List.at(i).push_back(temp);
                temp = List.at(i).at(0);
                temp.pop_back();
				temp.pop_back();
				temp.pop_back();
                edgeCount++;
				emptycount++;
            }
        }
		for(int p = 0; p < bucketNum; p++){
			for(int q = 0; q < bucketNum; q++){
				if(List.at(i).at(0).at(p) > 0 && List.at(i).at(0).at(q) < buckets.at(q) && p != q){
					int canFit = (buckets.at(q) - temp.at(q));
					if(canFit > 0){
						int canPour = temp.at(p);
						if(canFit == canPour){
							temp.at(p) = 0;
							temp.at(q) = buckets.at(q);
							List.at(i).push_back(temp);
							temp = List.at(i).at(0);
							temp.pop_back();
							temp.pop_back();
							temp.pop_back();
							edgeCount++;
							pourcount++;
						}
						else if(canFit > canPour){
							temp.at(p) = 0;
							temp.at(q) = temp.at(q) + canPour;
							List.at(i).push_back(temp);
							temp = List.at(i).at(0);
							temp.pop_back();
							temp.pop_back();
							temp.pop_back();
							edgeCount++;
							pourcount++;
						}
						else{
							temp.at(q) = buckets.at(q);
							temp.at(p) = canPour - canFit;
							List.at(i).push_back(temp);
							temp = List.at(i).at(0);
							temp.pop_back();
							temp.pop_back();
							temp.pop_back();
							edgeCount++;
							pourcount++;
						}
					}
				}
			}
		}
    }
	auto stop = high_resolution_clock::now();
	auto duration = duration_cast<microseconds>(stop - start);
	cout << "Edge Creation Complete: " << edgeCount << " " << setw(30) << right << duration.count() << " miliseconds" << endl; 
	}

int bfSearch(){
	auto start = high_resolution_clock::now(); 
    List.at(0).at(0).at(bucketNum) = 1;
    q.push(List.at(0).at(0));
    
    while(!q.empty()){
        temp = q.front();
        temptemp = temp;
        temptemp.pop_back();
		temptemp.pop_back();
		temptemp.pop_back();
		
        int index = GOD[temptemp];
        int sum = temp.at(bucketNum+2);
        int level = temp.at(bucketNum+1);
       
		if(miniGOD.find(sum) == miniGOD.end()){
			miniGOD.insert(pair<int, int>(sum, level));
		}

q.pop();

for(int i = 1; i < List.at(index).size(); i++){
            int index2 = GOD[List.at(index).at(i)];
			if(List.at(index2).at(0).at(bucketNum) == 0){
                List.at(index2).at(0).at(bucketNum) = 1;
                List.at(index2).at(0).at(bucketNum + 1) = level + 1;
                q.push(List.at(index2).at(0));                
            }
        }
    }
    
//    std::cout << "mymap contains: ";
    for ( auto it = miniGOD.begin(); it != miniGOD.end(); ++it )
		if(it->second > answerMoves){
			if(it->second == answerMoves){
				if(it->first > answerSize){
					answerSize = it->first;
					answerMoves = it->second;
				}
			}
			else{
				answerSize = it->first;
				answerMoves = it->second;
			}
		}
//		cout << answerSize << ", " << answerMoves << endl;
    auto stop = high_resolution_clock::now();
	auto duration = duration_cast<microseconds>(stop - start);
	cout << "BFS Complete: (" << answerSize << ", " << answerMoves << ") " << setw(30) << right << duration.count() << " miliseconds" << endl;
	return 0;
}


run \| edit \| history \| help	0