503 lines
14 KiB
C
503 lines
14 KiB
C
/*
|
|
VertexColoration
|
|
Andrew Coleman
|
|
Licensed under the GPL version 2 or later.
|
|
Full license details are available at http://gnu.org/
|
|
CSC-2400
|
|
|
|
This program is designed to create or read in a graph
|
|
from a user and find a way to identify each vertex
|
|
without touching another vertex of the same indentifier
|
|
(color) and using as few colors as possible.
|
|
*/
|
|
|
|
#define USE_TI92PLUS
|
|
#define OPTIMIZE_ROM_CALLS
|
|
#define MIN_AMS 208
|
|
#define SAVE_SCREEN
|
|
|
|
#include <tigcclib.h>
|
|
|
|
#define MAX_VERTEX 100
|
|
#define SLIDER_WIDTH 125
|
|
#define START_COL 2
|
|
#define START_ROW 10
|
|
|
|
int (*neighbor)[MAX_VERTEX];
|
|
FILE *output;
|
|
void RandomizeGraph ( int );
|
|
void UserDefineGraph ( int );
|
|
void DrawGraph ( int );
|
|
void Greedy ( int );
|
|
void BackTrack ( int );
|
|
/* algorithmstr, numvertexes, numsteps, numcolors, colorarray */
|
|
void ColorationResults ( const char *, int, unsigned long, int, int * );
|
|
|
|
void _main(void)
|
|
{
|
|
randomize();
|
|
int numvert = 0;
|
|
randomize();
|
|
|
|
output = NULL;
|
|
|
|
char *params = calloc ( 11, sizeof( char ) );
|
|
short *opt = calloc ( 2, sizeof( short ) );
|
|
opt[1] = 1;
|
|
/* TIOS specific windowing */
|
|
HANDLE sizewin = DialogNewSimple ( 120, 70 );
|
|
HANDLE sourcepopup = PopupNew ( NULL, 0 );
|
|
PopupAddText ( sourcepopup, -1, "Random", 0 );
|
|
PopupAddText ( sourcepopup, -1, "User", 0 );
|
|
DialogAddTitle ( sizewin, "Graph Source", BT_OK, BT_NONE );
|
|
DialogAddRequest ( sizewin, 2, 16, "Size: ", 0, 3, 4 );
|
|
DialogAddPulldown ( sizewin, 2, 29, "Source: ", sourcepopup, 1 );
|
|
DialogAddRequest ( sizewin, 2, 42, "Output: ", 3, 8, 9 );
|
|
|
|
do {
|
|
if ( DialogDo ( sizewin, CENTER, CENTER, params, opt ) == KEY_ESC )
|
|
{
|
|
HeapFree ( sizewin );
|
|
HeapFree ( sourcepopup );
|
|
free ( params );
|
|
free ( opt );
|
|
return;
|
|
}
|
|
/* convert the number of strings and filename to something i can use */
|
|
char *tmp = calloc ( 8, sizeof( char ) );
|
|
memcpy ( tmp, params, 3 * sizeof( char ) );
|
|
numvert = atoi ( tmp );
|
|
memcpy ( tmp, params + 3, 8 * sizeof( char ) );
|
|
if ( strcmp ( tmp, "" ) != 0 )
|
|
output = fopen ( tmp, "w" );
|
|
free ( tmp );
|
|
} while ( numvert <= 0 && numvert >= MAX_VERTEX );
|
|
HeapFree ( sizewin );
|
|
HeapFree ( sourcepopup );
|
|
free ( params );
|
|
|
|
/* initialize the adjacency matrix */
|
|
neighbor = calloc ( numvert, sizeof( *neighbor ) );
|
|
|
|
if ( opt[1] == 1 )
|
|
RandomizeGraph ( numvert );
|
|
else
|
|
UserDefineGraph ( numvert );
|
|
free ( opt );
|
|
|
|
/* display the neighborlist, size permitting */
|
|
DrawGraph ( numvert );
|
|
/* perform a greedy coloration */
|
|
Greedy ( numvert );
|
|
/* perform a backtrack coloration */
|
|
BackTrack ( numvert );
|
|
|
|
if ( output != NULL )
|
|
fclose ( output );
|
|
free ( neighbor );
|
|
}
|
|
|
|
/*
|
|
This is the random graph algorithm handed out in class.
|
|
*/
|
|
void RandomizeGraph ( int numvert )
|
|
{
|
|
ClrScr();
|
|
int row = 0, col = 0;
|
|
DrawStr ( 1, 1, "Creating neighbors...", A_NORMAL );
|
|
/* For the slider */
|
|
DrawLine ( START_COL, START_ROW, START_COL + SLIDER_WIDTH, START_ROW, A_NORMAL );
|
|
DrawLine ( START_COL, START_ROW + 2, START_COL + SLIDER_WIDTH, START_ROW + 2, A_NORMAL );
|
|
DrawPix ( START_COL, START_ROW + 1, A_NORMAL );
|
|
DrawPix ( START_COL + SLIDER_WIDTH, START_ROW + 1, A_NORMAL );
|
|
int lastsize = 1;
|
|
for ( row = 0; row < numvert - 2; row++ )
|
|
{
|
|
/* again for the slider */
|
|
for ( col = lastsize; col < ceil ( row * SLIDER_WIDTH / numvert ); col++ )
|
|
DrawPix ( col + START_COL, START_ROW + 1, A_NORMAL );
|
|
lastsize = ceil ( row * SLIDER_WIDTH / numvert );
|
|
|
|
/* randomly pick edges for each vertex after this one to eliminate duplicates */
|
|
for ( col = row + 1; col < numvert; col++ )
|
|
{
|
|
int tmp = random ( numvert ) + 1;
|
|
if ( tmp > numvert / 2 )
|
|
{
|
|
neighbor[row][col] = 1;
|
|
neighbor[col][row] = 1;
|
|
}
|
|
}
|
|
}
|
|
|
|
/* finish drawing the slider */
|
|
for ( col = lastsize; col < SLIDER_WIDTH; col++ )
|
|
DrawPix ( col + START_COL, START_ROW + 1, A_NORMAL );
|
|
}
|
|
|
|
/*
|
|
This function will query the user for each vertex's neighbors
|
|
*/
|
|
void UserDefineGraph ( int numvert )
|
|
{
|
|
char *letters = calloc ( MAX_VERTEX * 2, sizeof( int ) );
|
|
HANDLE neighbors = DialogNewSimple ( 145, 70 );
|
|
DialogAddTitle ( neighbors, "Neighbors", BT_OK, BT_NONE );
|
|
|
|
int row = 0;
|
|
char title[23];
|
|
for ( row = 0; row < numvert; row++ )
|
|
{
|
|
/* repeat the same dialog pattern for each vertex */
|
|
memset ( title, 0, 23 * sizeof( char ) );
|
|
memset ( letters, 0, MAX_VERTEX * 2 * sizeof( char ) );
|
|
sprintf ( title, "Enter neighbors for %d", row + 1 );
|
|
DialogAddText ( neighbors, 2, 16, title );
|
|
DialogAddText ( neighbors, 2, 29, "separated by commas" );
|
|
DialogAddRequest ( neighbors, 2, 42, "", 0, MAX_VERTEX * 2, 20 );
|
|
int error = 0;
|
|
if ( DialogDo ( neighbors, CENTER, CENTER, letters, NULL ) == KEY_ESC )
|
|
error = 1;
|
|
if ( !error )
|
|
{
|
|
/* convert the string to neighbors */
|
|
char *num = strtok ( letters, "," );
|
|
while ( num != NULL )
|
|
{
|
|
int neighbornum = atoi ( num );
|
|
/* if neighbornum is out of this range, there is nothing we can do with it */
|
|
if ( neighbornum > 0 && neighbornum <= MAX_VERTEX && neighbornum != row )
|
|
{
|
|
/* otherwise, put in a neighbor */
|
|
neighbor[row][neighbornum - 1] = 1;
|
|
neighbor[neighbornum - 1][row] = 1;
|
|
}
|
|
num = strtok ( NULL, "," );
|
|
}
|
|
}
|
|
/* the user pressed esc, so they want to leave */
|
|
else
|
|
break;
|
|
}
|
|
free ( letters );
|
|
HeapFree ( neighbors );
|
|
}
|
|
|
|
/*
|
|
This function will display the neighbor list so long as there are < 15 vertecies (screen is too small...)
|
|
*/
|
|
void DrawGraph ( int numvert )
|
|
{
|
|
ClrScr();
|
|
|
|
int row = 0, col = 0;
|
|
char *tmp = calloc ( 5, sizeof ( char ) );
|
|
if ( numvert < 15 )
|
|
DrawStr ( 1, 1, "Neighbor listing...", A_NORMAL );
|
|
if ( output != NULL )
|
|
fputs ( "Neighbor listing...\n", output );
|
|
|
|
/* go over each vertex, yes, we can go over this even if we have > 15 vertecies and we aren't printing to a file */
|
|
for ( row = 0; row < numvert; row++ )
|
|
{
|
|
sprintf ( tmp, "%d: ", row + 1 );
|
|
if ( numvert < 15 )
|
|
DrawStr ( 1, (row + 1) * 8 + 1, tmp, A_NORMAL );
|
|
if ( output != NULL )
|
|
fputs ( tmp, output );
|
|
|
|
/* find all neighbors of current vertex */
|
|
for ( col = 0; col < numvert; col++ )
|
|
{
|
|
/* if we have a neighbor, and the random/user graph functions make sure we don't have (row == col) being a neighbor */
|
|
if ( neighbor[row][col] == 1 )
|
|
{
|
|
sprintf ( tmp, " %d", col + 1 );
|
|
if ( numvert < 15 )
|
|
DrawStr ( col * 14 + 20, (row + 1) * 8 + 2, tmp, A_NORMAL );
|
|
if ( output != NULL )
|
|
fputs ( tmp, output );
|
|
}
|
|
}
|
|
if ( output != NULL )
|
|
fputs ( "\n", output );
|
|
}
|
|
if ( output != NULL )
|
|
fputc ( '\n', output );
|
|
free ( tmp );
|
|
|
|
/* if we displayed something, wait for the user to get done before continuing */
|
|
if ( numvert < 15 )
|
|
{
|
|
GKeyFlush();
|
|
ngetchx();
|
|
}
|
|
}
|
|
|
|
/*
|
|
This function will color the graph in a greedy fashion
|
|
*/
|
|
void Greedy ( int numvert )
|
|
{
|
|
ClrScr();
|
|
int maxcolor = 1, row = 0, col = 0, curcolor = 0;
|
|
unsigned long steps = 0;
|
|
/* array of colors for each vertex */
|
|
int *colors = calloc ( numvert, sizeof( int ) );
|
|
/* display what we are doing and the box for the slider bar */
|
|
DrawStr ( 1, 1, "Coloring by greed...", A_NORMAL );
|
|
DrawLine ( START_COL, START_ROW, START_COL + SLIDER_WIDTH, START_ROW, A_NORMAL );
|
|
DrawLine ( START_COL, START_ROW + 2, START_COL + SLIDER_WIDTH, START_ROW + 2, A_NORMAL );
|
|
DrawPix ( START_COL, START_ROW + 1, A_NORMAL );
|
|
DrawPix ( START_COL + SLIDER_WIDTH, START_ROW + 1, A_NORMAL );
|
|
|
|
/* used to keep the last position for the slider */
|
|
int lastsize = 1;
|
|
/* we want to color each vertex */
|
|
for ( row = 0; row < numvert; row++ )
|
|
{
|
|
/* flag to know if a neighbor of the same current color was found */
|
|
int found = 0;
|
|
|
|
/* update the slider bar for each vertex */
|
|
for ( col = lastsize; col < ceil ( row * SLIDER_WIDTH / numvert ); col++ )
|
|
DrawPix ( col + START_COL, START_ROW + 1, A_NORMAL );
|
|
lastsize = ceil ( row * SLIDER_WIDTH / numvert );
|
|
|
|
/* we want to search all colors from 1 to maxcolor + 1 */
|
|
for ( curcolor = 1; curcolor <= maxcolor + 1; curcolor++ )
|
|
{
|
|
/* we already have a color selected, move on */
|
|
if ( colors[row] != 0 )
|
|
continue;
|
|
found = 0;
|
|
/* now we search every other vertex for a neighbor */
|
|
for ( col = 1; col <= numvert; col++ )
|
|
{
|
|
/* don't keep looking if we have already found a color */
|
|
if ( found )
|
|
break;
|
|
/* do we have a neighbor of the same color */
|
|
if ( neighbor[row][col - 1] == 1 && colors[col - 1] == curcolor )
|
|
found = 1;
|
|
/* that's another step towards the solution */
|
|
steps++;
|
|
}
|
|
|
|
/* if no neighbor of this color was found and no color has been assigned, use curcolor */
|
|
if ( !found && colors[row] == 0 )
|
|
colors[row] = curcolor;
|
|
|
|
/* if we have gone over our maximum color limit, increase it */
|
|
if ( colors[row] > maxcolor )
|
|
maxcolor = colors[row];
|
|
}
|
|
}
|
|
|
|
/* finish drawing the slider */
|
|
for ( col = lastsize; col < SLIDER_WIDTH; col++ )
|
|
DrawPix ( col + START_COL, START_ROW + 1, A_NORMAL );
|
|
|
|
/* display the results */
|
|
ColorationResults ( "Greed Colors", numvert, steps, maxcolor, colors );
|
|
free ( colors );
|
|
}
|
|
|
|
void BackTrack ( int numvert )
|
|
{
|
|
ClrScr();
|
|
/* if we output partial listings, we can break the 64KB file limit on the calculator, plus file writes are *slow* */
|
|
int partiallistings = 0;
|
|
if ( output != NULL && DlgMessage ( "Question", "Output partial listings of BackTrack?", BT_YES, BT_NO ) == KEY_ENTER )
|
|
partiallistings = 1;
|
|
int maxcolor = 1, curcolor = 1, row = 0, col = 0;
|
|
unsigned long steps = 0;
|
|
int *colors = calloc ( numvert, sizeof( int ) );
|
|
char *tmp = calloc ( 20, sizeof( char ) );
|
|
/* let the user know what's going on */
|
|
DrawStr ( 1, 1, "BackTrack Color", A_NORMAL );
|
|
ST_helpMsg ( "Hit [ESC] to quit..." );
|
|
sprintf ( tmp, "MaxColor: %d", maxcolor );
|
|
DrawStr ( 1, 9, tmp, A_NORMAL );
|
|
|
|
/* clear the keyboard queue to make sure any stray kepresses don't bother the results */
|
|
GKeyFlush();
|
|
|
|
/* flag to find a neighbor of same color, if we are backtracking in the for loop, and if we have an error */
|
|
int found = 0, back = 0, error = 0;
|
|
if ( output != NULL && partiallistings )
|
|
fputs ( "\nBacktrack Partial Colorings:\n", output );
|
|
for ( row = 0; row < numvert; row++ )
|
|
{
|
|
/* if we are backtracking, start coloring above that vertex's current color */
|
|
if ( back )
|
|
{
|
|
curcolor = colors[row] + 1;
|
|
back = 0;
|
|
}
|
|
/* if we are not backtracking, and we do want to output partial listings, print */
|
|
else if ( output != NULL && partiallistings )
|
|
{
|
|
int i = 0, zero = 0;
|
|
for ( i = 0; i < numvert; i++ )
|
|
{
|
|
char outputltr[4];
|
|
if ( colors[i] != 0 )
|
|
{
|
|
zero = 1;
|
|
sprintf ( outputltr, "%d ", colors[i] );
|
|
fputs ( outputltr, output );
|
|
}
|
|
}
|
|
if ( zero )
|
|
fputs ( "\n", output );
|
|
}
|
|
|
|
found = 0;
|
|
|
|
/* if current color is bigger than maxcolor, we need to stop and back up */
|
|
if ( curcolor > maxcolor )
|
|
{
|
|
/* if we are at the first vertex, then we can increase the current maximum color limit */
|
|
if ( row == 0 )
|
|
{
|
|
/* increase maximum colors */
|
|
maxcolor++;
|
|
sprintf ( tmp, "MaxColor: %d ", maxcolor );
|
|
DrawStr ( 1, 9, tmp, A_REPLACE );
|
|
/* start coloring again */
|
|
curcolor = 1;
|
|
/* if maxcolor is greater than the number of vertecies, then we cannot use more than 1 color per vertex */
|
|
if ( maxcolor > numvert )
|
|
{
|
|
ClrScr();
|
|
DrawStr ( 1, 1, "Cannot be solved by\n tracking backwards.", A_NORMAL );
|
|
if ( output != NULL )
|
|
fputs ( "Cannot be solved by tracking backwards.\n", output );
|
|
error = 1;
|
|
break;
|
|
}
|
|
}
|
|
/* since we aren't at the first vertex, reset the color, since it was wrong anyways, and backtrack */
|
|
else
|
|
{
|
|
colors[row] = 0;
|
|
row = row - 2;
|
|
back = 1;
|
|
continue;
|
|
}
|
|
}
|
|
|
|
/* since we aren't backtracking, and we don't need to backtrack, do some work */
|
|
for ( col = 0; col < numvert; col++ )
|
|
{
|
|
/* don't keep looking if we already have a neighbor of same color */
|
|
if ( found )
|
|
continue;
|
|
/* if we have a neighbor of same color */
|
|
if ( neighbor[row][col] == 1 && colors[col] == curcolor )
|
|
found = 1;
|
|
steps++;
|
|
}
|
|
|
|
/* if a color is not found, increase color and try the same vertex */
|
|
if ( found )
|
|
{
|
|
curcolor++;
|
|
row--;
|
|
continue;
|
|
}
|
|
/* found a color */
|
|
else
|
|
{
|
|
colors[row] = curcolor;
|
|
}
|
|
|
|
/* backtrack takes a long time, so if the user wants to quit prematurely, just hit esc */
|
|
if ( kbhit() )
|
|
{
|
|
if ( ngetchx() == KEY_ESC )
|
|
{
|
|
ClrScr();
|
|
error = 1;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
if ( output != NULL && partiallistings )
|
|
fputs ( "\n", output );
|
|
|
|
/* if the user didn't press esc, display the results */
|
|
if ( !error )
|
|
{
|
|
ColorationResults ( "BackTrack Colors", numvert, steps, maxcolor, colors );
|
|
}
|
|
|
|
free ( colors );
|
|
free ( tmp );
|
|
}
|
|
|
|
/*
|
|
this function will display the results for each of the algorithms
|
|
*/
|
|
void ColorationResults ( const char *algorithm, int numvert, unsigned long steps, int maxcolor, int *colors )
|
|
{
|
|
/* the number of vertecies to put on one row */
|
|
#define ROW_WIDTH 6
|
|
ClrScr();
|
|
char *tmp = calloc ( 20, sizeof( char ) );
|
|
int row = 0, col = 0;
|
|
|
|
/* clear the keyboard queue to make sure we don't get a stray keypress */
|
|
GKeyFlush();
|
|
|
|
DrawStr ( 1, 1, algorithm, A_NORMAL );
|
|
/* print to a file if we need to */
|
|
if ( output != NULL )
|
|
{
|
|
fputs ( algorithm, output );
|
|
fputs ( "\n", output );
|
|
}
|
|
/* print each vertex */
|
|
for ( row = 0; row <= numvert / ROW_WIDTH; row++ )
|
|
{
|
|
/* find each vertex's neighbors */
|
|
for ( col = 1; col <= ROW_WIDTH; col++ )
|
|
{
|
|
/* make sure we don't try to display a vertex that doesn't exist */
|
|
if ( row * ROW_WIDTH + col <= numvert )
|
|
{
|
|
int vert = row * ROW_WIDTH + col;
|
|
sprintf ( tmp, "%d: %d", vert, colors[vert - 1] );
|
|
DrawStr ( ( col - 1 ) * 40, ( row + 2 ) * 8, tmp, A_REPLACE );
|
|
if ( output != NULL )
|
|
{
|
|
fputs ( tmp, output );
|
|
fputs ( "\n", output );
|
|
}
|
|
}
|
|
}
|
|
}
|
|
/* display and print out colors used */
|
|
sprintf ( tmp, "Colors used: %d", maxcolor );
|
|
DrawStr ( 1, ceil ( numvert / ROW_WIDTH + 4 ) * 8, tmp, A_NORMAL );
|
|
if ( output != NULL )
|
|
{
|
|
fputs ( tmp, output );
|
|
fputs ( "\n", output );
|
|
}
|
|
/* display and print out steps taken */
|
|
sprintf ( tmp, "Steps taken: %lu", steps );
|
|
DrawStr ( 1, ceil ( numvert / ROW_WIDTH + 5 ) * 8, tmp, A_NORMAL );
|
|
if ( output != NULL )
|
|
{
|
|
fputs ( tmp, output );
|
|
fputs ( "\n", output );
|
|
fputs ( "\n", output );
|
|
}
|
|
/* let the user press a key when done */
|
|
ngetchx();
|
|
free ( tmp );
|
|
#undef ROW_WIDTH
|
|
}
|