#include <iostream>
#include <fstream>
using namespace std;

int main()
{
	//open file to write results	
	ofstream myfile;
	myfile.open ("improvedtriangleinequality.txt");
	//setting up all subgraphs of K_5,5 with <=6-edges
	int B[77][5][5];
	for (int i=0; i<77; i++){
		for (int j=0; j<5; j++){
			for (int k = 0; k<5;k++){
				B[i][j][k]=0;
			}
		}
	}
	int num = 0;
	//case 0
	num++;
	//case 1
	B[num][0][0] = 1;
	num++;
	//case 2
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	num++;
	//case 3
	B[num][0][0] = 1;
	B[num][1][1] = 1;
	num++;
	//case 4
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	num++;
	//case 5
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	num++;
	//case 6
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][2] = 1;
	num++;
	//case 7
	B[num][0][0] = 1;
	B[num][1][1] = 1;
	B[num][2][2] = 1;
	num++;
	//case 8
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][0][3] = 1;
	num++;
	//case 9
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	num++;
	//case 10
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][3] = 1;
	num++;
	//case 11
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	B[num][1][1] = 1;
	num++;
	//case 12
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	B[num][1][2] = 1;
	num++;
	//case 13
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	B[num][2][2] = 1;
	num++;
	//case 14
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][2] = 1;
	B[num][1][3] = 1;
	num++;
	//case 15
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][2] = 1;
	B[num][2][2] = 1;
	num++;
	//case 16
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][2] = 1;
	B[num][2][3] = 1;
	num++;
	//case 17
	B[num][0][0] = 1;
	B[num][1][1] = 1;
	B[num][2][2] = 1;
	B[num][3][3] = 1;
	num++;
	//case 18
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][0][3] = 1;
	B[num][0][4] = 1;
	num++;
	//case 19
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][0][3] = 1;
	B[num][1][0] = 1;
	num++;
	//case 20
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][0][3] = 1;
	B[num][1][4] = 1;
	num++;
	//case 21
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][1][1] = 1;
	num++;
	//case 22
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][1][3] = 1;
	num++;
	//case 23
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][2][0] = 1;
	num++;
	//case 24
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][2][1] = 1;
	num++;
	//case 25
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][2][3] = 1;
	num++;
	//case 26
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][3] = 1;
	B[num][1][4] = 1;
	num++;
	//case 27
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][3] = 1;
	B[num][2][3] = 1;
	num++;
	//case 28
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][3] = 1;
	B[num][2][4] = 1;
	num++;
	//case 29
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	B[num][1][1] = 1;
	B[num][2][2] = 1;
	num++;
	//case 30
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	B[num][1][2] = 1;
	B[num][2][1] = 1;
	num++;
	//case 31
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	B[num][1][2] = 1;
	B[num][2][3] = 1;
	num++;
	//case 32
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	B[num][2][2] = 1;
	B[num][2][3] = 1;
	num++;
	//case 33
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	B[num][2][2] = 1;
	B[num][3][3] = 1;
	num++;
	//case 34
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][2] = 1;
	B[num][1][3] = 1;
	B[num][2][4] = 1;
	num++;
	//case 35
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][2] = 1;
	B[num][2][2] = 1;
	B[num][3][3] = 1;
	num++;
	//case 36
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][2] = 1;
	B[num][2][3] = 1;
	B[num][3][4] = 1;
	num++;
	//case 37
	B[num][0][0] = 1;
	B[num][1][1] = 1;
	B[num][2][2] = 1;
	B[num][3][3] = 1;
	B[num][4][4] = 1;
	num++;
	//case 38
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][0][3] = 1;
	B[num][0][4] = 1;
	B[num][1][0] = 1;
	num++;
	//case 39
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][0][3] = 1;
	B[num][1][0] = 1;
	B[num][1][1] = 1;
	num++;
	//case 40
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][0][3] = 1;
	B[num][1][0] = 1;
	B[num][1][4] = 1;
	num++;
	//case 41
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][0][3] = 1;
	B[num][1][0] = 1;
	B[num][2][0] = 1;
	num++;
	//case 42
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][0][3] = 1;
	B[num][1][0] = 1;
	B[num][2][1] = 1;
	num++;
	//case 43
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][0][3] = 1;
	B[num][1][0] = 1;
	B[num][2][4] = 1;
	num++;
	//case 44
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][0][3] = 1;
	B[num][1][4] = 1;
	B[num][2][4] = 1;
	num++;
	//case 45
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][1][1] = 1;
	B[num][1][2] = 1;
	num++;
	//case 46
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][1][1] = 1;
	B[num][1][3] = 1;
	num++;
	//case 47
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][1][1] = 1;
	B[num][2][0] = 1;
	num++;
	//case 48
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][1][1] = 1;
	B[num][2][2] = 1;
	num++;
	//case 49
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][1][1] = 1;
	B[num][2][3] = 1;
	num++;
	//case 50
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][1][3] = 1;
	B[num][1][4] = 1;
	num++;
	//case 51
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][1][3] = 1;
	B[num][2][0] = 1;
	num++;
	//case 52
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][1][3] = 1;
	B[num][2][1] = 1;
	num++;
	//case 53
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][1][3] = 1;
	B[num][2][3] = 1;
	num++;
	//case 54
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][1][3] = 1;
	B[num][2][4] = 1;
	num++;
	//case 55
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][2][0] = 1;
	B[num][3][3] = 1;
	num++;
	//case 56
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][2][1] = 1;
	B[num][3][2] = 1;
	num++;
	//case 57
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][2][1] = 1;
	B[num][3][3] = 1;
	num++;
	//case 58
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][2][3] = 1;
	B[num][2][4] = 1;
	num++;
	//case 59
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][2][3] = 1;
	B[num][3][3] = 1;
	num++;
	//case 60
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][0] = 1;
	B[num][2][3] = 1;
	B[num][3][4] = 1;
	num++;
	//case 61
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][3] = 1;
	B[num][1][4] = 1;
	B[num][2][3] = 1;
	num++;
	//case 62
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][3] = 1;
	B[num][2][3] = 1;
	B[num][3][3] = 1;
	num++;
	//case 63
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][0][2] = 1;
	B[num][1][3] = 1;
	B[num][2][3] = 1;
	B[num][3][4] = 1;
	num++;
	//case 64
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	B[num][1][1] = 1;
	B[num][2][2] = 1;
	B[num][2][3] = 1;
	num++;
	//case 65
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	B[num][1][1] = 1;
	B[num][2][2] = 1;
	B[num][3][3] = 1;
	num++;
	//case 66
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	B[num][1][2] = 1;
	B[num][2][1] = 1;
	B[num][2][2] = 1;
	num++;
	//case 67
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	B[num][1][2] = 1;
	B[num][2][1] = 1;
	B[num][2][3] = 1;
	num++;
	//case 68
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	B[num][1][2] = 1;
	B[num][2][1] = 1;
	B[num][3][3] = 1;
	num++;
	//case 69
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	B[num][1][2] = 1;
	B[num][2][3] = 1;
	B[num][2][4] = 1;
	num++;
	//case 70
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	B[num][1][2] = 1;
	B[num][2][3] = 1;
	B[num][3][3] = 1;
	num++;
	//case 71
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	B[num][1][2] = 1;
	B[num][2][3] = 1;
	B[num][3][4] = 1;
	num++;
	//case 72
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	B[num][2][2] = 1;
	B[num][2][3] = 1;
	B[num][3][2] = 1;
	num++;
	//case 73
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	B[num][2][2] = 1;
	B[num][2][3] = 1;
	B[num][3][4] = 1;
	num++;
	//case 74
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][0] = 1;
	B[num][2][2] = 1;
	B[num][3][3] = 1;
	B[num][4][4] = 1;
	num++;
	//case 75
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][2] = 1;
	B[num][1][3] = 1;
	B[num][2][4] = 1;
	B[num][3][4] = 1;
	num++;
	//case 76
	B[num][0][0] = 1;
	B[num][0][1] = 1;
	B[num][1][2] = 1;
	B[num][2][2] = 1;
	B[num][3][3] = 1;
	B[num][4][4] = 1;
	num++;
	//running over all <= 6-edges subgraphs of K_5,5
	for (int ex = 0; ex<77;ex++){	
		//setting up b_{u0}
		int bu[5][5];
		for (int i=0;i<5;i++){
			for (int j=0;j<5;j++){
				bu[i][j]=B[ex][i][j];
			}
		}
		//possible choices for other $b_{ui}$, $i>0$
		int A[512][5][5];
		int rownum = 0;
		for (int a=0; a<512; a++) {
			int c[10];
			int s = a;
			for(int k=0; k<10; k++){
				c[k]=0;
			}
			for(int i=0; s>0; i++)    {    
				c[i]=s%2;    
				s= s/2;  
			}
			for(int i=0; i<5; i++){
				for(int j=0;j<5;j++){
					A[rownum][i][j]= (c[i]+c[5+j]+bu[i][j])%2;
				}
			}
			rownum++;
		}
		//running over all possible b with b_{u0} given <=6-edges subgraph of K_5,5 with
		// |b|<=34 and |b_{u0}|=min_i |b_{ui}| finding worst ratio  
		// |b| / (sum_{uu'} |b_u+b_{u'}|) for all such b and writing it to output file
		double currentmax = 1.0;
		int currentnum = 1;
		int currentdenom = 1;
		//running over choices for b_ui, i>0
		for (int u=0; u<512; u++){
			for(int v=u; v<512; v++){
				for(int w=v; w<512; w++){
					for(int x=w;x<512;x++){
						//computing size of coboundary
						int sizecobound =0;
						int sumvert[5];
						for (int i =0; i<5;i++){
							sumvert[i] =0;
						}
						for(int i = 0; i<5;i++){
							for(int j =0;j<5;j++){
								sumvert[0] += bu[i][j];
								sumvert[1] += A[u][i][j];
								sumvert[2] += A[v][i][j];
								sumvert[3] += A[w][i][j];
								sumvert[4] += A[x][i][j];
							}
						}
						for(int i =0; i<5;i++){
							sizecobound+=sumvert[i];
						}
						//checking whether |b|<=34 and  |b_{u0}|=min_i |b_{ui}|  and b!=0
						if(sizecobound<= 34    && sumvert[0]<= sumvert[1] && sumvert[0]<=sumvert[2] && sumvert[0]<=sumvert[3] && sumvert[0]<=sumvert[4] && sizecobound>0){
							//computing sum_{uu'}|b_u+b_u'|
							int trianglepair =0;
							int cob[5][5][5];
							for (int i =0;i<5;i++){
								for(int j=0;j<5;j++){
									cob[0][i][j] = bu[i][j];
									cob[1][i][j] = A[u][i][j];
									cob[2][i][j] = A[v][i][j];
									cob[3][i][j] = A[w][i][j];
									cob[4][i][j] = A[x][i][j];
								}
							}
							for (int y=0;y<5;y++){
								for(int z=y+1;z<5;z++){
									for(int i=0;i<5;i++){
										for(int j=0;j<5;j++){
											trianglepair= trianglepair+(cob[y][i][j]+cob[z][i][j])%2+(cob[i][y][j]+cob[i][z][j])%2+(cob[i][j][y]+cob[i][j][z])%2;
										}
									}
								}
							}
							//checking whether we have worse ratio |b| / (sum_{uu'} |b_u+b_{u'}|) and update if necessary
							if (trianglepair*currentdenom>currentnum*sizecobound){
								currentmax = float(trianglepair)/float(sizecobound);
								currentnum = trianglepair;
								currentdenom = sizecobound;
							}
						}
					}
				}
			}
		}
	//write worst ratio for given subgraph of K_5,5 to file
	myfile << "Upper bound for case " <<  ex  << " is: " << currentmax << " with numerator " << currentnum << " and denominator " << currentdenom << endl;
	}
	cout << "Done!" << endl;
	myfile.close();
}