/*
#include <opencv2/core/core.hpp>
#include <opencv2/imgproc/imgproc.hpp>
#include <opencv2/highgui/highgui.hpp>
using namespace cv;

int main(int argc, char *argv[])
{
Mat img = imread("C++/Test/images/cameraman.jpg", CV_LOAD_IMAGE_COLOR);
if(img.empty())
return -1;
namedWindow( "lena", CV_WINDOW_AUTOSIZE );
imshow("lena", img);
waitKey(0);
return 0;
}*/

#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <regex>
#include <utility>
#include <algorithm>
#include <time.h>

#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>

#include <boost/ref.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/planar_canonical_ordering.hpp>
#include <boost/graph/boyer_myrvold_planar_test.hpp>
#include <tuple>

#define w 600

using namespace std;
using namespace boost;
using namespace cv;

regex reg1("\\(([UD][LR]){2}\\)");
regex reg2("\\(([UD][LR]){4}\\)");

//Initial Processes relating to Gauss Code
//--------------------------------------------------------------------------------------------------------------------------------------------------------

void removeDouble(pair<vector<int>, vector<int> > &gaussCode){

	int loopBreak = 1;
	bool flag = true;
	while (flag) {
		loopBreak++;
		if (loopBreak > 1000) {
			std::cout << "A loop appears to not be ending, perhaps the code was too long?" << endl;
			exit(EXIT_FAILURE);
		}
		if (gaussCode.first.size() == 0) {
			std::cout << "The Gauss Code immediately reduced to the unknot" << endl;
			exit(EXIT_FAILURE);
		}
		vector <int> temp = gaussCode.first;
		for (int index = temp.size() - 2; index > 0; index--){
			if (temp[index] + temp[index - 1] == 0){
				temp.erase(temp.begin() + index - 1);
				temp.erase(temp.begin() + index - 1);

			}
		}
		if (gaussCode.first[0] == -gaussCode.first[gaussCode.first.size() - 1]){
			temp.pop_back();
			temp.erase(temp.begin());
		}
		if (temp[temp.size() - 1] == -temp[temp.size() - 2]){
			temp.pop_back();
			temp.pop_back();

		}
		if (temp.size() == gaussCode.first.size()){
			flag = false;
		}
		gaussCode.first = temp;
	}

	return;
}
//Removes instances of a repeated vertex in the Gauss Code. That is, un-twist as in the first Reidemeister move

pair<vector<int>, vector<int> > GaussCheck(string GaussCode){
	std::stringstream stream(GaussCode);
	int Total = 0;
	vector<int> GaussVector;
	vector<int> Signs;
	while (1) {
		string mystring;
		stream >> mystring;
		if (!stream)
			break;
		//GaussVector.push_back(int(n));
		if (mystring.size() > 0) {
			if (mystring[0] == '+'){
				mystring.erase(0, 1);
				Signs.push_back(1);
			}
			else if (mystring[0] == '-'){
				mystring.erase(0, 1);
				Signs.push_back(-1);
			}
			else {
				Signs.push_back(0);
			}

			GaussVector.push_back(stoi(mystring, nullptr, 10));
		}
	}
	return make_pair(GaussVector, Signs);
}
//Augments the Gauss Code from a string to a desired form, splitting the crossing numbers from the crossing type for later computations

bool CheckNext(std::tuple<int, int, int, int, int> CurrentEdge, std::tuple<int, int, int, int, int> checkEdge, pair<vector<int>, vector<int> > gaussCode){
	bool answer = false;
	if (get<0>(checkEdge) == get<2>(CurrentEdge)){
		if (get<3>(CurrentEdge) == 0){
			int first = distance(gaussCode.first.begin(), find(gaussCode.first.begin(), gaussCode.first.end(), get<2>(CurrentEdge)));
			int second = distance(gaussCode.first.begin(), find(gaussCode.first.begin() + first + 1, gaussCode.first.end(), get<2>(CurrentEdge)));
			if (second != gaussCode.first.size()){

				int sign = gaussCode.second[first] + gaussCode.second[second];


				if ((get<1>(checkEdge) == sign) && (get<4>(checkEdge) == sign * get<4>(CurrentEdge))){
					answer = true;
				}
			}
			else{
				if (get<4>(checkEdge) == get<4>(CurrentEdge)){
					answer = true;
				}
			}
		}
		else {
			if ((get<1>(checkEdge) == 0) && (get<4>(checkEdge) == -1 * get<3>(CurrentEdge)*get<4>(CurrentEdge))){
				answer = true;
			}
		}
		if (get<2>(checkEdge) == get<0>(CurrentEdge)){
			answer = false;
		}
	}
	return answer;
}
//Given the Gauss Code, and two (directed) edges, determines whether the "checkEdge" follows "CurrentEdge" when using turning left to generate faces

void Embed(pair<vector<int>, vector<int> > gaussCode, pair<vector<int>, vector<int> > crossingType, int vertexNum, pair<vector<int>, vector<int> > &adjList){
	vector<std::tuple<int, int, int, int, int> > Edges;


	for (unsigned int iter = 0; iter < gaussCode.first.size(); iter++){
		if (iter + 1 != gaussCode.first.size()){
			auto newEdge1 = make_tuple(gaussCode.first[iter], gaussCode.second[iter], gaussCode.first[iter + 1], gaussCode.second[iter + 1], 1);
			auto newEdge2 = make_tuple(gaussCode.first[iter + 1], gaussCode.second[iter + 1], gaussCode.first[iter], gaussCode.second[iter], -1);
			Edges.push_back(newEdge1);
			Edges.push_back(newEdge2);
		}
		else {
			auto newEdge1 = make_tuple(gaussCode.first[iter], gaussCode.second[iter], gaussCode.first[0], gaussCode.second[0], 1);
			auto newEdge2 = make_tuple(gaussCode.first[0], gaussCode.second[0], gaussCode.first[iter], gaussCode.second[iter], -1);
			Edges.push_back(newEdge1);
			Edges.push_back(newEdge2);
		}
	}

	cout << endl << endl << "Edges:" << endl;
	for (auto iter = Edges.begin(); iter != Edges.end(); iter++){
		auto printedge = *iter;
		cout << get<0>(printedge) << "  " << get<1>(printedge) << "  " << get<2>(printedge) << "  " << get<3>(printedge) << "  " << get<4>(printedge) << endl;

	}

	vector<vector<int> > Faces;
	bool flag = true;
	int E = Edges.size() / 2;
	while (flag){
		vector<int> CurrentFace;

		auto StartEdge = Edges[0];
		auto CurrentEdge = StartEdge;
		CurrentFace.push_back(get<0>(StartEdge));
		Edges.erase(Edges.begin());
		bool flaginner = true;
		int counterinner = 0;
		while (flaginner){

			for (auto iter = Edges.begin(); iter != Edges.end(); iter++){
				auto checkEdge = *iter;

				if (CheckNext(CurrentEdge, checkEdge, gaussCode)){
					CurrentEdge = checkEdge;
					Edges.erase(iter);
					CurrentFace.push_back(get<0>(CurrentEdge));
					break;
				}

			}
			auto printedge = CurrentEdge;
			//cout << endl << get<0>(printedge) << "  " << get<1>(printedge) << "  " << get<2>(printedge) << "  " << get<3>(printedge) << "  " << get<4>(printedge) << endl;
			if (CheckNext(CurrentEdge, StartEdge, gaussCode)){
				flaginner = false;
			}
		}
		Faces.push_back(CurrentFace);
		flag = (Edges.size() != 0);
	}
	cout << "The Faces of the associated surface are:" << endl;
	for (auto it = Faces.begin(); it != Faces.end(); it++){
		auto CurrentFace = *it;
		std::cout << "Face :  ";
		for (auto it2 = CurrentFace.begin(); it2 != CurrentFace.end(); it2++){
			std::cout << *it2 << "  ";
		}
		std::cout << endl << endl;
	}

	//Check the Euler Characteristic to verify the Gauss Code is planar
	int F = Faces.size();
	int V = vertexNum;
	int Chi = V - E + F;
	if (Chi != 2){
		cout << "The Euler Characteristic was computed to be: " << Chi << " =/=  2" << endl << "Hence the Gauss Code does not describe a planar knot, please check";
		cout << endl << "V = " << V << endl << "E = " << E << endl << "F = " << F << endl;
		exit(EXIT_FAILURE);
	}



	vector<vector<int> > TriangulationFaces;
	for (vector<vector<int> >::iterator iter = Faces.begin(); iter != Faces.end(); iter++){
		vector<int> BigFace = *iter;
		while (BigFace.size() != 3){
			int v1 = BigFace[0];
			int v3 = BigFace[2];
			bool check = false;
			for (unsigned int iter = 0; iter < adjList.first.size(); iter++){
				if ((adjList.first[iter] == v1) && (adjList.second[iter] == v3)){
					check = true;
				}
				if ((adjList.first[iter] == v3) && (adjList.second[iter] == v1)){
					check = true;
				}
			}


			if (check){
				for (unsigned int innerit = 3; innerit < BigFace.size(); innerit++){
					adjList.first.push_back(BigFace[1]);
					adjList.second.push_back(BigFace[innerit]);
					//vector<int> NewFace{ BigFace[1], BigFace[innerit - 1], BigFace[innerit] };
					vector<int> NewFace;
					NewFace.push_back(BigFace[1]);
					NewFace.push_back(BigFace[innerit - 1]);
					NewFace.push_back(BigFace[innerit]);
					TriangulationFaces.push_back(NewFace);
				}
				std::array<int, 3> iBigFace = { BigFace[0], BigFace[1], BigFace[BigFace.size() - 1] };
				BigFace = vector<int>(iBigFace.begin(), iBigFace.end());
			}
			else {
				adjList.first.push_back(BigFace[0]);
				adjList.second.push_back(BigFace[2]);
				array<int, 3> iNewFace = { BigFace[0], BigFace[1], BigFace[2] };
				vector<int> NewFace(iNewFace.begin(), iNewFace.end());
				TriangulationFaces.push_back(NewFace);
				BigFace.erase(BigFace.begin() + 1);
			}
		}

		TriangulationFaces.push_back(BigFace);
	}

	std::cout << "The triangulation is given by:  " << endl << endl;
	for (auto it = TriangulationFaces.begin(); it != TriangulationFaces.end(); it++){
		auto CurrentFace = *it;
		std::cout << "Face :  ";
		for (auto it2 = CurrentFace.begin(); it2 != CurrentFace.end(); it2++){
			std::cout << *it2 << "  ";
		}
		std::cout << endl << endl;
	}

	//std::cout << endl << endl;
	//std::cout << "Triangulation Adj List:" << endl << endl;

	//for (vector<int>::iterator it = adjList.first.begin(); it != adjList.first.end(); it++) {
	//std::cout << *it << "  ";
	//}
	//std::cout << endl << endl;
	//for (vector<int>::iterator it = adjList.second.begin(); it != adjList.second.end(); it++) {
	//std::cout << *it << "  ";
	//}
	//std::cout << endl << endl;

}
/*
Takes a Gauss Code, (and the auxilliary data deduced from it) and computes an embedding in the form of an adjacency list of a triangulation of that embedding, as follows:
1: Generate a list of signed edges, with each graph edge appearing once forwards and once backwards
2: Generate a list of faces using the "turn left" rule.
ie Pick an edge and follow it anti-clockwise until you return to your start point, at which point, store the list of vertices as a face, and remove all edges used
3: Triangulate each face by adding extra edges (ensuring we don't add an edge already in our graph
4: Output the adjacency list of the triangulation
*/

void extractGraph(pair<vector<int>, vector<int> > &gaussCode, pair<vector<int>, vector<int> > &adjList, pair<vector<int>, vector<int> > &CrossingType, int &vertNum) {
	int orig = vertNum;
	bool flag = true;
	while (flag){
		int size = gaussCode.first.size();
		for (int index = 0; index < size - 1; index++) {
			int FirstVertex = gaussCode.first[index];
			int SecondVertex = gaussCode.first[index + 1];

			int count = 0;
			for (unsigned int innerindex = 0; innerindex < gaussCode.first.size() - 1; innerindex++){
				if ((gaussCode.first[innerindex] == FirstVertex) && (gaussCode.first[innerindex + 1] == SecondVertex)){
					count++;
				}
			}
			if ((FirstVertex == gaussCode.first[gaussCode.first.size() - 1]) && (SecondVertex == gaussCode.first[0])){
				count++;
			}
			for (unsigned int innerindex = 0; innerindex < gaussCode.first.size() - 1; innerindex++){
				if ((gaussCode.first[innerindex] == SecondVertex) && (gaussCode.first[innerindex + 1] == FirstVertex)){
					count++;
				}
			}
			if ((FirstVertex == gaussCode.first[gaussCode.first.size() - 1]) && (SecondVertex == gaussCode.first[0])){
				count++;
			}
			if ((SecondVertex == gaussCode.first[gaussCode.first.size() - 1]) && (FirstVertex == gaussCode.first[0])){
				count++;
			}
			if (count >1){
				gaussCode.first.insert(gaussCode.first.begin() + index + 1, vertNum + 1);
				gaussCode.second.insert(gaussCode.second.begin() + index + 1, 0);
				vertNum++;
				index = size;
			}
		}
		if (size == gaussCode.first.size()){
			flag = false;
		}
	}

	adjList.first = gaussCode.first;
	adjList.second = gaussCode.first;
	adjList.second.push_back(adjList.second[0]);
	adjList.second.erase(adjList.second.begin(), adjList.second.begin() + 1);

	for (int iterator = 1; iterator <= orig; iterator++){
		int first = distance(gaussCode.first.begin(), find(gaussCode.first.begin(), gaussCode.first.end(), iterator));
		int second = distance(gaussCode.first.begin(), find(gaussCode.first.begin() + first + 1, gaussCode.first.end(), iterator));
		if (gaussCode.second[first] != 0) {

			if (first == 0){
				CrossingType.first.push_back(gaussCode.first[gaussCode.first.size() - 1]);
			}
			else {
				CrossingType.first.push_back(gaussCode.first[first - 1]);
			}
			if (first == gaussCode.first.size() - 1) {
				CrossingType.second.push_back(gaussCode.first[0]);
			}
			else {
				CrossingType.second.push_back(gaussCode.first[first + 1]);
			}



		}
		else {
			if (second == 0){
				CrossingType.first.push_back(gaussCode.first[gaussCode.first.size() - 1]);
			}
			else {
				CrossingType.first.push_back(gaussCode.first[second - 1]);
			}

			if (second == gaussCode.first.size() - 1) {
				CrossingType.second.push_back(gaussCode.first[0]);
			}
			else {
				CrossingType.second.push_back(gaussCode.first[second + 1]);
			}
		}
	}


	return;
}
//Computes additional data from the augmented Gauss code. In particular, the adjacency matrix of the induced graph (possibly with vertices added) and a list of crossing types


void extractGraphLinks(string gaussCode, pair<vector<int>, vector<int>> &adjList, pair<vector<int>, vector<int>> &crossingType, vector<int> &crossingSign, int &vertNum){
	int linkNum = 1;
	for (unsigned int index = 0; index < gaussCode.length(); index++){
		if (gaussCode[index] == ':'){
			linkNum++;
		}
	}
	string TempGaussCode = gaussCode;

	cout << "There are " << linkNum << " Links" << endl;


	vertNum = 1;
	string vertCountString = gaussCode;
	stringstream stream(vertCountString);
	while (1) {
		string mystring;
		stream >> mystring;
		if (!stream){
			break;
		}
		if (mystring.size() > 0){
			vertNum++;
		}
	}
	vertNum = (vertNum - linkNum) / 2;

	cout << "There are " << vertNum << " vertices" << endl << endl;

	vector<int> Empty;
	adjList = make_pair(Empty, Empty);
	vector<int> Temp(vertNum);
	crossingSign = Temp;
	crossingType = make_pair(crossingSign, crossingSign);

	while (linkNum > 1){
		linkNum--;
		int LinkEnd = TempGaussCode.find(":");
		string tempString = TempGaussCode.substr(0, LinkEnd);
		TempGaussCode.erase(0, LinkEnd + 1);
		std::stringstream stream(tempString);
		int Total = 0;
		vector<int> GaussVector;
		vector<int> Under;
		while (1) {
			string mystring;
			stream >> mystring;
			if (!stream)
				break;
			//GaussVector.push_back(int(n));
			if (mystring.size() > 0) {
				if (mystring[0] == '+'){
					mystring.erase(0, 1);
					int vertex = stoi(mystring, nullptr, 10);
					crossingSign[stoi(mystring) - 1] = 1;
					Under.push_back(1);
				}
				else if (mystring[0] == '-'){
					mystring.erase(0, 1);
					crossingSign[stoi(mystring) - 1] = -1;
					Under.push_back(1);
				}
				else {
					Under.push_back(0);
				}
				GaussVector.push_back(stoi(mystring, nullptr, 10));
			}
		}

		adjList.first.push_back(GaussVector[GaussVector.size() - 1]);
		adjList.second.push_back(GaussVector[0]);
		if (Under[0] == 1){
			crossingType.first[GaussVector[0] - 1] = GaussVector[1];
			crossingType.second[GaussVector[0] - 1] = GaussVector[GaussVector.size() - 1];
		}


		for (unsigned int index = 1; index < GaussVector.size() - 1; index++){
			adjList.second.push_back(GaussVector[index]);
			adjList.first.push_back(GaussVector[index - 1]);
			if (Under[index] == 1){
				crossingType.first[GaussVector[index] - 1] = GaussVector[index - 1];
				crossingType.second[GaussVector[index] - 1] = GaussVector[index + 1];
			}
		}



		adjList.first.push_back(GaussVector[GaussVector.size() - 2]);
		adjList.second.push_back(GaussVector[GaussVector.size() - 1]);
		if (Under[Under.size() - 1] == 1){
			crossingType.first[GaussVector[GaussVector.size() - 1] - 1] = GaussVector[0];
			crossingType.second[GaussVector[GaussVector.size() - 1] - 1] = GaussVector[GaussVector.size() - 2];
		}



	}


	string tempString = TempGaussCode;

	std::stringstream Newstream(tempString);
	int Total = 0;
	vector<int> GaussVector;
	vector<int> Under;
	while (1) {
		string mystring;
		Newstream >> mystring;
		if (!Newstream)
			break;
		//GaussVector.push_back(int(n));
		if (mystring.size() > 0) {
			if (mystring[0] == '+'){
				mystring.erase(0, 1);
				int vertex = stoi(mystring, nullptr, 10);
				crossingSign[stoi(mystring) - 1] = 1;
				Under.push_back(1);
			}
			else if (mystring[0] == '-'){
				mystring.erase(0, 1);
				crossingSign[stoi(mystring) - 1] = -1;
				Under.push_back(1);
			}
			else{
				Under.push_back(0);
			}

			GaussVector.push_back(stoi(mystring, nullptr, 10));
		}
	}

	adjList.first.push_back(GaussVector[GaussVector.size() - 1]);
	adjList.second.push_back(GaussVector[0]);
	if (Under[0] == 1){
		crossingType.first[GaussVector[0] - 1] = GaussVector[1];
		crossingType.second[GaussVector[0] - 1] = GaussVector[GaussVector.size() - 1];
	}


	for (unsigned int index = 1; index < GaussVector.size() - 1; index++){
		adjList.first.push_back(GaussVector[index - 1]);
		adjList.second.push_back(GaussVector[index]);
		if (Under[index] == 1){
			crossingType.first[GaussVector[index] - 1] = GaussVector[index - 1];
			crossingType.second[GaussVector[index] - 1] = GaussVector[index + 1];
		}
	}

	adjList.first.push_back(GaussVector[GaussVector.size() - 2]);
	adjList.second.push_back(GaussVector[GaussVector.size() - 1]);
	if (Under[Under.size() - 1] == 1){
		crossingType.first[GaussVector[GaussVector.size() - 1] - 1] = GaussVector[0];
		crossingType.second[GaussVector[GaussVector.size() - 1] - 1] = GaussVector[GaussVector.size() - 2];
	}
	cout << "AdjList:" << endl;
	for (unsigned int index = 0; index < adjList.first.size(); index++){ cout << adjList.first[index] << "   " << adjList.second[index] << endl; }
	for (unsigned int index = 0; index < adjList.first.size() - 1; index++){
		int vertex1 = adjList.first[index];
		int vertex2 = adjList.second[index];


		for (unsigned int innerIndex = index + 1; innerIndex < adjList.first.size(); innerIndex++){
			if ((vertex1 == adjList.first[innerIndex]) && (vertex2 == adjList.second[innerIndex])){
				if (crossingSign[vertex1 - 1] == crossingSign[vertex2 - 1]){
					vertNum++;
					adjList.first.push_back(vertNum);
					adjList.second.push_back(vertex2);
					adjList.second[innerIndex] = vertNum;
					crossingSign.push_back(0);
					crossingType.first.push_back(0);
					crossingType.second.push_back(0);
					if (crossingType.first[vertex2 - 1] == vertex1){
						crossingType.first[vertex2 - 1] = vertNum;
					}
					else{
						crossingType.second[vertex2 - 1] = vertNum;
					}
				}
				else{
					vertNum++;
					adjList.first.push_back(vertNum);
					adjList.second.push_back(vertex2);
					adjList.second[innerIndex] = vertNum;
					crossingSign.push_back(0);
					crossingType.first.push_back(0);
					crossingType.second.push_back(0);
					if (crossingType.first[vertex1 - 1] == vertex2){
						crossingType.first[vertex1 - 1] = vertNum;
					}
					else{
						crossingType.second[vertex1 - 1] = vertNum;
					}
					if (crossingType.first[vertex1 - 1] == vertex2){
						crossingType.first[vertex1 - 1] = vertNum;
					}
					else{
						crossingType.second[vertex1 - 1] = vertNum;
					}

				}
			}
		}
		for (unsigned int innerIndex = index + 1; innerIndex < adjList.first.size(); innerIndex++){
			if ((vertex2 == adjList.first[innerIndex]) && (vertex1 == adjList.second[innerIndex])){
				if (crossingSign[vertex1 - 1] == crossingSign[vertex2 - 1]){
					vertNum++;
					adjList.first.push_back(vertNum);
					adjList.second.push_back(vertex1);
					adjList.second[innerIndex] = vertNum;
					crossingSign.push_back(0);
					crossingType.first.push_back(0);
					crossingType.second.push_back(0);
					if (crossingSign[vertex1 - 1] == 1){
						if (crossingType.first[vertex1 - 1] == vertex2){
							crossingType.first[vertex1 - 1] = vertNum;
						}
						else{
							crossingType.second[vertex1 - 1] = vertNum;
						}
					}
					else {
						if (crossingType.first[vertex1 - 1] == vertex2){
							crossingType.first[vertex1 - 1] = vertNum;
						}
						else{
							crossingType.second[vertex1 - 1] = vertNum;
						}

					}
				}
				else{
					vertNum++;
					adjList.first.push_back(vertNum);
					adjList.second.push_back(vertex1);
					adjList.second[innerIndex] = vertNum;
					crossingSign.push_back(0);
					crossingType.first.push_back(0);
					crossingType.second.push_back(0);
					if (crossingType.first[vertex1 - 1] == vertex2){
						crossingType.first[vertex1 - 1] = vertNum;
					}
					else{
						crossingType.second[vertex1 - 1] = vertNum;
					}
					if (crossingType.first[vertex2 - 1] == vertex1){
						crossingType.first[vertex2 - 1] = vertNum;
					}
					else{
						crossingType.second[vertex2 - 1] = vertNum;
					}

				}
			}
		}
	}





	cout << "AdjList:" << endl;
	for (unsigned int index = 0; index < adjList.first.size(); index++){ cout << adjList.first[index] << "   " << adjList.second[index] << endl; }
	cout << "CrossingType:  " << endl << endl;
	for (unsigned int index = 0; index < crossingType.first.size(); index++){ cout << crossingType.first[index] << "   " << crossingType.second[index] << endl; }
	cout << "CrossingSign" << endl;
	for (unsigned int index = 0; index < crossingSign.size(); index++) { cout << crossingSign[index] << "   "; }
	cout << endl << endl;


}
bool LinksCheckNext(std::tuple<int, int, int, int, int> CurrentEdge, std::tuple<int, int, int, int, int> checkEdge, pair<vector<int>, vector<int> > crossingType){
	bool answer = false;
	if (get<0>(checkEdge) == get<2>(CurrentEdge)){
		if (crossingType.first[get<0>(checkEdge) -1] == 0){
			if (get<4>(checkEdge) == get<4>(CurrentEdge)){
				answer = true;
			}
		}
		else if (get<3>(CurrentEdge) != get<1>(checkEdge)){
			if (get<1>(checkEdge) == 0){
				int sign = get<3>(CurrentEdge);
				if (sign*get<4>(CurrentEdge)*get<4>(checkEdge) == -1){
					answer = true;
				}
			}
			else {
				int sign = get<1>(checkEdge);
				if (sign*get<4>(CurrentEdge)*get<4>(checkEdge) == 1){
					answer = true;
				}
			}
		}
	}
	return answer;
}
void LinkEmbed(pair<vector<int>, vector<int> > crossingType, int vertexNum, pair<vector<int>, vector<int> > &adjList, vector<int> &crossingSign){
	vector<std::tuple<int, int, int, int, int> > Edges;

	for (unsigned int index = 0; index < adjList.first.size(); index++){
		int vertex1 = adjList.first[index];
		int vertex2 = adjList.second[index];
		//cout << "Vertex 1 = " << vertex1 << "     vertex 2 =   " << vertex2 << endl;
		auto newEdge1 = make_tuple(vertex1, 0, vertex2, 0, 1);
		auto newEdge2 = make_tuple(vertex2, 0, vertex1, 0, -1);

		if ((vertex2 == crossingType.first[vertex1 - 1]) || (vertex2 == crossingType.second[vertex1 - 1])){
			get<1>(newEdge1) = crossingSign[vertex1 - 1];
			get<3>(newEdge2) = crossingSign[vertex1 - 1];
		}
		if ((vertex1 == crossingType.first[vertex2 - 1]) || (vertex1 == crossingType.second[vertex2 - 1])){
			get<3>(newEdge1) = crossingSign[vertex2 - 1];
			get<1>(newEdge2) = crossingSign[vertex2 - 1];
		}

		Edges.push_back(newEdge1);
		Edges.push_back(newEdge2);
	}




	cout << endl << endl << "Edges:" << endl;
	for (auto iter = Edges.begin(); iter != Edges.end(); iter++){
		auto printedge = *iter;
		cout << get<0>(printedge) << "  " << get<1>(printedge) << "  " << get<2>(printedge) << "  " << get<3>(printedge) << "  " << get<4>(printedge) << endl;

	}

	vector<vector<int> > Faces;
	bool flag = true;
	int E = Edges.size() / 2;
	while (flag){
		vector<int> CurrentFace;

		auto StartEdge = Edges[0];
		auto CurrentEdge = StartEdge;
		CurrentFace.push_back(get<0>(StartEdge));
		Edges.erase(Edges.begin());
		bool flaginner = true;
		int counterinner = 0;
		while (flaginner){

			for (auto iter = Edges.begin(); iter != Edges.end(); iter++){
				auto checkEdge = *iter;

				if (LinksCheckNext(CurrentEdge, checkEdge, crossingType)){
					CurrentEdge = checkEdge;
					Edges.erase(iter);
					CurrentFace.push_back(get<0>(CurrentEdge));
					break;
				}

			}
			auto printedge = CurrentEdge;
			//cout << endl << get<0>(printedge) << "  " << get<1>(printedge) << "  " << get<2>(printedge) << "  " << get<3>(printedge) << "  " << get<4>(printedge) << endl;
			//cout << endl << "Face = ";
			//for (auto it = CurrentFace.begin(); it != CurrentFace.end(); it++){
			//cout << *it << "  ";
			//}
			if (LinksCheckNext(CurrentEdge, StartEdge, crossingType)){
				flaginner = false;
			}

		}
		Faces.push_back(CurrentFace);
		flag = (Edges.size() != 0);
	}
	cout << "The Faces of the associated surface are:" << endl;
	for (auto it = Faces.begin(); it != Faces.end(); it++){
		auto CurrentFace = *it;
		std::cout << "Face :  ";
		for (auto it2 = CurrentFace.begin(); it2 != CurrentFace.end(); it2++){
			std::cout << *it2 << "  ";
		}
		std::cout << endl << endl;
	}

	//Check the Euler Characteristic to verify the Gauss Code is planar
	int F = Faces.size();
	int V = vertexNum;
	int Chi = V - E + F;
	if (Chi != 2){
		cout << "The Euler Characteristic was computed to be: " << Chi << " =/=  2" << endl << "Hence the Gauss Code does not describe a planar knot, please check";
		cout << endl << "V = " << V << endl << "E = " << E << endl << "F = " << F << endl;
		exit(EXIT_FAILURE);
	}



	vector<vector<int> > TriangulationFaces;
	for (vector<vector<int> >::iterator iter = Faces.begin(); iter != Faces.end(); iter++){
		vector<int> BigFace = *iter;
		while (BigFace.size() != 3){
			int v1 = BigFace[0];
			int v3 = BigFace[2];
			bool check = false;
			for (unsigned int iter = 0; iter < adjList.first.size(); iter++){
				if ((adjList.first[iter] == v1) && (adjList.second[iter] == v3)){
					check = true;
				}
				if ((adjList.first[iter] == v3) && (adjList.second[iter] == v1)){
					check = true;
				}
			}


			if (check){
				for (unsigned int innerit = 3; innerit < BigFace.size(); innerit++){
					adjList.first.push_back(BigFace[1]);
					adjList.second.push_back(BigFace[innerit]);
					//vector<int> NewFace{ BigFace[1], BigFace[innerit - 1], BigFace[innerit] };
					vector<int> NewFace;
					NewFace.push_back(BigFace[1]);
					NewFace.push_back(BigFace[innerit - 1]);
					NewFace.push_back(BigFace[innerit]);
					TriangulationFaces.push_back(NewFace);
				}
				std::array<int, 3> iBigFace = { BigFace[0], BigFace[1], BigFace[BigFace.size() - 1] };
				BigFace = vector<int>(iBigFace.begin(), iBigFace.end());
			}
			else {
				adjList.first.push_back(BigFace[0]);
				adjList.second.push_back(BigFace[2]);
				array<int, 3> iNewFace = { BigFace[0], BigFace[1], BigFace[2] };
				vector<int> NewFace(iNewFace.begin(), iNewFace.end());
				TriangulationFaces.push_back(NewFace);
				BigFace.erase(BigFace.begin() + 1);
			}
		}

		TriangulationFaces.push_back(BigFace);
	}

	std::cout << "The triangulation is given by:  " << endl << endl;
	for (auto it = TriangulationFaces.begin(); it != TriangulationFaces.end(); it++){
		auto CurrentFace = *it;
		std::cout << "Face :  ";
		for (auto it2 = CurrentFace.begin(); it2 != CurrentFace.end(); it2++){
			std::cout << *it2 << "  ";
		}
		std::cout << endl << endl;
	}

	//std::cout << endl << endl;
	//std::cout << "Triangulation Adj List:" << endl << endl;

	//for (vector<int>::iterator it = adjList.first.begin(); it != adjList.first.end(); it++) {
	//std::cout << *it << "  ";
	//}
	//std::cout << endl << endl;
	//for (vector<int>::iterator it = adjList.second.begin(); it != adjList.second.end(); it++) {
	//std::cout << *it << "  ";
	//}
	//std::cout << endl << endl;

}



//--------------------------------------------------------------------------------------------------------------------------------------------------------



// Two Page Embedding of Graph
//--------------------------------------------------------------------------------------------------------------------------------------------------------

vector<int> findNeighbours(pair<vector<int>, vector<int> > adjList, int n){
	vector<int> neighbourList;
	for (unsigned int index = 0; index < adjList.first.size(); index++){
		if (adjList.first[index] == n) {
			neighbourList.push_back(adjList.second[index]);
		}
		else if (adjList.second[index] == n)
			neighbourList.push_back(adjList.first[index]);
	}
	sort(neighbourList.begin(), neighbourList.end());
	return neighbourList;
}
//Given an adjacency list, and a vertex, lists the neighbours of said vertex

int FollowEdge(pair<vector<int>, vector<int> > adjList, int Start, int FirstNeighbour, int origvertNum){
	int PreviousNeighbour = Start;
	int CurrentNeighbour = FirstNeighbour;
	while (true){
		vector<int> Neighbours = findNeighbours(adjList, CurrentNeighbour);


		if (CurrentNeighbour <= origvertNum){
			return CurrentNeighbour;
		}
		else if (Neighbours[0] == PreviousNeighbour) {
			PreviousNeighbour = CurrentNeighbour;
			CurrentNeighbour = Neighbours[1];
		}
		else {
			PreviousNeighbour = CurrentNeighbour;
			CurrentNeighbour = Neighbours[0];
		}
	}
	return 0;
}
//Given an adjacency list, a vertex and an edge eminating from that vertex, follows the path starting with that edge until a vertex of degree > 2 is found, and outputs said vertex

string TwoPageCode(vector<int> vertexOrdering, pair<vector<int>, vector<int> > &adjList, pair<vector<int>, vector<int> > CrossingTypeList, int VertNum) {
	string TwoPageCode = "";
	for (vector<int>::iterator index = vertexOrdering.begin(); index != vertexOrdering.end(); index++){

		string NewCodePart = "(";
		vector<int> Neighbours = findNeighbours(adjList, *index);
		vector<bool> IsAbove;
		if (*index <= VertNum){
			for (vector<int>::iterator innerIndex = Neighbours.begin(); innerIndex != Neighbours.end(); innerIndex++) {
				IsAbove.push_back((FollowEdge(adjList, *index, *innerIndex, VertNum) == CrossingTypeList.first[*index - 1]) || (FollowEdge(adjList, *index, *innerIndex, VertNum) == CrossingTypeList.second[*index - 1]));
			}
		}



		if (IsAbove.size() == 4){



			if (IsAbove[0] == IsAbove[1]){
				int temp = Neighbours[2];
				Neighbours[2] = Neighbours[1];
				Neighbours[1] = temp;
				bool temp2 = IsAbove[2];
				IsAbove[2] = IsAbove[1];
				IsAbove[1] = temp2;
			}

			if (!IsAbove[0]){
				int temp = Neighbours[1];
				Neighbours[1] = Neighbours[0];
				Neighbours[0] = temp;
				bool temp2 = IsAbove[1];
				IsAbove[1] = IsAbove[0];
				IsAbove[0] = temp2;

			}

			if (!IsAbove[2]){
				int temp = Neighbours[3];
				Neighbours[3] = Neighbours[2];
				Neighbours[2] = temp;
				bool temp2 = IsAbove[3];
				IsAbove[3] = IsAbove[2];
				IsAbove[2] = temp2;

			}





			//cout << endl << endl << "Test Data:   Vertex Number is   " << *index << endl;
			//cout << "Neighbours (in order above below above below) are " << IsAbove[0] << "  " << IsAbove[1] << "  " << IsAbove[2] << "  " << IsAbove[3];
			//cout << "Neighbours (in order above below above below) are " << Neighbours[0] << "  " << Neighbours[1] << "  " << Neighbours[2] << "  " << Neighbours[3];


		}


		for (vector<int>::iterator innerIndex = Neighbours.begin(); innerIndex != Neighbours.end(); innerIndex++){
			if (find(vertexOrdering.begin(), vertexOrdering.end(), *index) < find(vertexOrdering.begin(), vertexOrdering.end(), *innerIndex)){

				if ((*index <= VertNum) || (*innerIndex <= VertNum)){
					NewCodePart = NewCodePart + "UR";
				}
				else {
					NewCodePart = NewCodePart + "DR";
				}
			}
			else {
				if ((*index <= VertNum) || (*innerIndex <= VertNum)){
					NewCodePart = NewCodePart + "UL";
				}
				else {
					NewCodePart = NewCodePart + "DL";
				}

			}
		}

		if (NewCodePart == "(ULULURUR"){
			int first = 0;
			for (unsigned int iter = 0; iter < vertexOrdering.size(); iter++){
				if ((vertexOrdering[iter] == Neighbours[0]) || (vertexOrdering[iter] == Neighbours[1]) || (vertexOrdering[iter] == Neighbours[2]) || (vertexOrdering[iter] == Neighbours[3])){
					first = iter;
					iter = vertexOrdering.size();
				}
			}
			int LeftMost = vertexOrdering[first];
			if ((LeftMost == Neighbours[0]) || (LeftMost == Neighbours[2])){
				NewCodePart = "(ULURURUL";
			}
			else {
				NewCodePart = "(ULULURUR";
			}
		}
		else if (NewCodePart == "(ULURURUL"){
			int first = 0;
			for (unsigned int iter = 0; iter < vertexOrdering.size(); iter++){
				if ((vertexOrdering[iter] == Neighbours[0]) || (vertexOrdering[iter] == Neighbours[1]) || (vertexOrdering[iter] == Neighbours[2]) || (vertexOrdering[iter] == Neighbours[3])){
					first = iter;
					iter = vertexOrdering.size();
				}
			}
			int LeftMost = vertexOrdering[first];
			if ((LeftMost == Neighbours[0]) || (LeftMost == Neighbours[2])){
				NewCodePart = "(ULURURUL";
			}
			else {
				NewCodePart = "(ULULURUR";
			}

		}
		else if (NewCodePart == "(URURULUL"){
			int first = 0;
			for (unsigned int iter = 0; iter < vertexOrdering.size(); iter++){
				if ((vertexOrdering[iter] == Neighbours[0]) || (vertexOrdering[iter] == Neighbours[1]) || (vertexOrdering[iter] == Neighbours[2]) || (vertexOrdering[iter] == Neighbours[3])){
					first = iter;
					iter = vertexOrdering.size();
				}
			}
			int LeftMost = vertexOrdering[first];
			if ((LeftMost == Neighbours[0]) || (LeftMost == Neighbours[2])){
				NewCodePart = "(ULURURUL";
			}
			else {
				NewCodePart = "(ULULURUR";
			}
		}
		else if (NewCodePart == "(URULULUR"){
			int first = 0;
			for (unsigned int iter = 0; iter < vertexOrdering.size(); iter++){
				if ((vertexOrdering[iter] == Neighbours[0]) || (vertexOrdering[iter] == Neighbours[1]) || (vertexOrdering[iter] == Neighbours[2]) || (vertexOrdering[iter] == Neighbours[3])){
					first = iter;
					iter = vertexOrdering.size();
				}
			}
			int LeftMost = vertexOrdering[first];
			if ((LeftMost == Neighbours[0]) || (LeftMost == Neighbours[2])){
				NewCodePart = "(ULURURUL";
			}
			else {
				NewCodePart = "(ULULURUR";
			}
		}


		if (Neighbours.size() != 0){
			TwoPageCode = TwoPageCode + NewCodePart + ")";
		}
		//cout << TwoPageCode << endl;

	}
	return TwoPageCode;
}
//Takes an ordering of vertices along a spine, as well as the required adjacencies and outputs a string ("TwoPageCode") corresponding to 
//the crossings (with sign) in order to interpret the two page embedding

void spineEmbedding(vector<int> &vertexOrdering, pair<vector<int>, vector<int> > &adjList, int &vertNum){
	vector<signed int> NewVertexList;
	pair<vector<int>, vector<int> > NewAdjList;
	NewVertexList.push_back(vertexOrdering[0]);
	NewVertexList.push_back(vertexOrdering[1]);
	NewAdjList.first.push_back(vertexOrdering[0]);
	NewAdjList.second.push_back(vertexOrdering[1]);
	int NewCrossingNum = 0;

	for (int index = 2; index < vertNum; index++){

		int VertexToAdd = vertexOrdering[index];
		vector<int> Neighbours = findNeighbours(adjList, VertexToAdd);
		vector<int> AddedNeighbours;
		for (unsigned int innerindex = 0; innerindex < NewVertexList.size(); innerindex++){
			if (find(Neighbours.begin(), Neighbours.end(), NewVertexList[innerindex]) != Neighbours.end()) { // If given vertex is a Neighbour
				AddedNeighbours.push_back(NewVertexList[innerindex]);
			}
		}
		//cout << endl;
		//for (vector<int>::iterator id = AddedNeighbours.begin(); id != AddedNeighbours.end(); id++){ cout << *id << "  "; }
		int PlaceToAdd = 0;
		bool flag = true;
		for (unsigned int iter = 0; iter < Neighbours.size(); iter++){
			if (flag){
				if (NewVertexList[iter] == AddedNeighbours[0]){
					flag = false;
					PlaceToAdd = iter + 1;
				}
			}
		}
		cout << index << endl;
		NewVertexList.insert(NewVertexList.begin() + PlaceToAdd, VertexToAdd);//Add the new vertex in the required place
		NewAdjList.first.push_back(NewVertexList[PlaceToAdd - 1]);
		NewAdjList.second.push_back(NewVertexList[PlaceToAdd]);//Add the edge to the left of the new vertex

		for (unsigned int innerindex = 0; innerindex < AddedNeighbours.size(); innerindex++){
			if (AddedNeighbours[innerindex] == NewVertexList[PlaceToAdd + 1]){
				NewAdjList.first.push_back(VertexToAdd);
				NewAdjList.second.push_back(AddedNeighbours[innerindex]);
				AddedNeighbours.erase(AddedNeighbours.begin() + innerindex);
			}
		}


		for (unsigned int innerindex = 1; innerindex <AddedNeighbours.size(); innerindex++){


			vector<int>::iterator TempName = find(NewVertexList.begin(), NewVertexList.end(), AddedNeighbours[innerindex]);
			NewVertexList.insert(TempName, vertNum + NewCrossingNum + 1);
			NewVertexList.insert(NewVertexList.begin() + PlaceToAdd + 1, vertNum + NewCrossingNum);
			NewAdjList.first.push_back(VertexToAdd);
			NewAdjList.second.push_back(vertNum + NewCrossingNum);
			NewAdjList.first.push_back(vertNum + NewCrossingNum);
			NewAdjList.second.push_back(vertNum + NewCrossingNum + 1);
			NewAdjList.first.push_back(vertNum + NewCrossingNum + 1);
			NewAdjList.second.push_back(AddedNeighbours[innerindex]);


			NewCrossingNum = NewCrossingNum + 2;
		}

		//cout << endl;
		//for (vector<int>::iterator it = NewVertexList.begin(); it != NewVertexList.end(); it++){
		//	cout << *it << "  ";
		//}
		//cout << endl << "AdjListLength = " << NewAdjList.second.size() << endl;
	}
	//cout << endl << "With";
	//for (unsigned int iter = 0; iter < NewAdjList.first.size(); iter++) {
	//	cout << endl << "Vertex " << NewAdjList.first[iter] << " adjacent to " << NewAdjList.second[iter];
	//}
	//cout << endl;

	adjList = NewAdjList;
	vertexOrdering = NewVertexList;
	vertNum = vertNum + NewCrossingNum - 1;
	return;
}
/*
Implements the algorithm of Di Giacomo et al. Finding a two page embedding of a maximal planar graph given canonical order:
1: Starting with an entry list of vertics, we add the first two (and the edge between them)
2: For each new vertex in the ordering, find the leftmost of the already added vertices adjacent to the current vertex
3: Add that vertex just "to the right" of the aforementioned neighbour.
4: For each additional neighbour of the vertex being added, added two more vertices, and edges (for more details, see Di Giacomo)
*/

void Restriction(pair<vector<int>, vector<int> > oldAdjList, pair<vector<int>, vector<int> > &newAdjList, int origVertNum){
	vector<bool> deletions(newAdjList.first.size());
	for (unsigned int index = 0; index < deletions.size(); index++){
		int end1 = FollowEdge(newAdjList, newAdjList.first[index], newAdjList.second[index], origVertNum);
		//cout << end1 << endl;
		int end2 = FollowEdge(newAdjList, newAdjList.second[index], newAdjList.first[index], origVertNum);
		//cout << end2 << endl;

		deletions[index] = false;
		for (unsigned int innerindex = 0; innerindex < oldAdjList.first.size(); innerindex++){
			if (((oldAdjList.first[innerindex] == end1) && (oldAdjList.second[innerindex] == end2)) || (((oldAdjList.first[innerindex] == end2) && (oldAdjList.second[innerindex] == end1)))){
				deletions[index] = true;
			}
		}
		//cout << deletions[index] << endl;
		//cout << endl << endl;
	}

	pair<vector<int>, vector<int> > tempAdj;

	for (unsigned int index = 0; index < deletions.size(); index++){
		if (deletions[index]){
			tempAdj.first.push_back(newAdjList.first[index]);
			tempAdj.second.push_back(newAdjList.second[index]);
		}
	}
	newAdjList = tempAdj;
}
//Restricts our two page embedding of a triangulation to a two page embedding of the original graph
//--------------------------------------------------------------------------------------------------------------------------------------------------------



//Three Page Embedding
//--------------------------------------------------------------------------------------------------------------------------------------------------------

string Three_Page_Emb(string two_page_code, int vert_num)         // Converts a two page embedding code to a three page embedding
{
	string three_page_code = "";
	while (two_page_code.length() > 0) {
		string test_chunk_short = two_page_code.substr(0, 6);
		string test_chunk_long = two_page_code.substr(0, 10);
		if (regex_search(test_chunk_short, reg1)) {
			two_page_code.erase(0, 6);
			three_page_code = three_page_code + test_chunk_short;
			//std::cout << "Code part " << test_chunk_short << " was left unaltered" << endl;
		}
		else {
			two_page_code.erase(0, 10);

			if (test_chunk_long[6] == 'L'){
				string reordered = "(" + test_chunk_long.substr(5, 4) + test_chunk_long.substr(1, 4) + ")";
				test_chunk_long = reordered;
			}
			string new_crossing = "";
			if (test_chunk_long[3] == test_chunk_long[7]){
				string page = test_chunk_long.substr(3, 1);
				char new_page = ' ';
				if (page == "U") {
					new_page = 'D';
				}
				else {
					new_page = 'U';
				}

				if (test_chunk_long[1] == test_chunk_long[5]){
					string LRString = test_chunk_long.substr(2, 1) + test_chunk_long.substr(4, 1) + test_chunk_long.substr(6, 1) + test_chunk_long.substr(8, 1);
					if (LRString == "LLLL") {
						//new_crossing = "(XR" + page + "L)(" + new_page + "R" + page + "L)(" + page + "LXL)(ULDL)";
						new_crossing = "(" + page + "L" + new_page + "R)(" + page + "LXR)(ULDL)(" + page + "LXL)";
					}
					else if (LRString == "LLLR"){
						new_crossing = "(" + page + "LXR)(" + page + "L" + new_page + "R)(" + page + "LXL)(" + new_page + "L" + page + "R)";
					}
					else if (LRString == "LLRL"){
						new_crossing = "(" + page + "L" + new_page + "R)(" + page + "L" + "XR)(" + page + "L" + new_page + "L)(XL" + page + "R)";

					}
					else if (LRString == "LLRR"){
						new_crossing = "(" + page + "LXR)(" + page + "L" + new_page + "R)(XL" + page + "R)(" + new_page + "L" + page + "R)";
					}
					else if (LRString == "LRLL"){
						new_crossing = "(" + page + "LXR)(" + page + "L" + new_page + "R)(" + page + "LXL)(" + new_page + "L" + page + "R)";
					}
					else if (LRString == "LRRL"){
						new_crossing = "(" + page + "L" + new_page + "R)(" + page + "LXR)(" + new_page + "L" + page + "R)(XL" + page + "R)";
					}
					else if (LRString == "LRRR"){
						new_crossing = "(" + page + "LXR)(URDR)(XL" + page + "R)(" + new_page + "L" + page + "R)";
					}
					else if (LRString == "RLLL"){
						new_crossing = "(" + page + "L" + new_page + "R)(" + page + "L" + "XR)(" + page + "L" + new_page + "L)(XL" + page + "R)";
					}
					else if (LRString == "RLLR"){
						new_crossing = "(" + page + "L" + new_page + "R)(" + page + "LXR)(" + new_page + "L" + page + "R)(XL" + page + "R)";
					}
					else if (LRString == "RLRR"){
						new_crossing = "(" + page + "L" + new_page + "R)(" + page + "RXR)(" + new_page + "L" + page + "R)(XL" + page + "R)";
					}
					else if (LRString == "RRLL"){
						new_crossing = "(" + page + "LXR)(" + page + "L" + new_page + "R)(XL" + page + "R)(" + new_page + "L" + page + "R)";
					}
					else if (LRString == "RRLR"){
						new_crossing = "(" + page + "LXR)(URDR)(XL" + page + "R)(" + new_page + "L" + page + "R)";
					}
					else if (LRString == "RRRL"){
						new_crossing = "(" + page + "L" + new_page + "R)(" + page + "RXR)(" + new_page + "L" + page + "R)(XL" + page + "R)";
					}
					else if (LRString == "RRRR"){
						new_crossing = "(URDR)(" + page + "RXR)(" + new_page + "L" + page + "R)(XL" + page + "R)";
						//new_crossing = "(" + page + "RXR)" + "(URDR)(XL" + page + "R)(" + new_page + "L" + page + "R)";
					}
				}
				else{

					new_crossing = new_crossing + test_chunk_long.substr(0, 3) + "XR)";
					new_crossing = new_crossing + "(" + test_chunk_long.substr(5, 2) + new_page + "R)";
					new_crossing = new_crossing + "(XL" + test_chunk_long.substr(3, 2) + ")";
					new_crossing = new_crossing + "(" + new_page + "L" + test_chunk_long.substr(7, 3);
				}

				three_page_code = three_page_code + new_crossing;
				//std::cout << "The code given by " << test_chunk_long << " was changed to " << new_crossing << endl;
			}
			else {
				new_crossing = new_crossing + test_chunk_long.substr(0, 3) + "XR)";
				new_crossing = new_crossing + "(" + test_chunk_long.substr(3, 2) + test_chunk_long.substr(7, 2) + ")";
				new_crossing = new_crossing + "(XL" + test_chunk_long.substr(5, 2) + ")";
				//std::cout << "The code given by " << test_chunk_long << " was changed to " << new_crossing << endl;
				three_page_code = three_page_code + new_crossing;
			}

		}
	}


	return three_page_code;
}
//Converts a two page embedding (roughly (URURDRDL)(ULURDRDL)... into a three page embedding, on a crossing by crossing basis using the crossingtype

void removeDoubles(string &threePageEmbedding){
	signed int length = threePageEmbedding.size() / 6;
	for (int index = 0; index < length; ++index){
		string tempString = threePageEmbedding.substr((length - index - 1) * 6, 6);
		if (tempString == "(ULUL)") {
			threePageEmbedding.replace((length - index - 1) * 6, 6, "(ULDR)(DLUL)");

		}
		else if (tempString == "(DLDL)") {
			threePageEmbedding.replace((length - index - 1) * 6, 6, "(DLUR)(ULDL)");

		}
		else if (tempString == "(DRDR)") {
			threePageEmbedding.replace((length - index - 1) * 6, 6, "(DRUR)(ULDR)");

		}
		else if (tempString == "(URUR)") {
			threePageEmbedding.replace((length - index - 1) * 6, 6, "(URDR)(DLUR)");

		}

		else if (tempString == "(ULUR)") {
			threePageEmbedding.replace((length - index - 1) * 6, 6, "");

		}
		else if (tempString == "(URUL)") {
			threePageEmbedding.replace((length - index - 1) * 6, 6, "");

		}
		else if (tempString == "(DLDR)") {
			threePageEmbedding.replace((length - index - 1) * 6, 6, "");

		}
		else if (tempString == "(DRDL)") {
			threePageEmbedding.replace((length - index - 1) * 6, 6, "");

		}
		else if (tempString == "(XRXL)") {
			threePageEmbedding.replace((length - index - 1) * 6, 6, "");

		}
		else if (tempString == "(XLXR)") {
			threePageEmbedding.replace((length - index - 1) * 6, 6, "");

		}
	}
	length = threePageEmbedding.size() / 6;
	for (int index = 0; index < length - 1; ++index){
		string tempString = threePageEmbedding.substr((length - index - 2) * 6, 12);
		if (tempString == "(DLUR)(ULDR)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "");
		}
		else if (tempString == "(URDL)(DRUL)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "");
		}
		else if (tempString == "(URDL)(ULDR)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "");
		}
		else if (tempString == "(DLUR)(ULDR)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "");
		}
		else if (tempString == "(ULDR)(URDL)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "");
		}
		else if (tempString == "(ULDR)(DLUR)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "");
		}
		else if (tempString == "(DRUL)(DLUR)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "");
		}
		else if (tempString == "(DRUL)(URLD)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "");
		}


		else if (tempString == "(XLUR)(ULDR)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "(XLDR)");
		}
		else if (tempString == "(URXL)(ULDR)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "(XLDR)");
		}
		else if (tempString == "(XLUR)(DRUL)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "(XLDR)");
		}
		else if (tempString == "(URXL)(DRUL)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "(XLDR)");
		}


		else if (tempString == "(XLDR)(DLUR)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "(XLUR)");
		}
		else if (tempString == "(DRXL)(DLUR)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "(XLUR)");
		}
		else if (tempString == "(XLDR)(URDL)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "(XLUR)");
		}
		else if (tempString == "(DRXL)(URDL)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "(XLUR)");
		}



		else if (tempString == "(DLUR)(ULXR)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "(DLXR)");
		}
		else if (tempString == "(DLUR)(XRUL)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "(DLXR)");
		}
		else if (tempString == "(URDL)(ULXR)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "(DLXR)");
		}
		else if (tempString == "(URDL)(ULXR)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "(DLXR)");
		}


		else if (tempString == "(ULDR)(DLXR)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "(ULXR)");
		}
		else if (tempString == "(ULDR)(XRDL)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "(ULXR)");
		}
		else if (tempString == "(DRUL)(DLXR)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "(ULXR)");
		}
		else if (tempString == "(DRUL)(DLXR)"){
			threePageEmbedding.replace((length - index - 2) * 6, 12, "(ULXR)");
		}



	}


}
//Performs a trivial simplification fo the three page embedding, removing some unnecessary vertices eg. (ULUR) or (XLXR)

//Graphics:
void MyFilledCircle(Mat img, Point center)
{
	int thickness = -1;
	int lineType = 4;

	circle(img,
		center,
		2,
		Scalar(255, 0, 0),
		thickness,
		lineType);
}
//Draws a circle at centre given, of radius 2 (in blue)

void MyLine(Mat img, Point start, Point end, int colour)
{
	int thickness = 1;
	int lineType = 8;
	int RED = 0;
	int GREEN = 0;
	int BLUE = 0;
	//if (colour == -1){
	//RED = 255;
	//}
	if (colour == 0){
		GREEN = 255;
	}
	if (colour == 1){
		BLUE = 255;
	}
	line(img,
		start,
		end,
		Scalar(RED, GREEN, BLUE),
		thickness,
		CV_AA);
}
//Draws a line from start to end (in black)

void MyGraph(Mat img, vector<int> leftEnds, vector<int> rightEnds, int numPoints, int pageNum) {
	int stanDistance = int(w / (numPoints + 1));
	int pageMultiplier;
	int colour = 0;
	if (pageNum == 1){
		pageMultiplier = 2;
	}
	else if (pageNum == 2){
		pageMultiplier = -2;
		colour = -1;
	}
	else {
		pageMultiplier = 1;
		colour = 1;
	}

	pair<vector<int>, vector<int>> Coords3dX;
	pair<vector<int>, vector<int>> Coords3dY;
	pair<vector<int>, vector<int>> Coords3dZ;





	for (unsigned int index = 0; index < leftEnds.size(); ++index){
		int midpoint = ((stanDistance*(rightEnds[index])) + (stanDistance*(leftEnds[index]))) / 2;
		signed int height = pageMultiplier*(((stanDistance*rightEnds[index]) - (stanDistance*leftEnds[index])) / 4);
		MyLine(img, Point((leftEnds[index])*stanDistance, w / 2), Point(midpoint, (w / 2) - height), colour);

		Coords3dX.first.push_back((leftEnds[index])*stanDistance);
		Coords3dX.second.push_back(midpoint);

		Coords3dY.first.push_back(w / 2);
		Coords3dZ.first.push_back(w / 2);

		if (pageNum == 1) {
			Coords3dY.second.push_back(int(w / 2 + height*0.5));
			Coords3dZ.second.push_back(int(height*sqrt(3)*0.5));
		}
		else if (pageNum == 2){
			Coords3dY.second.push_back(int(w / 2 + height*0.5));
			Coords3dZ.second.push_back((int(height*sqrt(3)*0.5)));
		}
		else {
			Coords3dY.second.push_back(int(w / 2 - height));
			Coords3dZ.second.push_back(0);
		}

		MyLine(img, Point((rightEnds[index])*stanDistance, w / 2), Point(midpoint, (w / 2) - height), colour);

		Coords3dX.first.push_back((rightEnds[index])*stanDistance);
		Coords3dX.second.push_back(midpoint);

		Coords3dY.first.push_back(w / 2);
		Coords3dZ.first.push_back(w / 2);

		if (pageNum == 1) {
			Coords3dY.second.push_back(int(w / 2 + height*0.5));
			Coords3dZ.second.push_back(int(height*sqrt(3)*0.5));
		}
		else if (pageNum == 2){
			Coords3dY.second.push_back(int(w / 2 + height*0.5));
			Coords3dZ.second.push_back((int(height*sqrt(3)*0.5)));
		}
		else {
			Coords3dY.second.push_back(w / 2 - height);
			Coords3dZ.second.push_back(0);
		}

	}
	for (int index = 0; index < numPoints; ++index) {
		MyFilledCircle(img, Point((index + 1)*stanDistance, w / 2));
	}

} // Draws the desired graph
//For each page of the three page embedding, calls MyLine and MyFilledCircle to draw the graph parts corresponding to the given page (given by "pagenum")


string gotoPage(string three_page_embedding, char pagenum) {
	signed int length = three_page_embedding.size() / 6;
	string pageCode = "";
	for (int index = 0; index < length; ++index){
		string tempString = three_page_embedding.substr(index * 6, 6);
		if (tempString[1] == pagenum){
			pageCode = pageCode + tempString[2];
		}
		else if (tempString[3] == pagenum) {
			pageCode = pageCode + tempString[4];
		}
		else{
			pageCode = pageCode + '0';
		}
	}
	//cout << pageCode << endl;
	return pageCode;
}
//Takes the large three page embedding string, and converts to a string detailing the drawing on the page given by "pagenum"

pair < vector<int>, vector<int> > Coords(string page_string)
{
	int numVertices = page_string.length();
	vector<int> leftEnds(numVertices);
	vector<int> rightEnds(numVertices);
	int firstLeft = page_string.find_first_of("L");
	int edgeNumber = 0;
	while (firstLeft != -1) {
		int lastRight = page_string.find_last_of("R", firstLeft);
		if (lastRight == -1) {
			std::cout << "Code was invalid, please check" << endl;
			exit(EXIT_FAILURE);
		}
		else {
			leftEnds[edgeNumber] = lastRight + 1;
			rightEnds[edgeNumber] = firstLeft + 1;
			page_string[lastRight] = '0';
			page_string[firstLeft] = '0';
			edgeNumber++;
			firstLeft = page_string.find_first_of("L");
		}


	}
	leftEnds.resize(edgeNumber);
	rightEnds.resize(edgeNumber);
	return make_pair(leftEnds, rightEnds);
}
//Calculates the coordinates for the graph associated to the given code (so that MyLine can be called to draw the edges)
//--------------------------------------------------------------------------------------------------------------------------------------------------------



//Final Outputs
//--------------------------------------------------------------------------------------------------------------------------------------------------------

string semiGroup(string codeChunk){
	if ((codeChunk == "(ULDL)") || (codeChunk == "(DLUL)")){
		return "c1 ";
	}
	else if ((codeChunk == "(ULDR)") || (codeChunk == "(DLUL)")){
		return "b1 ";
	}
	else if ((codeChunk == "(ULXL)") || (codeChunk == "(XLUL)")){
		return "c2 ";
	}
	else if ((codeChunk == "(ULXR)") || (codeChunk == "(XRUL)")){
		return "d2 ";
	}
	else if ((codeChunk == "(URDL)") || (codeChunk == "(DLUR)")){
		return "d1 ";
	}
	else if ((codeChunk == "(URDR)") || (codeChunk == "(DRUR)")){
		return "a1 ";
	}
	else if ((codeChunk == "(URXL)") || (codeChunk == "(XLUR)")){
		return "b2 ";
	}
	else if ((codeChunk == "(URXR)") || (codeChunk == "(XRUR)")){
		return "a2 ";
	}
	else if ((codeChunk == "(DLXL)") || (codeChunk == "(XLDL)")){
		return "c0 ";
	}
	else if ((codeChunk == "(DLXR)") || (codeChunk == "(XRDL)")){
		return "b0 ";
	}
	else if ((codeChunk == "(DRXL)") || (codeChunk == "(XLDR)")){
		return "d0 ";
	}
	else if ((codeChunk == "(DRXR)") || (codeChunk == "(XRDR)")){
		return "a0 ";
	}
	else{
		return "";
	}
}
//Converts our (ULDR)(URUR)... code into a more conventional semi-group code

bool String_Check(string two_page_code)				 // Checks the validity of a two page embedding code
{
	string edited_str = two_page_code;
	while (edited_str.length() > 0) {
		string test_chunk_short = edited_str.substr(0, 6);
		string test_chunk_long = edited_str.substr(0, 10);
		if (regex_match(test_chunk_short, reg1)) {
			edited_str.erase(0, 6);
		}
		else if (regex_match(test_chunk_long, reg2)) {
			edited_str.erase(0, 10);
		}
		else {
			return 0;
		}
	}

	return true;
}
//--------------------------------------------------------------------------------------------------------------------------------------------------------



int main() {

	//Take User inputs

	std::cout << "Please enter a Gauss Code, or type List for a selection of in built codes." << endl << "For advice on the form of the code, Type Help" << endl;
	string GaussCode;
	std::getline(std::cin, GaussCode);
	if (GaussCode == "List"){
		std::cout << "Please type the appropriate number to select the code:" << endl << endl
			<< "1: (3_1)   Trefoil" << endl
			<< "2: (4_1)" << endl
			<< "3: (5_1)" << endl
			<< "4: (6_3)" << endl
			<< "5: Linked Trefoils (same orientation)" << endl
			<< "6: Star of David" << endl
			<< endl;
		string selection;
		std::getline(std::cin, selection);
		cout << endl;
		if (selection[0] == '1'){
			GaussCode = "1 +2 3 +1 2 +3";
		}
		else if (selection[0] == '2'){
			GaussCode = "1 +2 3 -4 2 +1 4 -3";
		}
		else if (selection[0] == '3'){
			GaussCode = "1 +2 3 +4 5 +1 2 +3 4 +5";
		}
		else if (selection[0] == '4'){
			GaussCode = "1 +6 2 +1 4 -5 6 +2 3 -4 5 -3";
		}
		else if (selection[0] == '5'){
			GaussCode = "1 +2 +4 5 3 +1 2 +3 : 4 +5 8 +7 6 +8 7 +6";
		}
		else if (selection[0] == '6'){
			GaussCode = "1 +2 3 +4 5 +6 : 2 +3 4 +5 6 +1";
		}
		else{
			exit(EXIT_FAILURE);
		}
	}
	if (GaussCode[0] == 'H'){
		std::cout << "Help goes here" << endl;
		exit(EXIT_FAILURE);
	}

	clock_t t1, t2;
	t1 = clock();

	//Perform preliminary checks on the Gauss Code, format into the desired form and extract necessary additional data
	/*
	pair<vector<int>, vector<int> > gaussCode = GaussCheck(GaussCode);
	removeDouble(gaussCode);
	int vertNum = gaussCode.first.size() / 2;
	vector<int> Empty;
	pair<vector<int>, vector<int> > adjList = make_pair(Empty, Empty);
	pair<vector<int>, vector<int> > CrossingType = make_pair(Empty, Empty);
	extractGraph(gaussCode, adjList, CrossingType, vertNum);
	int origVertNum = vertNum;
	*/
	//Output some information to user:
	//		The Gauss Code in the new form, with signs seperated from the vertex numbers
	//		An Adjacency List
	//		"Crossing Type": For each vertex of the graph, this is -1 if the vertex is degree 2 (not a crossing) or 
	//						 lists the edges on the under arc of the crossing if it is a crossing

	std::cout << "GaussCode:" << GaussCode << endl;

	//extractGraphLinks(TestCode);
	vector<int> Empty;
	auto adjList = make_pair(Empty, Empty);
	pair<vector<int>, vector<int>> CrossingType = adjList;
	vector<int> CrossingSign = Empty;
	int vertNum;
	extractGraphLinks(GaussCode, adjList, CrossingType, CrossingSign, vertNum);
	int origVertNum = vertNum;








	/*
	for (vector<int>::iterator it = gaussCode.first.begin(); it != gaussCode.first.end(); it++) {
	std::cout << *it << "  ";
	}
	std::cout << endl << endl;
	for (vector<int>::iterator it = gaussCode.second.begin(); it != gaussCode.second.end(); it++) {
	std::cout << *it << "  ";
	}
	std::cout << endl << endl;
	*/
	std::cout << "Adj List:" << endl << endl;


	for (vector<int>::iterator it = adjList.first.begin(); it != adjList.first.end(); it++) {
		std::cout << *it << "  ";
	}
	std::cout << endl << endl;
	for (vector<int>::iterator it = adjList.second.begin(); it != adjList.second.end(); it++) {
		std::cout << *it << "  ";
	}
	std::cout << endl << endl;

	std::cout << "Crossing Type:" << endl << endl;


	for (vector<int>::iterator it = CrossingType.first.begin(); it != CrossingType.first.end(); it++) {
		std::cout << *it << "  ";
	}
	std::cout << endl << endl;
	for (vector<int>::iterator it = CrossingType.second.begin(); it != CrossingType.second.end(); it++) {
		std::cout << *it << "  ";
	}
	std::cout << endl << endl;
	auto TriAdjList = adjList;

	//Calculate our triangulation


	LinkEmbed(CrossingType, vertNum, TriAdjList, CrossingSign);

	//Define and initialise a graph for boosts' inbuilt functionality
	typedef adjacency_list
		< vecS,
		vecS,
		undirectedS,
		property<vertex_index_t, int>,
		property < edge_index_t, int >
		>
		graph;

	typedef vector < graph_traits<graph>::vertex_descriptor >
		ordering_storage_t;

	typedef std::vector< graph_traits<graph>::edge_descriptor > vec_t;

	graph g(vertNum);

	//Make the graph g, the triangulation from above
	for (unsigned int index = 0; index < TriAdjList.first.size(); index++){
		TriAdjList.first[index]--;
		TriAdjList.second[index]--;
		add_edge(TriAdjList.first[index], TriAdjList.second[index], g);
		//cout << "Edge  " << TriAdjList.first[index] << "  " << TriAdjList.second[index]<< "  was added"<<endl;
	}



	property_map<graph, edge_index_t>::type e_index = get(edge_index, g);
	graph_traits<graph>::edges_size_type edge_count = 0;
	graph_traits<graph>::edge_iterator ei, ei_end;

	for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
		put(e_index, *ei, edge_count++);

	//Initialise an embedding
	std::vector<vec_t> embedding(num_vertices(g));

	//Embed the triangulation in the plane (Boyer-Myrvold is linear time) 
	//NB: By Whitney's Theorem, this embedding is the same as the embedding we built, up to a homeomorphism of the sphere

	boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
		boyer_myrvold_params::embedding =
		&embedding[0]
		);

	//cout << "vertNum =   " << num_vertices(g) << endl;
	e_index = get(edge_index, g);
	edge_count = 0;
	//for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
	//cout << *ei << endl;


	//Compute the canonical ordering of our triangulation
	ordering_storage_t ordering;
	planar_canonical_ordering(g, &embedding[0], back_inserter(ordering));
	ordering_storage_t::iterator oi, oi_end;

	oi_end = ordering.end();
	//cout << endl << endl << ordering.size() << endl;

	cout << "The planar canonical ordering is: ";
	vector<int> vertexOrdering;
	for (oi = ordering.begin(); oi != oi_end; ++oi) {
		cout << *oi << " ";
		vertexOrdering.push_back(*oi);
	}

	//Build the two page embedding of the graph (Di Giacomo et al.)
	spineEmbedding(vertexOrdering, TriAdjList, vertNum);
	vertNum++;
	for (unsigned int iter = 0; iter < TriAdjList.first.size(); iter++) {
		TriAdjList.first[iter]++;
		TriAdjList.second[iter]++;
	}


	for (vector<int>::iterator ind = vertexOrdering.begin(); ind != vertexOrdering.end(); ind++){ ++(*ind); }

	//Restrict back to our original graph (pre-triangulating)
	Restriction(adjList, TriAdjList, origVertNum);




	int X = vertNum - CrossingType.first.size();
	for (int iter = 0; iter < X; iter++){
		CrossingType.first.push_back(-1);
		CrossingType.second.push_back(-1);
	}

	//Compute a two page code, in the form used by the program internally
	string two_page_code = TwoPageCode(vertexOrdering, TriAdjList, CrossingType, origVertNum);

	char checkStr = '(';
	int vert_num = 0;
	for (unsigned int i = 0; i < two_page_code.length(); i++){
		if (two_page_code[i] == checkStr) {
			vert_num++;
		}
	}
	cout << endl;
	cout << two_page_code << endl;

	bool valid = String_Check(two_page_code);
	if (valid == false) {
		std::cout << " The two page code entered is not valid. Please check" << endl;
		return 0;
	}

	//Convert from two page to three page
	string answer = Three_Page_Emb(two_page_code, vert_num);

	//Trivial Simplification
	removeDoubles(answer);

	//Output the semigroup
	cout << "The semigroup crossing code is" << endl;
	for (unsigned int ind = 0; ind < answer.size() / 6; ind++){
		cout << semiGroup(answer.substr(ind * 6, 6));
	}
	cout << endl;

	//Initialise the image and output to the user
	Mat page_1_image(w, w, CV_8UC3, Scalar(255, 255, 255));
	Mat SpineEmbeddingImage(w, w, CV_8UC3, Scalar(255, 255, 255));
	string Stringtest1 = gotoPage(answer, 'U');
	string Stringtest2 = gotoPage(answer, 'D');
	string Stringtest3 = gotoPage(answer, 'X');
	pair<vector<int>, vector<int> > Answer1 = Coords(Stringtest1);
	pair<vector<int>, vector<int> > Answer2 = Coords(Stringtest2);
	pair<vector<int>, vector<int> > Answer3 = Coords(Stringtest3);
	int vertNumFinal = answer.size() / 6;
	MyGraph(page_1_image, Answer1.first, Answer1.second, vertNumFinal, 1);
	MyGraph(page_1_image, Answer2.first, Answer2.second, vertNumFinal, 2);
	MyGraph(page_1_image, Answer3.first, Answer3.second, vertNumFinal, 3);
	cv::imshow("Page 1", page_1_image);

	//Output time taken (in seconds)
	t2 = clock();
	float diff((float)t2 - (float)t1);
	float seconds = diff / CLOCKS_PER_SEC;
	cout << endl << endl << "The code took " << seconds << " Seconds to run" << endl;
	cv::waitKey(0);

	return 0;
}