//
 //  Graph.m
 //  UltraGraph 10000
 //
 //  Created by Jamie Griffin on Mon Mar 01 2004.
 //  Copyright (c) 2004 __MyCompanyName__. All rights reserved.
 //
 //Version 1.0b6
 
 #import "Graph.h"
 
 
 @implementation Graph
 
 
 #pragma mark *** init / copy methods ***
 
 //create an empty graph
 -(id)init
 {
 	if (self =[super init])
 	{
 		verticies = [[NSMutableArray alloc] init];
 		threeColorings = [[NSMutableArray alloc] init];
 		//NSLog(@"New Graph made, size = %d",[verticies count]);
 	}
 	return self;
 }
 
 //makes a new graph from another, either copying or not
 //skips the threeColorings array
 -(id)initWithGraphNoColors:(Graph *)graph copyItems:(BOOL)copy;
 {
 	if (self =[super init]);
 	{
 		NSLog(@"no color init");
 		verticies = [[NSMutableArray alloc]initWithArray:[graph graphAsArray] copyItems:copy];
 		threeColorings = [[NSMutableArray alloc] init];
 	}
 	return self;
 }
 
 //makes a new graph from another, either copying or not
 -(id)initWithGraph:(Graph *)graph copyItems:(BOOL)copy
 {
 	if (self =[super init]);
 	{
 		verticies = [[NSMutableArray alloc]initWithArray:[graph graphAsArray] copyItems:copy];
 		NSMutableArray *tempColorings = [[NSMutableArray alloc]initWithArray:[graph threeColorings] copyItems:copy];
 		threeColorings = tempColorings;
 		if (copy)
 		{
 			NSLog(@"New Graph with Graph(init call, COPY), size = %d",[verticies count]);
 			if ([threeColorings count]>0)
 			{
 				int i;
 				for (i=0; i<[threeColorings count]; i++)
 					NSLog([[threeColorings objectAtIndex:i] graphAsString]);
 			}
 		}
 	}
 	return self;
 }
 
 //class method to copy a graph
 +(Graph *)graphWithGraph:(Graph *)graph copyItems:(BOOL)copy
 {
 	Graph *duplicate = [[Graph alloc] initWithGraph:graph copyItems:copy];
 	//NSLog(@"New Graph with Graph(class call), size = %d",[[duplicate graphAsArray]count]);
 	return duplicate;
 }
 
 //the init method for loading from file
 -(id)initWithCoder:(NSCoder *)coder
 {
 	if (self =[super init])
 	{
 		verticies = [[NSMutableArray alloc] init];
 		verticies = [coder decodeObject];
 		threeColorings = [[NSMutableArray alloc] init];
 		threeColorings = [coder decodeObject];
 		//NSLog(@"New Graph from archiver");
 	}
 	//NSLog([self graphAsString]);
 	return self;
 }
 
 
 
 +(Graph *)loadGraphFromTextFile:(NSString *)file
 {
 	int i;
 	Graph *thisGraph = [[Graph alloc] init];
 	
 	NSString *graphAsString = [[NSString alloc] initWithContentsOfFile:file];
 	//NSLog(graphAsString);
 	
 	//separate the vertices
 	NSArray *stringVertices = [graphAsString componentsSeparatedByString:@";"];
 	//NSLog(@"There are %d vertices", [stringVertices count]);
 	
 	//parse each vertex
 	for (i=0; i<[stringVertices count]; i++)
 	{
 		Vertex *thisVertex = [[Vertex alloc] initWithString:[stringVertices objectAtIndex:i]];
 		[thisGraph addVertex:thisVertex withCopy:FALSE];
 		
 	}
 	return thisGraph;
 	
 }
 
 //for NSCopying
 //ignoring the zone for now
 -(id)copyWithZone:(NSZone *)zone
 {
 	return [Graph graphWithGraph:self copyItems:FALSE];
 }
 
 #pragma mark ***accessor methods***
 
 -(NSMutableArray *)graphAsArray
 {
 	return verticies;
 }
 
 -(unsigned)count
 {
 	return [verticies count];
 }
 
 -(NSMutableArray *)threeColorings
 {
 	return threeColorings;
 }
 
 //gets the vertex with the given number
 //we cannot simply look at the array order since vertices
 //are not necessarily in order
 
 //there is no need to sort the vertices so this O(n) time loop is fine
 
 //post: returns nil if the number was not found
 -(id)vertexWithNumber:(int)thisNumber
 {
 	int i;
 	for (i=0; i<[verticies count]; i++)
 	{
 		if ([[verticies objectAtIndex:i] number]==thisNumber)
 		{
 			return [verticies objectAtIndex:i];
 			
 		}
 	}
 	
 	return nil;
 }
 
 -(Vertex *)vertexWithPosition:(int)thisPosition
 {
 	return [verticies objectAtIndex:thisPosition];
 }
 
 //returns the graph as a string
 //including the 3-colorings
 -(NSString *)graphAsString
 {
 	int i;
 	NSMutableString *stringToBuild = [[NSMutableString alloc] init];
 	
 	//first, the graph uncolored
 	for (i=0; i<[verticies count]-1; i++)
 	{
 		[stringToBuild appendString:[[verticies objectAtIndex:i] stringVertex]];
 		[stringToBuild appendString:@";"];
 	}
 	[stringToBuild appendString:[[verticies objectAtIndex:[verticies count]-1] stringVertex]];
 	
 	[stringToBuild appendString:@"------"];
 	
 	int j;
 	
 	//now the 3-colorings
 	for (j=0; j<[threeColorings count]; j++)
 	{
 		NSArray *thisColoringArray = [[threeColorings objectAtIndex:j] graphAsArray];
 		[stringToBuild appendString:@"**"];
 		int k;
 		for (k=0; k<[thisColoringArray count]-1; k++)
 		{
 			[stringToBuild appendString:[[thisColoringArray objectAtIndex:k] stringVertex]];
 			[stringToBuild appendString:@";"];
 		}
 		
 		//simply to avoid a trailing ";"
 		if ([thisColoringArray count]>0)
 		{
 			[stringToBuild appendString:[[thisColoringArray objectAtIndex:[thisColoringArray count]-1] stringVertex]];
 		}
 		
 	}
 	//NSLog(stringToBuild);
 	return stringToBuild;
 }
 
 
 #pragma mark ***mutator methods***
 
 
 //add a vertex, either copy it or not
 -(void)addVertex:(Vertex *)thisVertex withCopy:(BOOL)copy
 {
 	if (copy)
 	{
 		[verticies addObject:[Vertex vertexWithVertex:thisVertex]];
 	}
 	else
 	{
 		[verticies addObject:thisVertex];
 	}
 }
 
 //breaks the graph into subgraphs
 
 /*
  At this point the breakdown is random (actually not so random, most graphs
  come in nearly in order so the breakdown is often based on number)
  
  This is where the Separator Theorem will be used to make the breakdown
  along the lines of least connectivity for quicker recombination later
 */
 
 //all copies, the original is not affected and may be deleted
 //without adversely affecting the subgraphs
 -(NSArray *)breakGraphInParts:(int)numParts
 {
 	int h,i;
 	NSMutableArray *graphs = [[NSMutableArray alloc] init];
 
 	for (h=0; h<numParts; h++)
 	{
 		[graphs addObject:[[Graph alloc]init]];
 	}
 	for (i=0; i<[verticies count];i++)
 	{
 		//integer division is ideal here
 		[[graphs objectAtIndex:i%numParts] addVertex:[verticies objectAtIndex:i] withCopy:FALSE];
 	}
 	return graphs;
 }
 
 //combines the current graph with otherGraph and stores the resulting graph
 //in the current object
 -(void)combineThisWithGraph:(Graph *)otherGraph
 {
 	NSArray *theseColorings = [self threeColorings];
 	NSArray *otherColorings = [otherGraph threeColorings];
 	NSMutableArray *tempColorings = [[NSMutableArray alloc] init];
 	int numThese=[theseColorings count];
 	int numOthers=[otherColorings count];
 	int i,j,k,m;
 	
 	for (i=0; i<numThese; i++)
 	{
 		Graph *workingGraph = [[Graph alloc] initWithGraph:[theseColorings objectAtIndex:i]copyItems:FALSE];
 		NSLog(@"Working Graph:");
 		NSLog([workingGraph graphAsString]);
 		
 		for (j=0; j<numOthers; j++)
 		{
 			//for every vertex in otherGraph
 			Graph *thisOtherGraph = [[Graph alloc] initWithGraph:[otherColorings objectAtIndex:j]copyItems:FALSE];
 			NSLog(@"Other Graph:");
 			NSLog([otherGraph graphAsString]);
 			
 			for (k=0; k<[thisOtherGraph count]; k++)
 			{
 				NSLog(@"adding a vertex");
 				[workingGraph addVertex:[thisOtherGraph vertexWithNumber:k]withCopy:TRUE];
 			}
 			if ([workingGraph isThisGraphProperlyThreeColored])
 			{
 				[tempColorings addObject:workingGraph];
 			}
 		}
 		[workingGraph release];
 		
 	}
 	
 	//fix the current graph to represent changes
 	[threeColorings release];
 	threeColorings=tempColorings;
 	for (m=0; m<[otherGraph count]; m++)
 	{
 		[verticies addObject:[otherGraph vertexWithPosition:m]];
 	}
 	
 }
 
 //this method looks at this graph and determines if it is properly three colored
 -(BOOL)isThisGraphProperlyThreeColored
 {
 	int vertex, i, thisConnection;
 	Vertex *thisVertex;
 	//for every vertex
 	for (vertex=0; vertex<[verticies count]; vertex++)
 	{
 		thisVertex=[self vertexWithNumber:vertex];
 		//NSLog(@"Now looking at: %d,%d %d",[thisVertex number],vertex,[verticies count]);
 		//NSLog([thisVertex stringVertex]);
 		
 		//for every connection on that vertex
 		for(i=0;i<[thisVertex numConnections];i++)
 		{
 			thisConnection = [[[thisVertex connections] objectAtIndex:i] intValue];
 			//NSLog(@"%d",thisConnection);
 			
 			//see if a connection has the same color as this vertex
 			if ([[self vertexWithNumber:thisConnection] getColor]==[thisVertex getColor])
 			{
 				//NSLog(@"Not a 3-coloring");
 				return FALSE;
 			}
 		}
 	}
 	//we didn't find any problems, so it must work
 	NSLog(@"YES!!!");
 	//	[connectionInput setStringValue:[self stringColors:thisGraph]];
 	return TRUE;
 }
 
 
 //this method should be used from outside to generate the 3-colorings
 -(NSMutableArray *)getThreeColorings
 {
 	NSLog(@"Emtying the threeColorings");
 	[threeColorings removeAllObjects];
 	[self recursiveCheck:self];
 	return threeColorings;
 }
 	
 	
 //this is the recursive function that finds the 3-colorings
 
 /*
  This method generates all possible colorings, even stupid ones such as all the
  same color. This was done by choice since I am looking for a general case solution.
  We could look for K(4) or K(2,3) configurations but this would save negligible time
  and does not help to generalize the solution.
 */
 
 -(void)recursiveCheck:(Graph *)remainingVerticies
 {
 	//NSLog(@"Recursive call");
 	//NSLog([self graphAsString]);
 
 	int i,color;
 	
 	//termination of this branch
 	if ([[remainingVerticies graphAsArray] count]==1)
 	{
 		for (i=0;i<3;i++)
 		{
 			
 			[[[remainingVerticies graphAsArray] objectAtIndex:0] setThisColor:i];
 			if([self isThisGraphProperlyThreeColored])
 			{
 				//we have found a 3-coloring so make a copy and add it to the list
 				NSLog(@"recursive init");
 				[threeColorings addObject:[[Graph alloc] initWithGraphNoColors:self copyItems:TRUE]];
 			}
 		}
 	}
 	else
 	{
 		
 		/* this is a bit messy:
 		   It changes the color of the actual verticies array then checks each of
 		   the end branches for proper 3-coloring. no copys are made during
 		   this phase EVER, the whole graph is copied only if it is
 		   a 3-coloring
 		*/
 		for (color=0;color<3;color++)
 		{
 			//NSLog(@"Mid vertex check");
 			
 			[[[remainingVerticies graphAsArray] objectAtIndex:0] setThisColor:color];
 			Graph *tempGraph = [Graph graphWithGraph:remainingVerticies copyItems:FALSE];
 			[[tempGraph graphAsArray] removeObjectAtIndex:0];
 			//the recursive call
 			[self recursiveCheck:tempGraph];
 		}
 	}
 }
 
 
 
 
 #pragma mark **encoding method***
 
 //encoder method for saving
 -(void)encodeWithCoder:(NSCoder *)coder
 {
 	[coder encodeObject:verticies];
 	[coder encodeObject:threeColorings];
 }
 @end