```
#include "global.h"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm> //define random_shuffle, copy
using namespace std;
int generateG1(std::vector<std::vector<int> >& G1R, std::vector<std::vector<int> >& netConnectionsR, std::vector<int>& netConnectionsFilledColR, std::vector<int>& parta, std::vector<int>& partb, std::vector<int>& unlockeda, std::vector<int>& unlockedb, int& node2swapX, int& node2swapY)
{
int N = pad_offset+1; //set N to number of total nodes
int extraN = 4; //how many extra columns added to G1
int G1_Init = -1; //initial values for G1 vector
int node = 0, connectingNode = 0;
int k = 0;
int cutsize = 0;
bool inA = false, inB = false;
bool firstTime = false; //set firstTime to false. If G1 was not resized this time, it will be set to true.
if(N % 2) //if N is odd (true), dummy row was added during parseFile
N += 1; //account for additional dummy row, N should be even always
if(int(G1R.size()) != N) //if G1R is not N x something, then do initial resize
{
G1R.resize(N, vector<int>(N, G1_Init)); //resize G1 to create a N x N matrix with G1_Init
for(int i = 0; i < N; i++)
{
G1R[i].resize(N+extraN, 0); //resize G1 to create a N x N+extraN matrix with zeros
}
firstTime = true;
}
if(firstTime != true)
{
//cout << "in G1 node: " << node2swapX << "goes to partB now" << endl;
//cout << "in G1 node: " << node2swapY << "goes to partA now" << endl;
for(int i = 0; i <= 1; i++)
{
switch(i){ //select node2swapX or node2swapX depending on i
case 0:
node = node2swapX; //set node to node2swapX
G1R[node][N] = 2; //set that this node is going to partB, so make x(1) to y(2)
break;
case 1:
node = node2swapY; //set node to node2swapY
G1R[node][N] = 1; //set that this node is going to partB, so make y(2) to x(1)
break;
default:
break;
}//switch
for(int j = 0; j < (netConnectionsFilledColR[node]); j++) //cycle through all the connections to node2swap
{
connectingNode = netConnectionsR[node][j]; //save connected node of node2swapX
switch(G1R[node][connectingNode]){ //rows of swap have x's switched to y's and vice versa
case 11:
G1R[node][connectingNode] = 12; //was Ax, now is Ay
cutsize++;
break;
case 12:
G1R[node][connectingNode] = 11; //was Ay, now is Ax
break;
case 21:
G1R[node][connectingNode] = 22; //was Bx, now is By
break;
case 22:
G1R[node][connectingNode] = 21; //was By, now is Bx
break;
default:
break;
}//switch
switch(G1R[connectingNode][node]){ //columns of swap have x's switched to y's and vice versa
case 11:
G1R[connectingNode][node] = 21; //was Ax, now is Bx
G1R[connectingNode][N+1] -= 1; //subtract one A
G1R[connectingNode][N+2] += 1; //plus one B
break;
case 12:
G1R[connectingNode][node] = 22; //was Ay, now is By
G1R[connectingNode][N+1] -= 1; //subtract one A
G1R[connectingNode][N+2] += 1; //plus one B
break;
case 21:
G1R[connectingNode][node] = 11; //was Bx, now is Ax
G1R[connectingNode][N+1] += 1; //plus one A
G1R[connectingNode][N+2] -= 1; //subtract one B
break;
case 22:
G1R[connectingNode][node] = 12; //was By, now is Ay
G1R[connectingNode][N+1] += 1; //plus one A
G1R[connectingNode][N+2] -= 1; //subtract one B
break;
default:
break;
}//switch
}//cycle through all the connections to node2swap
}//end for node2swap
//find gain
for(int i = 0; i < N; i++)
{
if(G1R[i][N] == 1) //check if at position N, it is 1(x) or 2(y)
G1R[i][N+3] = G1R[i][N+2] - G1R[i][N+1]; //Since this row is marked as 1(Zx), do counts(B - A) = G
else
G1R[i][N+3] = G1R[i][N+1] - G1R[i][N+2]; //Since this row is marked as 2(Zy), do counts(A - B) = G
}//for find gain
for(int i = 0; i < N/2; i++) //go through partA, looking for node2swapX
{
if(parta[i] == node2swapX) //when node2swapX is found in partA
{
parta.erase(parta.begin() + i); //remove node2swapX
unlockeda.erase(unlockeda.begin() + i); //remove node2swapX and lock away
partb.push_back(node2swapX); //push node2swapX onto partB
break;
}
}
for(int i = 0; i < int(partb.size()); i++) //go through partB, looking for node2swapY
{
if(partb[i] == node2swapY) //when node2swapY is found in partB
{
partb.erase(partb.begin() + i); //remove node2swapY
unlockedb.erase(unlockedb.begin() + i); //remove node2swapY and lock away
parta.push_back(node2swapY); //push node2swapY onto partA
break;
}
}
/*cout << "after swap unlocked nodes are" << endl;
for(std::vector<int>::iterator it = unlockeda.begin(); it!=unlockeda.end(); ++it)
cout << ' ' << *it;
cout << '\n' ;
for(std::vector<int>::iterator it = unlockedb.begin(); it!=unlockedb.end(); ++it)
cout << ' ' << *it;
cout << '\n' ;
*/
}//if not firstTime
else //else firstTime != false, meaning it is the first time
{
for(int i = 0; i < N/2; i++) //cycle through partA
{
node = parta[i]; //select node in partA
for(int j = 0; j < (netConnectionsFilledColR[node]); j++) //cycle through all the connections to node
{
//cout << "netConnectionsFilledCol: " << netConnectionsFilledColR[node] << endl;
k = 0;
while(k < N/2 && inA == false && inB == false) //look for sink node in partA and partB
{
if(parta[k] == netConnectionsR[node][j]) //sink node in partA, so mark as 11(Ax)
{
inA = true; //found sink node in partA
connectingNode = netConnectionsR[node][j]; //save sink node
//cout << "inA: " << inA << endl;
//cout << "partAk: " << parta[k] << endl;
//cout << "netConnections: " << netConnectionsR[node][j] << endl;
}
if(partb[k] == netConnectionsR[node][j]) //sink node in partB, so mark as 21(Bx)
{
inB = true; //found sink node in partB
connectingNode = netConnectionsR[node][j]; //save sink node
//cout << "inB: " << inB << endl;
//cout << "partBk: " << partb[k] << endl;
//cout << "netConnections: " << netConnectionsR[node][j] << endl;
}
k++; //increment to next node in partitions, until N/2
}
if(inA == true) //in partA
{
G1R[node][connectingNode] = 11; //set G1R to 11(Ax), (sink in A, source in A)
G1R[connectingNode][node] = 11; //set G1R to 11(Ax), (sink in A, source in A), transpose nodes
G1R[node][N+1] += 1; //save count of A's in N of the row for the node
//don't count G1R[connectingNode][N] += 1, causes overcount
G1R[node][N] = 1; //set that this node is in partA, 1(Zx)
//cout << "G1: " << G1R[node][connectingNode] << endl;
inA = false;
}
if(inB == true) //in partB
{
G1R[node][connectingNode] = 21; //set G1R to 21(Bx), (sink in B, source in A)
G1R[connectingNode][node] = 12; //set G1R to 12(Ay), (sink in A, source in B), transpose nodes
G1R[node][N+2] += 1; //save count of B's in N of the row for the node
G1R[connectingNode][N+1] += 1; //save count of A's in N of the row for the connectingNode
G1R[node][N] = 1; //set that this node is in partA, 1(Zx)
G1R[connectingNode][N] = 2; //set that this node is in partB, 2(Zy)
cutsize++; //cutsize adds by one for each pair of Ay, Bx pairs
//cout << "G1: " << G1R[node][connectingNode] << endl;
inB = false;
}
}//cycle through all the connections to node
}//cycle through partA
/* Since the last section found three out of 4 possible combinations of source and sink nodes in the partitions, */
/* we can only look at partition B now, and just check if the sink nodes exist in B and mark accordingly. */
for(int i = 0; i < N/2; i++) //cycle through partB
{
node = partb[i]; //select node in partB
for(int j = 0; j < (netConnectionsFilledColR[node]); j++) //cycle through all the connections to node
{
//cout << "netConnectionsFilledCol: " << netConnectionsFilledColR[node] << endl;
k = 0;
while(k < N/2 && inA == false && inB == false) //look for sink node in partB
{
if(partb[k] == netConnectionsR[node][j]) //sink node in partB, so mark as 22(By)
{
inB = true; //found sink node in partB
connectingNode = netConnectionsR[node][j]; //save sink node
//cout << "inB: " << inB << endl;
//cout << "partBk: " << partb[k] << endl;
//cout << "netConnections: " << netConnectionsR[node][j] << endl;
}
k++; //increment to next node in partitions, until N/2
}
if(inB == true) //in partB
{
G1R[node][connectingNode] = 22; //set G1R to 22(By), (sink in B, source in B)
G1R[connectingNode][node] = 22; //set G1R to 22(By), (sink in B, source in B), transpose nodes
G1R[node][N+2] += 1; //save count of B's in N+1 of the row for the node
//don't count G1R[connectingNode][N+1] += 1, causes overcount
G1R[node][N] = 2; //set that this node is in partA, 2(Zy)
//cout << "G1: " << G1R[node][connectingNode] << endl;
inB = false;
}
}//cycle through all the connections to node
}//cycle through partB
//find gain
for(int i = 0; i < N; i++)
{
if(G1R[i][N] == 1)
G1R[i][N+3] = G1R[i][N+2] - G1R[i][N+1]; //Since this row is marked as 1(Zx), do counts(B - A) = G
else
G1R[i][N+3] = G1R[i][N+1] - G1R[i][N+2]; //Since this row is marked as 2(Zy), do counts(A - B) = G
}
}//end else firstTime != false, meaning it is the first time
//print out G1
/*for(int m = 0 ; m < N; m++) //rows
{
cout << m << ": ";
for(int n = 0; n < N+extraN; n++) //columns
{
cout << G1R[m][n] << " ";
}
cout << "" << endl;
}*/
//cout << "Cutsize: " << cutsize << endl;
return cutsize;
}
```