#define uint unsigned int

// hypergraph point
#define HPNT char

// Standard IO
#include <iostream>

// File IO
#include <fstream>

#include <set>
#include <vector>

#include <math.h>

using namespace std;

// Increments the row so that it's the next-highest (in sorted order) possible
// row. Returns false if the row is already the highest possible row.
bool incrementRow(vector<HPNT>& row);

// Whether every point in the hypergraph has a line through it.
bool allPointsCovered(vector<uint>& hypergraph);

// Whether the current graph is new compared to already-encountered graphs. If
// it is, outputs its symmetry matrix and each point's symmetry.
bool newGraph(
		vector                     <uint>      & hypergraph,
		vector<vector              <uint> >    & savedGraphs,
		vector<vector<vector<vector<HPNT> > > >& savedSymmetries,
		vector<vector              <HPNT> >    & savedPtsToSymms,
		vector<vector<vector       <HPNT> > >  & outSymmetryMatrix,
		vector                     <HPNT>      & outPtsToSymms,
		bool debug);

// Whether two graphs are identical, given that they have the same symmetry
// matrix. Permutes hypergraph1's points within its symmetries and checks each
// permutated hypergraph for identity with the other graph. Takes each graph's
// ptsToSymms vector and the symmetry matrix that both graphs have.
bool identicalGraphs(
		vector              <uint>    & hypergraph1,
		vector              <uint>    & hypergraph2,
        vector<vector<vector<HPNT> > >& symmetryMatrix,
        vector              <HPNT>    & ptsToSymms1,
        vector              <HPNT>    & ptsToSymms2,
        bool debug);

// Calculates n!.
uint factorial(uint n);

// Permutes a symmetry group one iteration within an existing permutation of an
// entire list of points. Uses the fact that the least permutation is just the
// index of each point (i.e. the identity permutation), so the least permutation
// of each group has its points sorted. Only currPerm is modified.
void permuteSymmGroup(vector<HPNT>& currPerm, vector<HPNT>& currSymmGroup);

// Tests a permutation of hypergraph1 for equality with hypergraph2 given a map
// from points in hypergraph1 to points in hypergraph2.
bool testEquality(
		vector<uint>& hypergraph1,
		vector<uint>& hypergraph2,
		vector<HPNT>& currPerm,
		vector<HPNT>& pointsToPoints);

// The symmetry matrix of a graph is a vector of vectors; each vector represents
// a symmetry class (a type of point); the point's index is the size of the
// vector divided by two. Also returns each point's corresponding symmetry.
void getSymmetryMatrix(
		vector              <uint>    & hypergraph,
		vector<vector<vector<HPNT> > >& outMatrix,
		vector              <HPNT>    & outPtsToSymms,
		bool debug);

// A recursive function used in getSymmetryMatrix. Transforms symmetryMatrix
// into its next iteration. pointsToSymmetries is the symmetry vector (in
// symmetryMatrix) that each point has. pointAdjacencies is the other points
// that each point is adjacent to, in groups of two (one pair for each line
// through the point).
void getSymmetryMatrixIter(
		vector              <HPNT>    & ptsToSymms,
		vector<vector<vector<HPNT> > >& pointAdjacencies,
		vector<vector<vector<HPNT> > >& symmetryMatrix,
		bool debug);

// Inserts a line's symmetry matrix into a hypergraph symmetry matrix so that
// the hypergraph matrix is sorted. Does not insert already-existing line
// matrices.  Returns the index of the inserted or preexisting line matrix in
// the graph matrix.
uint addToSymmetryMatrix(
		vector<vector<vector<HPNT> > >& symmetryMatrix,
		vector<vector       <HPNT> >  & symmetry);

// Compares the first symmetry line matrix to the second.
// -1: less, 0: equal, 1: greater.
int compareSymmetryVectors(
		vector<vector<HPNT> >& symmetry1,
		vector<vector<HPNT> >& symmetry2);

// Outputs the given hypergraph's index in the graph array along with some
// conditions on it. Also modifies a vector of counts of conditions.
bool outputGraph(vector<uint>& hypergraph, uint i, vector<uint>& counts);

// Whether a hypergraph is Gieseker-stable. Returns -1 for unstable, 0 for
// semistable, and 1 for stable.
int stableGraph(vector<uint>& hypergraph, vector<vector<bool> >& boolGraph);

// Converts a given hypergraph to a boolean matrix.
void booleanize(vector<uint>& hypergraph, vector<vector<bool> >& outGraph);

// Gets n(Y), where Y is some subgraph of the original X.
int getGiesekerN(vector<vector<bool> >& hypergraph, vector<bool>& subgraph,
                 HPNT origNumLines);

// Gets m(Y), where Y is some subgraph of the original X.
int getGiesekerM(vector<vector<bool> >& hypergraph, vector<bool>& subgraph,
                 HPNT origNumLines);

// Gets p(Y IN X\Y).
int getGiesekerP(vector<vector<bool> >& hypergraph, vector<bool>& subgraph);

// Returns whether the given graph is weak.
bool weakGraph(vector<uint>& hypergraph);

// Returns whether the given weak graph is strong by checking for weak
// subgraphs.
bool strongGraph(vector<uint>& hypergraph);

// Produces all of the F transformations of a given hypergraph. Outputs the
// results as boolean matrices.
//void transformF(vector<vector<bool> >& hypergraph,
//                vector<vector<vector<bool> > >& outGraphs);
//
// Produces all of the G transformations of a given hypergraph.
//void transformG(vector<vector<bool> >& hypergraph,
//                vector<vector<vector<bool> > >& outGraphs);

// Whether a hypergraph can be drawn on a plane.
bool planarGraph(vector<vector<bool> >& hypergraph);

// The index of the highest-index point on the hypergraph.
uint graphIndex(vector<vector<bool> >& hypergraph);

// Whether the hypergraph has any points of index 1.
bool hasLoosePoints(vector<vector<bool> >& hypergraph);

// The effective "size" of the hypergraph, i.e. the number of lines, with each
// extra point (past 3) counting as an extra line.
uint graphSize(vector<uint>& hypergraph);

// The number of points.
HPNT n;

// Stores every possible row in sorted order as a vector of three or more
// points (in order).
vector<vector<HPNT> > possibleRows;

int main(int argc, const char* argv[])
{
	// Opens and closes the output file to clear it.
	ofstream outFile("hypergraphs.txt");
	if (!outFile.is_open())
	{
		cerr << "Error opening output file." << endl;
		return 0;
	}
	outFile.close();

	if (argc != 2)
	{
		cout << "Please enter one argument for n." << endl;
		return 0;
	}

	n = char(atoi(argv[1]));
	if (n < 4)
	{
		cout << "Error: n must be at least 4." << endl;
		return 0;
	}

	vector<vector              <uint> >     oldGraphs;

	vector                     <uint>       currGraph;
	vector<vector<vector       <HPNT> > >   currSymmMatrix;
	vector                     <HPNT>       currPtsToSymms;

	vector<vector              <uint> >     newGraphs;
	vector<vector<vector<vector<HPNT> > > > newSymms;
	vector<vector              <HPNT> >     newPtsToSymms;

	vector<vector              <uint> >     outGraphs;
	vector<vector<vector<vector<HPNT> > > > outSymms;
	vector<vector              <HPNT> >     outPtsToSymms;

	// The least possible row.
	vector<HPNT> leastRow;
	leastRow.push_back(0);
	leastRow.push_back(1);
	leastRow.push_back(2);

	// All possible rows in order.
	vector<HPNT> currRow = leastRow;
	possibleRows.push_back(currRow);
	while (incrementRow(currRow))
	{
		possibleRows.push_back(currRow);
	}
	cout << "Number of possible rows: " << possibleRows.size() << endl;

	vector<uint> graphTypeCounts;
	for (uint i = 0; i < 9; i++)
	{
		graphTypeCounts.push_back(0);
	}

	bool outputSuccess;

	HPNT totalSize;

	uint counter = 0;

	HPNT lineSize;
	HPNT numLoosePts;
	bool skipGraph;
	vector<vector<bool> > boolGraph;

	for (HPNT currLine = 0; currLine < n - 2; currLine++)
	{
		for (uint currLineVal = 0; currLineVal < possibleRows.size();
		     currLineVal++)
		{
			if (oldGraphs.size() > 0)
			{
				for (uint currOldGraph = 0; currOldGraph < oldGraphs.size();
				     currOldGraph++)
				{
					currGraph = oldGraphs[currOldGraph];

					// The combined size of the current graph and the line
					// being considered is too high; skip it.
					totalSize = graphSize(currGraph) +
					            possibleRows[currLineVal].size() - 2;
					if (totalSize > n - 2)
					{
						continue;
					}

					currGraph.push_back(currLineVal);

					if (totalSize == n - 2)
					{
						// The graph is complete but misses some point; skip it.
						if (!allPointsCovered(currGraph))
						{
							continue;
						}

						// The graph is complete; add it to the output list.
						counter++;

						// Checks whether the graph a) has a loose point on a
						// triple where it is the only loose point, or b) has
						// a loose point on a higher-index line. If either of
						// these is true, the graph is skipped, because the
						// triple in (a) or the point in (b) can be removed,
						// preserving weakness and planarity.
						skipGraph = false;
						booleanize(currGraph, boolGraph);
						for (HPNT l1 = 0; l1 < (HPNT)boolGraph.size(); l1++)
						{
							lineSize = 0;
							for (HPNT pt = 0; pt < n; pt++)
							{
								if (boolGraph[l1][pt])
								{
									lineSize++;
								}
							}

							// Counts how many points on the line are loose.
							numLoosePts = lineSize;
							for (HPNT pt = 0; pt < n; pt++)
							{
								if (boolGraph[l1][pt])
								{
									for (HPNT l2 = 0;
									     l2 < (HPNT)boolGraph.size(); l2++)
									{
										if ((l1 != l2) && boolGraph[l2][pt])
										{
											numLoosePts--;
											break;
										}
									}
								}
							}
							if ((lineSize == 3 && numLoosePts == 1) ||
							    (lineSize == 3 && numLoosePts == 2) ||
								(lineSize >  3 && numLoosePts >= 1))
							{
								skipGraph = true;
								break;
							}
						}
						if (skipGraph)
						{
							continue;
						}

						if (newGraph(currGraph, outGraphs, outSymms,
						             outPtsToSymms, currSymmMatrix,
						             currPtsToSymms, false))
						{
							outGraphs    .push_back(currGraph);
							outSymms     .push_back(currSymmMatrix);
							outPtsToSymms.push_back(currPtsToSymms);

							outputSuccess = outputGraph(
									currGraph, outSymms.size() - 1,
									graphTypeCounts);
							if (!outputSuccess)
							{
								cerr << "Error in outputGraph: false returned"
								     << endl;

								return 0;
							}
						}
					}
					else
					{
						// The graph is incomplete; add it to the recursion
						// list.
						counter++;

						if (newGraph(currGraph, newGraphs, newSymms,
						             newPtsToSymms, currSymmMatrix,
						             currPtsToSymms, false))
						{
							newGraphs    .push_back(currGraph);
							newSymms     .push_back(currSymmMatrix);
							newPtsToSymms.push_back(currPtsToSymms);
						}
					}
				}
			}
			else
			{
				currGraph.clear();
				currGraph.push_back(currLineVal);
				if ((HPNT)possibleRows[currLineVal].size() == n)
				{
/*					// The graph is complete (it is a single line covering every
					// point); add it to the output list.
					counter++;
					if (newGraph(currGraph, outGraphs, outSymms,
								 outPtsToSymms, currSymmMatrix,
								 currPtsToSymms, false))
					{
						outGraphs    .push_back(currGraph);
						outSymms     .push_back(currSymmMatrix);
						outPtsToSymms.push_back(currPtsToSymms);

						outputSuccess = outputGraph(
								currGraph, outSymms.size() - 1,
								graphTypeCounts);
						if (!outputSuccess)
						{
							cerr << "Error in outputGraph: false returned"
								 << endl;

							return 0;
						}
					}
*/				}
				else
				{
					// The graph is incomplete; add it to the recursion
					// list.
					counter++;
					if (newGraph(currGraph, newGraphs, newSymms,
								 newPtsToSymms, currSymmMatrix,
								 currPtsToSymms, false))
					{
						newGraphs    .push_back(currGraph);
						newSymms     .push_back(currSymmMatrix);
						newPtsToSymms.push_back(currPtsToSymms);
					}
				}
			}
		}
		oldGraphs = newGraphs;
		newGraphs.clear();
		newSymms.clear();
		newPtsToSymms.clear();
	}

	cout << "Number of hypergraphs: " << outGraphs.size()  << endl
	     << "Nonweak unstable:   " << graphTypeCounts[0]   << endl
	     << "Nonweak semistable: " << graphTypeCounts[1]   << endl
	     << "Nonweak stable:     " << graphTypeCounts[2]   << endl
	     << "Weak unstable:      " << graphTypeCounts[3]   << endl
	     << "Weak semistable:    " << graphTypeCounts[4]   << endl
	     << "Weak stable:        " << graphTypeCounts[5]   << endl
	     << "Strong unstable:    " << graphTypeCounts[6]   << endl
	     << "Strong semistable:  " << graphTypeCounts[7]   << endl
	     << "Strong stable:      " << graphTypeCounts[8]   << endl
	     << "Number of times newGraph called: " << counter << endl;
/*
	for (uint i = 0; i < outGraphs.size(); i++)
	{
		cerr << i << endl;
		cerr << "pts to symms" << endl;
		for (uint j = 0; j < outPtsToSymms[i].size(); j++)
		{
			cerr << (uint)outPtsToSymms[i][j] << " ";
		}
		cerr << endl;
		cerr << "symmMatrix" << endl;
		for (uint j = 0; j < outSymms[i].size(); j++)
		{
			for (uint k = 0; k < outSymms[i][j].size(); k++)
			{
				for (uint l = 0; l < outSymms[i][j][k].size(); l++)
				{
					cerr << (uint)outSymms[i][j][k][l] << " ";
				}
				cerr << " endline" << endl;
			}
			cerr << " endsymm" << endl;
		}
		cerr << endl;
	}
*/
	return 0;
}

bool incrementRow(vector<HPNT>& row)
{
	// Tests whether the row is at its maximum value. If it is, increment its
	// size (if possible).
	bool maxRow = true;
	for (HPNT i = 0; i < (HPNT)row.size(); i++)
	{
		if (row[i] != n + i - (HPNT)row.size())
		{
			maxRow = false;
			break;
		}
	}
	if (maxRow)
	{
		if ((HPNT)row.size() == n)
		{
			return false;
		}
		for (HPNT i = 0; i < (HPNT)row.size(); i++)
		{
			row[i] = i;
		}
		row.push_back(row.size());
		return true;
	}

	// The row is not at its maximum, so increment it. We do this by finding the
	// highest indexed point in the row that does not have the point immediately
	// after it also in the row, and choosing the sequence of points just after
	// it. For example, if the row was originally 100101, then index 3 is chosen
	// and the new row is 100011.
	HPNT pointToIncrement;
	for (int i = int(row.size()) - 1; i >= 0; i--)
	{
		if (row[i] != n + i - (HPNT)row.size())
		{
			pointToIncrement = row[i];
			for (HPNT j = i; j < (HPNT)row.size(); j++)
			{
				row[j] = pointToIncrement + 1 + (j - i);
			}
			return true;
		}
	}

	cerr << "Error: incrementRow reached end of function." << endl;
	return false;
}

bool allPointsCovered(vector<uint>& hypergraph)
{
	bool currPointCovered;
	for (HPNT currPoint = 0; currPoint < n; currPoint++)
	{
		currPointCovered = false;
		for (HPNT currLine = 0;
		     (currLine < (HPNT)hypergraph.size()) && !currPointCovered;
		     currLine++)
		{
			for (HPNT i = 0;
			     (i < (HPNT)possibleRows[hypergraph[currLine]].size()) &&
			      !currPointCovered; i++)
			{
				if (possibleRows[hypergraph[currLine]][i] == currPoint)
				{
					currPointCovered = true;
				}
			}
		}
		if (!currPointCovered)
		{
			return false;
		}
	}
	return true;
}

bool newGraph(
		vector                     <uint>      & hypergraph,
		vector<vector              <uint> >    & savedGraphs,
		vector<vector<vector<vector<HPNT> > > >& savedSymmetries,
		vector<vector              <HPNT> >    & savedPtsToSymms,
		vector<vector<vector       <HPNT> > >  & outSymmetryMatrix,
		vector                     <HPNT>      & outPtsToSymms,
		bool debug)
{
	// Checks whether the hypergraph has lines l1 and l2 which intersect at two
	// points, and one is not contained in the other. If this is the case, the
	// graph is ignored, since it can be transformed into an equivalent graph
	// which does not have this condition.
	uint numSharedPts;
	for (int l1 = 0; l1 < int(hypergraph.size()) - 1; l1++)
	{
		for (int l2 = l1; l2 < int(hypergraph.size()); l2++)
		{
			// Counts the shared points.
			numSharedPts = 0;
			for (HPNT p1 = 0; p1 < (HPNT)possibleRows[hypergraph[l1]].size();
			     p1++)
			{
				for (HPNT p2 = 0;
				     p2 < (HPNT)possibleRows[hypergraph[l2]].size(); p2++)
				{
					if (possibleRows[hypergraph[l1]][p1] ==
					    possibleRows[hypergraph[l2]][p2])
					{
						numSharedPts++;
					}
				}
			}

			if (numSharedPts < 2)
			{
				continue;
			}
			// The lines share at least two points.

			if (possibleRows[l1].size() == numSharedPts ||
			    possibleRows[l2].size() == numSharedPts)
			{
				continue;
			}
			// Neither line contains the other.

			return false;
		}
	}

	getSymmetryMatrix(hypergraph, outSymmetryMatrix, outPtsToSymms, debug);

	// Check the existing graphs for matching symmetries.
	for (uint i = 0; i < savedSymmetries.size(); i++)
	{
		if (outSymmetryMatrix == savedSymmetries[i])
		{
			if (debug)
			{
				cerr << "identical symmetry matrices" << endl;
			}
			// For each existing graph with an identical symmetry matrix,
			// permute the points (within their symmetries) to check whether
			// the matrices are identical.
			if(identicalGraphs(hypergraph, savedGraphs[i], outSymmetryMatrix,
					           outPtsToSymms, savedPtsToSymms[i], debug))
			{
				if (debug)
				{
					cerr << "different graphs" << endl;
				}
				return false;
			}
		}
	}

	if (debug)
	{
		cerr << "hypergraph" << endl;
		for (uint i = 0; i < hypergraph.size(); i++)
		{
			for (uint j = 0; j < possibleRows[hypergraph[i]].size(); j++)
			{
				cerr << (uint)possibleRows[hypergraph[i]][j] << " ";
			}
			cerr << endl;
		}
		cerr << endl;

		cerr << "num symms " << outSymmetryMatrix.size() << endl;

		cerr << "symmetry matrix" << endl;
		for (uint i = 0; i < outSymmetryMatrix.size(); i++)
		{
			cerr << "symm" << i << " ";
			for (uint j = 0; j < outSymmetryMatrix[i].size(); j++)
			{
				for (uint k = 0; k < outSymmetryMatrix[i][j].size(); k++)
				{
					cerr << (uint)outSymmetryMatrix[i][j][k] << " ";
				}
				cerr << endl;
			}
			cerr << endl;
		}
		cerr << endl;

		cerr << "ptsToSymms" << endl;
		for (uint i = 0; i < outPtsToSymms.size(); i++)
		{
			cerr << (uint)outPtsToSymms[i] << " ";
		}
		cerr << endl;
	}

	return true;
}

bool identicalGraphs(
		vector              <uint>    & hypergraph1,
		vector              <uint>    & hypergraph2,
        vector<vector<vector<HPNT> > >& symmetryMatrix,
        vector              <HPNT>    & ptsToSymms1,
        vector              <HPNT>    & ptsToSymms2,
        bool debug)
{
	// For each symmetry number, this contains the points in hypergraph1 or
	// hypergraph2 that have that symmetry, in order.
	vector<vector<HPNT> > symmGroups1, symmGroups2;

	vector<HPNT> emptyVector;

	// Finds the maximum numbered symmetry (the symmetries are numbered 0
	// through this number).
	HPNT maxSymmNum = 0;
	HPNT currSymmNum;
	for (uint currPoint = 0; currPoint < ptsToSymms1.size(); currPoint++)
	{
		currSymmNum = ptsToSymms1[currPoint];
		if (currSymmNum > maxSymmNum)
		{
			maxSymmNum = currSymmNum;
		}
	}

	// Initializes the vectors in symmGroups.
	for (HPNT i = 0; i <= maxSymmNum; i++)
	{
		symmGroups1.push_back(emptyVector);
		symmGroups2.push_back(emptyVector);
	}

	// Populates symmGroups.
	for (uint i = 0; i < ptsToSymms1.size(); i++)
	{
		symmGroups1[ptsToSymms1[i]].push_back(i);
		symmGroups2[ptsToSymms2[i]].push_back(i);
	}

	// pointsToPoints maps the points in hypergraph1 to those in hypergraph2 so
	// that symmetries are preserved.
	vector<HPNT> pointsToPoints;
	for (uint i = 0; i < ptsToSymms1.size(); i++)
	{
		pointsToPoints.push_back(0);
	}

	// Populates pointsToPoints.
	for (uint currGroup = 0; currGroup < symmGroups1.size(); currGroup++)
	{
		for (uint i = 0; i < symmGroups1[currGroup].size(); i++)
		{
			pointsToPoints[symmGroups1[currGroup][i]]
					= symmGroups2[currGroup][i];
		}
	}

	// The current permutation applied to hypergraph1. Maps each point to the
	// point it's permuted to.
	vector<HPNT> currPerm;

	vector<HPNT> identityPerm;
	for (uint i = 0; i < ptsToSymms1.size(); i++)
	{
		identityPerm.push_back(i);
	}

	currPerm = identityPerm;

	// The current permutation being applied to each symmetry group. All 0s is
	// the identity permutation. The permutations are in lexical order (when the
	// identity is numbered by counting) from 0 to k!-1, where k is the size of
	// the given symmetry group.
	vector<uint> symmPermNums;
	vector<uint> minPermNums;
	for (uint i = 0; i < symmGroups1.size(); i++)
	{
		minPermNums.push_back(0);
	}
	symmPermNums = minPermNums;
	uint currSymmPermNum;

	// The maximum value of each entry in symmPermNums, i.e. just k!-1 for that
	// group's value of k.
	vector<uint> maxPermNums;
	for (uint i = 0; i < symmGroups1.size(); i++)
	{
		maxPermNums.push_back(factorial(symmGroups1[i].size()) - 1);
	}

	// Tests the identity permutation.
	if (testEquality(hypergraph1, hypergraph2, currPerm, pointsToPoints))
	{
		return true;
	}

	if (debug)
	{
		cerr << "symmGroups1: " << endl;
		for (uint i = 0; i < symmGroups1.size(); i++)
		{
			for (uint j = 0; j < symmGroups1[i].size(); j++)
			{
				cerr << symmGroups1[i][j] << " ";
			}
			cerr << endl;
		}
		cerr << endl;
	}

	// Emulates a nested series of 'for' loops where each loop corresponds to a
	// symmetry group and iterates through all of its permutations. The
	// innermost loop corresponds to symmetry group 0.
	do {
		for (uint currSymmGroup = 0; currSymmGroup < symmGroups1.size();
		     currSymmGroup++)
		{
			if (debug)
			{
				cerr << "currSymmGroup: " << currSymmGroup << endl;
			}
			// Tests whether current group is ready for permutation.
			currSymmPermNum = symmPermNums[currSymmGroup];
			if (currSymmPermNum < maxPermNums[currSymmGroup])
			{
				if (debug)
				{
					cerr << "permuting group " << currSymmGroup << ": ";
					for (uint i = 0; i < currPerm.size(); i++)
					{
						cerr << currPerm[i] << " ";
					}
					cerr << endl;

					cerr << "symmPermNums: ";
					for (uint i = 0; i < symmPermNums.size(); i++)
					{
						cerr << symmPermNums[i] << " ";
					}
					cerr << endl;
				}

				// This group is being permuted; increment its permutation
				// number.
				symmPermNums[currSymmGroup]++;

				if (debug)
				{
					cerr << "symmPermNums: ";
					for (uint i = 0; i < symmPermNums.size(); i++)
					{
						cerr << symmPermNums[i] << " ";
					}
					cerr << endl;
				}

				// Permutes currSymmGroup one iteration within currPerm.
				permuteSymmGroup(currPerm, symmGroups1[currSymmGroup]);

				// Tests hypergraph1's current permutation for equality with
				// hypergraph2.
				if (testEquality(hypergraph1, hypergraph2, currPerm,
				                 pointsToPoints))
				{
					if (debug)
					{
						cerr << "returning true" << endl;
					}
					return true;
				}

				// We have successfully permuted, so continue to the next
				// permutation. This is unreachable when symmPermNums is equal
				// to maxPermNums, but that leads to the end case.
				break;
			}
			else
			{
				// This group is at its maximum permutation number; go to the
				// next group and reset this group's permutation number.
				symmPermNums[currSymmGroup] = 0;

				// Also reset this group's permutation.
				for (uint i = 0; i < symmGroups1[currSymmGroup].size(); i++)
				{
					currPerm[symmGroups1[currSymmGroup][i]]
					       = symmGroups1[currSymmGroup][i];
				}
			}
		}
	} while (symmPermNums != minPermNums);

	return false;
}

uint factorial(uint k)
{
	if (k == 0)
	{
		return 1;
	}

	uint retVal = 1;
	for (uint i = 1; i <= k; i++)
	{
		retVal *= i;
	}

	return retVal;
}

void permuteSymmGroup(vector<HPNT>& currPerm, vector<HPNT>& currSymmGroup)
{
	uint groupSize = currSymmGroup.size();

	if (groupSize == 0)
	{
		return;
	}

	HPNT mirrorIndex;
	HPNT temp;
	bool swapped;
	bool permuted = false;

	for (uint i = groupSize - 1; i > 0; i--)
	{
		// The permutation occurs at the first instance of a point being greater
		// than its preceding point, from the right.
		if (currPerm[currSymmGroup[i]] > currPerm[currSymmGroup[i-1]])
		{
			// Swaps i-1 with the least point greater than it.
			swapped = false;
			for (uint j = groupSize - 1; j >= i; j--)
			{
				if (currPerm[currSymmGroup[j]] > currPerm[currSymmGroup[i-1]])
				{
					temp = currPerm[currSymmGroup[j]];
					currPerm[currSymmGroup[j]] = currPerm[currSymmGroup[i-1]];
					currPerm[currSymmGroup[i-1]] = temp;
					swapped = true;
					break;
				}
			}
			if (!swapped)
			{
				cerr << "Error: didn't swap in permuteSymmGroup." << endl;
			}

			// Reverses the string of points from i to the end.
			for (uint j = i; j <= (i + groupSize - 1)/2; j++)
			{
				mirrorIndex = (groupSize - 1) - (j - i);

				temp = currPerm[currSymmGroup[mirrorIndex]];
				currPerm[currSymmGroup[mirrorIndex]]
						= currPerm[currSymmGroup[j]];
				currPerm[currSymmGroup[j]] = temp;
			}
			permuted = true;
			break;
		}
	}

	if (!permuted)
	{
		cerr << "Error: permuteSymmGroup called with the last permutation."
		     << endl;
		cerr << "currPerm:" << endl;
		for (uint i = 0; i < currPerm.size(); i++)
		{
			cerr << currPerm[i] << " ";
		}
		cerr << endl << "currSymmGroup:" << endl;
		for (uint i = 0; i < currSymmGroup.size(); i++)
		{
			cerr << currSymmGroup[i] << " ";
		}
		cerr << endl << endl;
	}
}

bool testEquality(
		vector<uint>& hypergraph1,
		vector<uint>& hypergraph2,
		vector<HPNT>& currPerm,
		vector<HPNT>& pointsToPoints)
{
	// The remaining lines in hypergraph2, by index.
	set<uint> remainingLines;
	for (uint i = 0; i < hypergraph2.size(); i++)
	{
		remainingLines.insert(i);
	}

	// The lines in the graphs which are being compared are represented as sets
	// so that point ordering is irrelevant.
	set<uint> lineInGraph1, lineInGraph2;

	bool foundLine;
	for (uint i = 0; i < hypergraph1.size(); i++)
	{
		//cerr << "searching for line " << hypergraph1[i] << endl;

		// To equate a line in hypergraph1 with one in hypergraph2, each of the
		// three pairs of points must be equated. To see what a point in
		// hypergraph1 corresponds to in hypergraph2, we must first get that
		// point's number from possibleRows using
		// possibleRows[hypergraph1[i]][j], where j is the point index. Then we
		// permute that point with currPerm, and then we map it to the
		// corresponding point in hypergraph2 with pointsToPoints.
		lineInGraph1.clear();
		for (uint j = 0; j < possibleRows[hypergraph1[i]].size(); j++)
		{
			lineInGraph1.insert(
					pointsToPoints[currPerm[possibleRows[hypergraph1[i]][j]]]);
		}

		foundLine = false;
		// For each line in hypergraph1, we search through every remaining line
		// in hypergraph2 and test it for equality.
		for (set<uint>::iterator remainIter = remainingLines.begin();
		     remainIter != remainingLines.end(); remainIter++)
		{
			lineInGraph2.clear();
			for (uint j = 0; j < possibleRows[hypergraph2[*remainIter]].size();
			     j++)
			{
				lineInGraph2.insert(possibleRows[hypergraph2[*remainIter]][j]);
			}

			if (lineInGraph1 == lineInGraph2)
			{
				// We have found a corresponding line; erase it from the
				// remaining lines and leave the loop.
				remainingLines.erase(remainIter);
				foundLine = true;
				break;
			}
		}

		if (!foundLine)
		{
			//cerr << "didn't find line" << endl;
			return false;
		}
		//cerr << "found line" << endl;
	}

	if (remainingLines.size() != 0)
	{
		cerr << "testEquality found every line without erasing all of "
		     << "remainingLines." << endl;
	}

	return true;
}

void getSymmetryMatrix(
		vector              <uint>    & hypergraph,
		vector<vector<vector<HPNT> > >& outMatrix,
		vector              <HPNT>    & outPtsToSymms,
		bool debug)
{
	outMatrix.clear();

	// The index of each point.
	vector<HPNT> pointIndices;
	set<HPNT> existingIndices;

	// The adjacency matrix of each point. The top vector denotes the point, the
	// middle vector deontes lines the point lies on, and the bottom vector
	// denotes the other points on that line.
	vector<vector<vector<HPNT> > > pointAdjacencies;
	vector<HPNT> currAdjacency;

	vector<vector<HPNT> > emptyNestedVector;
	for (HPNT i = 0; i < n; i++)
	{
		pointAdjacencies.push_back(emptyNestedVector);
	}

	vector<uint> currLine;

	// Translates the structure of the hypergraph into a more useful format by
	// populating pointIndices and pointAdjacencies.
	vector<HPNT> newAdjacency;
	for (HPNT i = 0; i < (HPNT)hypergraph.size(); i++)
	{
		currLine.clear();
		for (HPNT j = 0; j < (HPNT)possibleRows[hypergraph[i]].size(); j++)
		{
			currLine.push_back(possibleRows[hypergraph[i]][j]);
		}

		for (HPNT p1 = 0; p1 < (HPNT)currLine.size(); p1++)
		{
			newAdjacency.clear();
			for (HPNT p2 = 0; p2 < (HPNT)currLine.size(); p2++)
			{
				if (p1 != p2)
				{
					newAdjacency.push_back(currLine[p2]);
				}
			}
			pointAdjacencies[currLine[p1]].push_back(newAdjacency);
		}
	}

	for (HPNT currPoint = 0; currPoint < n; currPoint++)
	{
		pointIndices.push_back(pointAdjacencies[currPoint].size());
		existingIndices.insert(pointAdjacencies[currPoint].size());
	}

	// pointsToSymmetries is initialized to pointIndices because the only
	// initial distinction between points is their index. However, it needs to
	// be adjusted so that the indices go from 0 to the number of indices - 1.
	vector<HPNT> pointsToSymmetries;
	for (uint i = 0; i < pointIndices.size(); i++)
	{
		pointsToSymmetries.push_back(0);
	}
	int indexCount = 0;
	for (set<HPNT>::iterator indexIter = existingIndices.begin();
	     indexIter != existingIndices.end(); indexIter++)
	{
		for (HPNT i = 0; i < (HPNT)pointIndices.size(); i++)
		{
			if (pointIndices[i] == *indexIter)
			{
				pointsToSymmetries[i] = indexCount;
			}
		}
		indexCount++;
	}

	// symmetryMatrix is initialized to k empty vectors, where k is the number
	// of distinct point indices, since getSymmetryMatrixIter only uses it to
	// find the number of symmetries.
	vector<vector<vector<HPNT> > > symmetryMatrix;
	for (uint i = 0; i < existingIndices.size(); i++)
	{
		symmetryMatrix.push_back(emptyNestedVector);
	}

	// Iterates the symmetry matrix until a repetition (i.e., the next iteration
	// is equivalent to the current one).
	vector<HPNT> oldPtsToSymms;
	vector<vector<vector<HPNT> > > oldSymmetryMatrix;

	if (debug)
	{
		cerr << "hypergraph" << endl;
		for (uint i = 0; i < hypergraph.size(); i++)
		{
			for (uint j = 0; j < possibleRows[hypergraph[i]].size(); j++)
			{
				cerr << (uint)possibleRows[hypergraph[i]][j] << " ";
			}
			cerr << endl;
		}
		cerr << endl;

		cerr << "pointAdjacencies" << endl;
		for (uint i = 0; i < pointAdjacencies.size(); i++)
		{
			for (uint j = 0; j < pointAdjacencies[i].size(); j++)
			{
				for (uint k = 0; k < pointAdjacencies[i][j].size(); k++)
				{
					cerr << (uint)pointAdjacencies[i][j][k] << " ";
				}
				cerr << " end line" << endl;
			}
			cerr << " end point" << endl;
		}
		cerr << endl;

		cerr << "symmetryMatrix size" << symmetryMatrix.size() << endl;
	}

	do
	{
		oldPtsToSymms = pointsToSymmetries;
		oldSymmetryMatrix = symmetryMatrix;

		getSymmetryMatrixIter(pointsToSymmetries, pointAdjacencies,
		                      symmetryMatrix, debug);
	} while (oldSymmetryMatrix != symmetryMatrix);

	outMatrix = symmetryMatrix;
	outPtsToSymms = pointsToSymmetries;
}

void getSymmetryMatrixIter(vector              <HPNT>    & ptsToSymms,
                           vector<vector<vector<HPNT> > >& pointAdjacencies,
                           vector<vector<vector<HPNT> > >& symmetryMatrix,
                           bool debug)
{
	vector<HPNT> newPtsToSymms;
	for (uint i = 0; i < ptsToSymms.size(); i++)
	{
		newPtsToSymms.push_back(0);
	}

	vector<vector<HPNT> > currSymm;
	vector<HPNT> currSymmLine;
	HPNT currSymmVal;

	HPNT newSymmMatrixSize;

	HPNT insertedPosition;

	bool insertHere;
	bool identicalLines;

	// tempSymmetryMatrix holds the matrix of new symmetries for every symmetry
	// in the old symmetry matrix, so that new symmetries within one old
	// symmetry are sorted, but sorting does not occur between new symmetries
	// within different old symmetries. This is necessary to avoid infinite
	// looping (see the n=6 hypergraph {345 245 135 124}). It produces the
	// (possibly never-occurring) problem of two identical new symmetries
	// popping up from different old symmetries, which needs to be tested for
	// unless it's established to be impossible.
	vector<vector<vector<vector<HPNT> > > > tempSymmetryMatrix;
	vector<vector<vector       <HPNT> > >   emptyMatrix;
	for (uint i = 0; i < symmetryMatrix.size(); i++)
	{
		tempSymmetryMatrix.push_back(emptyMatrix);
	}

	if (debug)
	{
		cerr << "iter called" << endl;
	}

	// Since tempSymmetryMatrix is populated symmetry number by symmetry number,
	// this counter keeps track of how many points have been inserted into
	// previous symmetry numbers, so that the outer vector doesn't need to be
	// looped through every time a new point is inserted.
	HPNT ptsInPrevSymms = 0;

	for (HPNT currSymmNum = 0;
	     currSymmNum < (HPNT)symmetryMatrix.size();
	     currSymmNum++)
	{
		for (HPNT currPoint = 0;
		     currPoint < (HPNT)ptsToSymms.size();
		     currPoint++)
		{
			if (ptsToSymms[currPoint] == currSymmNum)
			{
				// Creates the new sorted symmetry matrix for the current point.
				currSymm.clear();
				if (debug)
				{
					cerr << "making matrix" << endl;
				}
				for (HPNT line = 0;
				     line < (HPNT)pointAdjacencies[currPoint].size();
				     line++)
				{
					// Creates the sorted symmetry vector for a line.
					currSymmLine.clear();
					for (HPNT adjPt = 0;
					     adjPt < (HPNT)pointAdjacencies[currPoint][line].size();
					     adjPt++)
					{
						currSymmVal = ptsToSymms[
								pointAdjacencies[currPoint][line][adjPt]];
						for (HPNT i = 0; i <= (HPNT)currSymmLine.size(); i++)
						{
							if (i == (HPNT)currSymmLine.size() ||
							    currSymmVal <  currSymmLine[i])
							{
								currSymmLine.insert(currSymmLine.begin() + i,
								                    currSymmVal);
								break;
							}
						}
					}

					if (debug)
					{
						cerr << "created vector" << endl;
						for (uint i = 0; i < currSymmLine.size(); i++)
						{
							cerr << (uint)currSymmLine[i] << " ";
						}
						cerr << endl;
					}

					// Adds the vector to the sorted symmetry matrix.
					for (HPNT i = 0; i <= (HPNT)currSymm.size(); i++)
					{
						insertHere = false;
						identicalLines = true;
						if (i < (HPNT)currSymm.size())
						{
							if      (currSymmLine.size() <  currSymm[i].size())
							{
								// The new line is smaller; insert here.
								insertHere = true;
							}
							else if (currSymmLine.size() == currSymm[i].size())
							{
								for (HPNT j = 0; j < (HPNT)currSymmLine.size();
								     j++)
								{
									if (currSymmLine[j] < currSymm[i][j])
									{
										// The new line has a smaller value;
										// insert here.
										insertHere = true;
										identicalLines = false;
										break;
									}
									else if (currSymmLine[j] > currSymm[i][j])
									{
										// The new line has a larger value;
										// do not insert here.
										identicalLines = false;
										break;
									}
								}

								// The two lines are identical; insert here.
								if (identicalLines)
								{
									insertHere = true;
								}
							}
						}
						if (i == (HPNT)currSymm.size() || insertHere)
						{
							if (debug)
							{
								cerr << "inserted at position " << (uint)i << endl;
							}
							currSymm.insert(currSymm.begin() + (uint)i,
							                currSymmLine);
							break;
						}
					}
				}

				newSymmMatrixSize = tempSymmetryMatrix[currSymmNum].size();

				insertedPosition = addToSymmetryMatrix(
						tempSymmetryMatrix[currSymmNum], currSymm);

				// The symmetry matrix is the same size, so the symmetry vector
				// already existed.
				if ((HPNT)tempSymmetryMatrix[currSymmNum].size() ==
				    newSymmMatrixSize)
				{
					newPtsToSymms[currPoint] =
							insertedPosition + ptsInPrevSymms;
				}
				// The symmetry matrix changed size, so the symmetry vector was
				// newly inserted.
				else
				{
					// The positions of some of the previous points have been
					// incremented; adjust the vector accordingly.
					for (uint i = 0; i < newPtsToSymms.size(); i++)
					{
						if (newPtsToSymms[i] >=
							insertedPosition + ptsInPrevSymms)
						{
							newPtsToSymms[i]++;
						}
					}

					newPtsToSymms[currPoint] =
							insertedPosition + ptsInPrevSymms;
				}
			}
		}
		ptsInPrevSymms += tempSymmetryMatrix[currSymmNum].size();
	}

	// Converts tempSymmetryMatrix to symmetryMatrix by flattening it.
	symmetryMatrix.clear();
	bool repeatedSymmetry;
	for (uint i = 0; i < tempSymmetryMatrix.size(); i++)
	{
		for (uint j = 0; j < tempSymmetryMatrix[i].size(); j++)
		{
			// Tests for repeated symmetries.
			repeatedSymmetry = false;
			for (uint k = 0; k < symmetryMatrix.size(); k++)
			{
				if (symmetryMatrix[k] == tempSymmetryMatrix[i][j])
				{
					cerr << "Error: Repeated symmetry matrix in "
					     << "getSymmetryMatrixIter." << endl;
					repeatedSymmetry = true;
				}
			}
			if (!repeatedSymmetry)
			{
				symmetryMatrix.push_back(tempSymmetryMatrix[i][j]);
			}
		}
	}

	ptsToSymms = newPtsToSymms;
}

uint addToSymmetryMatrix(vector<vector<vector<HPNT> > >& symmetryMatrix,
                         vector<vector       <HPNT> >  & symmetry)
{
	uint insertedIndex = 0;

	int compareValue;

	for (vector<vector<vector<HPNT> > >::iterator matrixIter =
	     		symmetryMatrix.begin();
	     matrixIter != symmetryMatrix.end();
	     matrixIter++)
	{
		compareValue = compareSymmetryVectors(symmetry, *matrixIter);

		// If the vector already exists in the matrix, don't do anything.
		if      (compareValue == 0)
		{
			return insertedIndex;
		}
		else if (compareValue == -1)
		{
			symmetryMatrix.insert(matrixIter, symmetry);
			return insertedIndex;
		}

		insertedIndex++;
	}
	symmetryMatrix.insert(symmetryMatrix.end(), symmetry);
	return insertedIndex;
}

int compareSymmetryVectors(vector<vector<HPNT> >& symmetry1,
                           vector<vector<HPNT> >& symmetry2)
{
	HPNT size1 = symmetry1.size();
	HPNT size2 = symmetry2.size();

	if      (size1 < size2)
	{
		return -1;
	}
	else if (size1 > size2)
	{
		return 1;
	}

	for (HPNT i = 0; i < size1; i++)
	{
		if      (symmetry1[i].size() < symmetry2[i].size())
		{
			return -1;
		}
		else if (symmetry1[i].size() > symmetry2[i].size())
		{
			return 1;
		}
	}

	HPNT currVal1, currVal2;
	for (HPNT i = 0; i < size1; i++)
	{
		for (HPNT j = 0; j < (HPNT)symmetry1[i].size(); j++)
		{
			currVal1 = symmetry1[i][j];
			currVal2 = symmetry2[i][j];

			if      (currVal1 < currVal2)
			{
				return -1;
			}
			else if (currVal1 > currVal2)
			{
				return 1;
			}
		}
	}

	return 0;
}

bool outputGraph(vector<uint>& hypergraph, uint i, vector<uint>& counts)
{
	ofstream outFile("hypergraphs.txt", ios::app);
	if (!outFile.is_open())
	{
		cerr << "Error opening output file." << endl;
		return false;
	}

	outFile << i << endl;

	int graphWeakness;
	if (!weakGraph(hypergraph))
	{
		graphWeakness = -1;
		outFile << "non-weak" << endl;
	}
	else if (!strongGraph(hypergraph))
	{
		graphWeakness = 0;
		outFile << "weak" << endl;
	}
	else
	{
		graphWeakness = 1;
		outFile << "strong" << endl;
	}

	vector<vector<bool> > boolGraph;
	booleanize(hypergraph, boolGraph);

	int graphStability = stableGraph(hypergraph, boolGraph);
	if      (graphStability == -1)
	{
		outFile << "unstable" << endl;
	}
	else if (graphStability == 0)
	{
		outFile << "semistable" << endl;
	}
	else if (graphStability == 1)
	{
		outFile << "stable" << endl;
	}
	else
	{
		cerr << "invalid graph stability in outputGraph" << endl;
		return false;
	}

	// The counts are set up so that /3 gives weakness and %3 gives stability.
	counts[3*(graphWeakness + 1) + (graphStability + 1)]++;

	if (planarGraph(boolGraph))
	{
		outFile << "planar" << endl;
	}
	else
	{
		outFile << "nonplanar" << endl;
	}

	outFile << "index " << graphIndex(boolGraph) << endl;

	if (hasLoosePoints(boolGraph))
	{
		outFile << "loose" << endl;
	}
	else
	{
		outFile << "not loose" << endl;
	}

	uint numRows = hypergraph.size();

	for (uint row = 0; row < numRows; row++)
	{
		for (uint point = 0; point < possibleRows[hypergraph[row]].size();
		     point++)
		{
			outFile << (uint)possibleRows[hypergraph[row]][point] << " ";
		}
		outFile << endl;
	}
	outFile << endl;

	return true;
}

int stableGraph(vector<uint>& hypergraph, vector<vector<bool> >& boolGraph)
{
	HPNT numPoints;
	vector<vector<bool> > boolGraphCopy = boolGraph;
	if (boolGraph.empty())
	{
		booleanize(hypergraph, boolGraphCopy);
		numPoints = n;
	}
	else
	{
		numPoints = boolGraph[0].size();
	}

	// Stabilizes the graph by converting high-index points to lines.
	HPNT origNumPoints = numPoints;
	HPNT origNumLines = boolGraph.size();
	// The number of lines which the current point lies on.
	HPNT pointIndex;
	// The lines which the current point lies on.
	vector<HPNT> touchingLines;
	vector<bool> newRow;

	for (HPNT currColNum = 0; currColNum < origNumPoints; currColNum++)
	{
		pointIndex = 0;
		touchingLines.clear();

		for (HPNT currRowNum = 0; currRowNum < origNumLines; currRowNum++)
		{
			if (boolGraphCopy[currRowNum][currColNum])
			{
				pointIndex++;
				touchingLines.push_back(currRowNum);
			}
		}

		if (pointIndex >= 3)
		{
			numPoints += pointIndex - 1;

			// Creates a new row in the hypergraph. If the three touching
			// lines are, in order, A, B, and C, and the triple point's index
			// was originally i, and the old number of points is m, then the
			// points in the new row are i, m, and m+1.
			newRow.clear();
			for (HPNT i = 0; i < numPoints; i++)
			{
				newRow.push_back((i == currColNum) ||
				                 (i > numPoints - pointIndex));
			}
			boolGraphCopy.push_back(newRow);

			// Adds two new columns to the rest of the hypergraph. A is not
			// modified, but B's i is replaced with m, and C's i is replaced
			// with m+1.
			for (HPNT r = 0; r < (HPNT)boolGraphCopy.size() - 1; r++)
			{
				for (HPNT i = 1; i < (HPNT)touchingLines.size(); i++)
				{
					if (r == touchingLines[i])
					{
						boolGraphCopy[r][currColNum] = false;
						boolGraphCopy[r].push_back(true);
					}
					else
					{
						boolGraphCopy[r].push_back(false);
					}
				}
			}
		}
	}

	HPNT totalNumRows = boolGraphCopy.size();

	vector<bool> subgraph;
	vector<bool> fullSubgraph;
	for (HPNT i = 0; i < totalNumRows; i++)
	{
		subgraph.push_back(0);
		fullSubgraph.push_back(1);
	}

	uint numSubgraphs = (uint)(pow(2.0, double(totalNumRows)));

	uint currPowOf2;

	int nY;
	int mY;
	int nX;
	int mX;
	int pYinXminusY;

	double lhs;
	double rhs;

	bool semistable = true;
	bool stable = true;

	// Iterates through each non-empty proper subset by counting in binary.
	// Tests Gieseker's inequality on each subset.
	for (uint subgraphNum = 1; subgraphNum < numSubgraphs - 1; subgraphNum++)
	{
		// Sets the appropriate subgraph (represents which rows are included).
		currPowOf2 = 1;
		for (uint power = 0; power < (uint)totalNumRows; power++)
		{
			subgraph[power] = (subgraphNum/currPowOf2) % 2;
			currPowOf2 *= 2;
		}

		// Gieseker's inequality is the following:
		// 2*|n(Y) - m(Y)*n(X)/m(X)| < p(Y IN X\Y).
		// X is the hypergraph and Y is the subgraph.
		// n(G) is the number of original lines in G.
		// m(G) is the total number of rows (lines plus triple points) in G.
		// IN is set intersection.
		// X\Y is those rows in X but not in Y.
		// p(G) is the number of points (columns with at least one 1) in a
		// graph.

		nY = getGiesekerN(boolGraphCopy, subgraph, origNumLines);
		mY = getGiesekerM(boolGraphCopy, subgraph, origNumLines);
		nX = getGiesekerN(boolGraphCopy, fullSubgraph, origNumLines);
		mX = getGiesekerM(boolGraphCopy, fullSubgraph, origNumLines);
		pYinXminusY = getGiesekerP(boolGraphCopy, subgraph);

		lhs = fabs(2.0*(double(nY) - double(mY*nX)/double(mX)));
		rhs = double(pYinXminusY);

		if (lhs >= rhs)
		{
			if (lhs > rhs)
			{
				semistable = false;
				return -1;
			}

			stable = false;
		}
	}

	if (semistable && !stable)
	{
		return 0;
	}
	else if (semistable && stable)
	{
		return 1;
	}

	cerr << "invalid state in stableGraph" << endl;
	return 2;
}

void booleanize(vector<uint>& hypergraph, vector<vector<bool> >& outGraph)
{
	outGraph.clear();

	vector<bool> emptyRow;
	for (HPNT i = 0; i < n; i++)
	{
		emptyRow.push_back(false);
	}
	for (HPNT i = 0; i < (HPNT)hypergraph.size(); i++)
	{
		outGraph.push_back(emptyRow);
	}

	// Converts the hypergraph to a bool matrix.
	for (uint i = 0; i < hypergraph.size(); i++)
	{
		for (uint j = 0; j < possibleRows[hypergraph[i]].size(); j++)
		{
			outGraph[i][possibleRows[hypergraph[i]][j]] = true;
		}
	}
}

int getGiesekerN(vector<vector<bool> >& hypergraph, vector<bool>& subgraph,
                 HPNT origNumLines)
{
	int giesekerN = 0;
	int amountToAdd;

	for (HPNT i = 0; i < origNumLines; i++)
	{
		if (subgraph[i])
		{
			amountToAdd = 0;
			for (HPNT j = 0; j < (HPNT)hypergraph[i].size(); j++)
			{
				if (hypergraph[i][j])
				{
					amountToAdd++;
				}
			}
			giesekerN += amountToAdd - 2;
		}
	}

	return giesekerN;
}

int getGiesekerM(vector<vector<bool> >& hypergraph, vector<bool>& subgraph,
                 HPNT origNumLines)
{
	int giesekerM = 0;
	int amountToAdd;

	for (HPNT i = 0; i < (HPNT)hypergraph.size(); i++)
	{
		if (subgraph[i])
		{
			amountToAdd = 0;
			for (HPNT j = 0; j < (HPNT)hypergraph[i].size(); j++)
			{
				if (hypergraph[i][j])
				{
					amountToAdd++;
				}
			}
			giesekerM += amountToAdd - 2;
		}
	}

	return giesekerM;
}

int getGiesekerP(vector<vector<bool> >& hypergraph, vector<bool>& subgraph)
{
	int giesekerP = 0;

	bool pointInY, pointInXMinusY;

	for (uint currCol = 0; currCol < hypergraph[0].size(); currCol++)
	{
		pointInY = false;
		pointInXMinusY = false;

		for (uint currRow = 0; currRow < hypergraph.size(); currRow++)
		{
			if (hypergraph[currRow][currCol])
			{
				if (subgraph[currRow])
				{
					pointInY = true;
				}
				else
				{
					pointInXMinusY = true;
				}
			}
		}

		if (pointInY && pointInXMinusY)
		{
			giesekerP++;
		}
	}

	return giesekerP;
}

bool weakGraph(vector<uint>& hypergraph)
{
	vector<bool> subgraph;
	for (uint i = 0; i < hypergraph.size(); i++)
	{
		subgraph.push_back(0);
	}

	uint numSubgraphs = (uint)(pow(2.0, double(hypergraph.size())));

	uint currPowOf2;

	bool includeRow;
	uint numRowsIncluded;

	bool pointIncluded;
	uint numPointsIncluded;

	// Tests every subgraph which has more than 1 line and less than all of
	// them. Hence, starts with subgraph 3, which represents having the last two
	// lines, and ends with subgraph numSubgraphs - 2, which represents having
	// all but the last line.
	for (uint subgraphNum = 3; subgraphNum < numSubgraphs - 1; subgraphNum++)
	{
		// Sets the appropriate subgraph (represents which rows are included).
		numPointsIncluded = 0;
		numRowsIncluded = 0;
		currPowOf2 = 1;
		for (uint power = 0; power < hypergraph.size(); power++)
		{
			includeRow = (subgraphNum/currPowOf2) % 2;
			subgraph[power] = includeRow;
			if (includeRow)
			{
				numRowsIncluded += possibleRows[hypergraph[power]].size() - 2;
			}
			currPowOf2 *= 2;
		}

		// Skip the subset if it only contains one row.
		if (numRowsIncluded == 1)
		{
			continue;
		}

		// Counts the points in the subgraph.
		for (HPNT i = 0; i < n; i++)
		{
			pointIncluded = false;
			for (HPNT j = 0; j < (HPNT)hypergraph.size(); j++)
			{
				if (subgraph[j])
				{
					for (uint k = 0; k < possibleRows[hypergraph[j]].size();
					     k++)
					{
						if (possibleRows[hypergraph[j]][k] == i)
						{
							pointIncluded = true;
							break;
						}
					}
					if (pointIncluded)
					{
						break;
					}
				}
			}
			if (pointIncluded)
			{
				numPointsIncluded++;
			}
		}

		if (numPointsIncluded < numRowsIncluded + 2)
		{
			return false;
		}
	}

	return true;
}

bool strongGraph(vector<uint>& hypergraph)
{
	vector<uint> subhypergraph;

	vector<bool> subgraph;
	for (uint i = 0; i < hypergraph.size(); i++)
	{
		subgraph.push_back(0);
	}

	uint numSubgraphs = (uint)(pow(2.0, double(hypergraph.size())));

	uint currPowOf2;

	bool includeRow;
	uint numRowsIncluded;

	bool pointIncluded;
	uint numPointsIncluded;

	// Tests every subgraph which has more than 6 lines and less than all of
	// them.
	for (uint subgraphNum = 0; subgraphNum < numSubgraphs - 1; subgraphNum++)
	{
		// Sets the appropriate subgraph (represents which rows are included).
		numPointsIncluded = 0;
		numRowsIncluded = 0;
		currPowOf2 = 1;
		for (uint power = 0; power < hypergraph.size(); power++)
		{
			includeRow = (subgraphNum/currPowOf2) % 2;
			subgraph[power] = includeRow;
			if (includeRow)
			{
				numRowsIncluded += possibleRows[hypergraph[power]].size() - 2;
			}
			currPowOf2 *= 2;
		}

		// Counts the points in the subgraph.
		for (HPNT i = 0; i < n; i++)
		{
			pointIncluded = false;
			for (HPNT j = 0; j < (HPNT)hypergraph.size(); j++)
			{
				if (subgraph[j])
				{
					for (uint k = 0; k < possibleRows[hypergraph[j]].size();
					     k++)
					{
						if (possibleRows[hypergraph[j]][k] == i)
						{
							pointIncluded = true;
							break;
						}
					}
					if (pointIncluded)
					{
						break;
					}
				}
			}
			if (pointIncluded)
			{
				numPointsIncluded++;
			}
		}

		// Skip the subset if it contains less than six points (the smallest weak
		// hypergraph that isn't degenerate is for n=6).
		if (numPointsIncluded < 6)
		{
			continue;
		}

		if (numPointsIncluded == numRowsIncluded + 2)
		{
			// This subgraph is a hypergraph; test the weak condition on it.
			subhypergraph.clear();
			for (HPNT i = 0; i < (HPNT)hypergraph.size(); i++)
			{
				if (subgraph[i])
				{
					subhypergraph.push_back(hypergraph[i]);
				}
			}
			if (weakGraph(subhypergraph))
			{
				return false;
			}
		}
	}

	return true;
}

/*
void transformF(vector<vector<bool> >& hypergraph,
                vector<vector<vector<bool> > >& outGraphs)
{
	// F can be applied whenever we find two lines l1 and l2 and a point i such
	// that l1 and l2 intersect at exactly one point k and i is not on either
	// line. Because of symmetry, we assume that l2 has a greater index than l1.
	uint intersect;
	bool doublePoint;
	uint newGraphIndex;
	vector<bool> newLine;
	for (uint l1 = 0; l1 < hypergraph.size(); l1++)
	{
		for (uint l2 = l1 + 1; l2 < hypergraph.size(); l2++)
		{
			intersect = hypergraph[l1].size();
			// Finds the points at which l1 and l2 intersect.
			for (uint k = 0; k < hypergraph[l1].size(); k++)
			{
				if (hypergraph[l1][k] && hypergraph[l2][k])
				{
					if (intersect != hypergraph[l1].size())
					{
						// We've found two intersects; set the intersect to an
						// invalid value.
						intersect = hypergraph[l1].size();
						break;
					}
					intersect = k;
				}
			}
			// Tests that l1 and l2 have been found to intersect at exactly one
			// point.
			if (intersect != hypergraph[l1].size())
			{
				doublePoint = true;
				// Checks that the intersect point is a double point.
				for (uint line = 0; line < hypergraph.size(); line++)
				{
					if ((line != l1) && (line != l2))
					{
						if (hypergraph[line][intersect])
						{
							doublePoint = false;
							break;
						}
					}
				}

				if (!doublePoint)
				{
					continue;
				}

				// Finds every point i which is not on either line and makes a
				// new hypergraph out of it.
				for (uint i = 0; i < hypergraph[l1].size(); i++)
				{
					if (!hypergraph[l1][i] && !hypergraph[l2][i])
					{
						cerr << l1 << " " << l2 << " " << intersect << " " << i << endl;
						newGraphIndex = outGraphs.size();
						outGraphs.push_back(hypergraph);
						for (uint line = 0; line < hypergraph.size(); line++)
						{
							if (line == l2)
							{
								outGraphs[newGraphIndex][line][intersect] = 0;
								outGraphs[newGraphIndex][line].push_back(1);
							}
							else
							{
								outGraphs[newGraphIndex][line].push_back(0);
							}
						}
						newLine.clear();
						for (uint point = 0; point < hypergraph[0].size() + 1;
						     point++)
						{
							if ((point == i)         ||
							    (point == intersect) ||
							    (point == hypergraph[0].size()))
							{
								newLine.push_back(1);
							}
							else
							{
								newLine.push_back(0);
							}
						}
						outGraphs[newGraphIndex].push_back(newLine);
					}
				}
				cerr << endl;
			}
		}
	}
}

void transformG(vector<vector<bool> >& hypergraph,
                vector<vector<vector<bool> > >& outGraphs)
{
	// G can be applied whenever we find two lines l1 and l2 with point p1 on l1
	// and p2 on l2 such that lines l1 and l2 don't intersect and there is no
	// line joining p1 with p2. Also, p1 and p2 must have index over 1.
	uint newGraphIndex;
	bool intersect;
	bool joiningLine;
	bool goodIndex1, goodIndex2;
	vector<bool> newLine;
	for (uint l1 = 0; l1 < hypergraph.size(); l1++)
	{
		for (uint l2 = l1 + 1; l2 < hypergraph.size(); l2++)
		{
			intersect = false;
			// Finds whether l1 and l2 intersect.
			for (uint k = 0; k < hypergraph[l1].size(); k++)
			{
				if (hypergraph[l1][k] && hypergraph[l2][k])
				{
					intersect = true;
					break;
				}
			}

			if (intersect)
			{
				continue;
			}

			for (uint p1 = 0; p1 < hypergraph[l1].size(); p1++)
			{
				if (!hypergraph[l1][p1])
				{
					continue;
				}

				for (uint p2 = 0; p2 < hypergraph[l2].size(); p2++)
				{
					if (!hypergraph[l2][p2])
					{
						continue;
					}

					joiningLine = false;
					for (uint l3 = 0; l3 < hypergraph.size(); l3++)
					{
						if (hypergraph[l3][p1] && hypergraph[l3][p2])
						{
							joiningLine = true;
							break;
						}
					}

					if (joiningLine)
					{
						continue;
					}

					// Tests that p1 and p2 have index > 1.
					goodIndex1 = false;
					goodIndex2 = false;
					for (uint l3 = 0; l3 < hypergraph.size(); l3++)
					{
						if ((!goodIndex1) && (l3 != l1) && hypergraph[l3][p1])
						{
							goodIndex1 = true;
						}
						if ((!goodIndex2) && (l3 != l2) && hypergraph[l3][p2])
						{
							goodIndex2 = true;
						}
						if (goodIndex1 && goodIndex2)
						{
							continue;
						}
					}
					if (!goodIndex1 || !goodIndex2)
					{
						continue;
					}

					// We have found a suitable l1, l2, p1, p2.
					cerr << l1 << " " << l2 << " " << p1 << " " << p2 << endl;

					newGraphIndex = outGraphs.size();
					outGraphs.push_back(hypergraph);
					for (uint line = 0; line < hypergraph.size(); line++)
					{
						if      (line == l1)
						{
							outGraphs[newGraphIndex][line][p1] = 0;
							outGraphs[newGraphIndex][line].push_back(1);
						}
						else if (line == l2)
						{
							outGraphs[newGraphIndex][line][p2] = 0;
							outGraphs[newGraphIndex][line].push_back(1);
						}
						else
						{
							outGraphs[newGraphIndex][line].push_back(0);
						}
					}

					newLine.clear();
					for (uint point = 0; point < hypergraph[0].size() + 1;
					     point++)
					{
						if ((point == p1) || (point == p2) ||
						    (point == hypergraph[0].size()))
						{
							newLine.push_back(1);
						}
						else
						{
							newLine.push_back(0);
						}
					}

					outGraphs[newGraphIndex].push_back(newLine);
				}
			}
		}
	}
}
*/
bool planarGraph(vector<vector<bool> >& hypergraph)
{
	// Maps the hypergraph lines to set indices; each set will ultimately hold
	// a group of lines which must be drawn as the same line on the plane.
	vector<uint> linesToSets;

	// The sets themselves.
	vector<set<uint> > setsToLines;

	set<uint> emptySet;

	// Initializes linesToSets and setsToLines. Each line initially has its own
	// set.
	for (uint i = 0; i < hypergraph.size(); i++)
	{
		linesToSets.push_back(i);
		setsToLines.push_back(emptySet);
		setsToLines[i].insert(i);
	}

	vector<uint> oldLinesToSets;
	set<uint>* pSet1 = NULL;
	set<uint>* pSet2 = NULL;
	uint numIntersects;
	uint firstIntersect;
	uint numPts = hypergraph[0].size();
	bool mergedSets;
	while (linesToSets != oldLinesToSets)
	{
		oldLinesToSets = linesToSets;

		mergedSets = false;

		// Iterates through every ordered pair of sets.
		for (uint set1Idx = 0; set1Idx < setsToLines.size() - 1; set1Idx++)
		{
			for (uint set2Idx = set1Idx + 1; set2Idx < setsToLines.size();
			     set2Idx++)
			{
				pSet1 = &setsToLines[set1Idx];
				pSet2 = &setsToLines[set2Idx];

				// Iterates through every ordered pair of lines, one from each
				// set. Tests whether the two sets intersect at at least two
				// points.
				numIntersects = 0;
				firstIntersect = numPts;

				for (set<uint>::iterator set1Iter = pSet1->begin();
				     set1Iter != pSet1->end(); set1Iter++)
				{
					for (set<uint>::iterator set2Iter = pSet2->begin();
					     set2Iter != pSet2->end(); set2Iter++)
					{
						// Tests for an intersection.
						for (uint p = 0; p < numPts; p++)
						{
							if (hypergraph[*set1Iter][p] &&
							    hypergraph[*set2Iter][p])
							{
								if (numIntersects == 0)
								{
									firstIntersect = p;
									numIntersects++;
								}
								else if (p != firstIntersect)
								{
									// If two intersects are found, break out
									// of the nested loops counting the
									// intersects.
									numIntersects++;
									break;
								}
							}
						}

						if (numIntersects == 2)
						{
							break;
						}
					}

					if (numIntersects == 2)
					{
						break;
					}
				}

				// Two intersects have been found; merge the sets by having set1
				// absorb set2. Then break out of the set iteration loops.
				if (numIntersects == 2)
				{
					for (set<uint>::iterator set2Iter = pSet2->begin();
					     set2Iter != pSet2->end(); set2Iter++)
					{
						pSet1->insert(*set2Iter);
						linesToSets[*set2Iter] = set1Idx;
					}
					setsToLines.erase(setsToLines.begin() + set2Idx);

					mergedSets = true;
					break;
				}
			}

			if (mergedSets)
			{
				break;
			}
		}
	}

	return (setsToLines.size() > 1);
}

uint graphIndex(vector<vector<bool> >& hypergraph)
{
	uint maxIndex = 0;
	uint currIndex;
	for (uint pt = 0; pt < hypergraph[0].size(); pt++)
	{
		currIndex = 0;
		for (uint ln = 0; ln < hypergraph.size(); ln++)
		{
			if (hypergraph[ln][pt])
			{
				currIndex++;
			}
		}
		if (currIndex > maxIndex)
		{
			maxIndex = currIndex;
		}
	}
	return maxIndex;
}

bool hasLoosePoints(vector<vector<bool> >& hypergraph)
{
	uint currIndex;
	for (uint pt = 0; pt < hypergraph[0].size(); pt++)
	{
		currIndex = 0;
		for (uint ln = 0; ln < hypergraph.size(); ln++)
		{
			if (hypergraph[ln][pt])
			{
				currIndex++;
			}
		}
		if (currIndex == 1)
		{
			return true;
		}
	}
	return false;
}

uint graphSize(vector<uint>& hypergraph)
{
	uint size = 0;
	for (uint line = 0; line < hypergraph.size(); line++)
	{
		size += possibleRows[hypergraph[line]].size() - 2;
	}
	return size;
}