/* Robert S Laramee
 * CS391S/T
 * 8 April 1997
 * Assignment #1
 *
 * see end of program for required documentation
 */

#include<stdio.h>
#define WORKED 1
#define DIDNT_WORK 2
#define NUM_OF_NODES 56169     /**  smallgraph = 128 
                              **  largegraph1 = 56,169 
                              **  largegraph2 = 16,384
                              **/

typedef enum { GREEN, RED, BLUE } colortype1;
typedef enum { WHITE, GRAY, BLACK } colortype2;

struct node_template {
    
    colortype1 paint_color;           
    colortype2 visit_color;        
    int adjacent_nodes[50];
    int predecessor;
};

struct node_template node_array[NUM_OF_NODES];

/**  a variable for the DFS_Visit() function 
 **/ 

int parent = 0;

void Print_Cycle(int matching_node, int original_node) {

    printf("This graph is not two-colorable.\n");
    printf("Odd cycle starts at node %i and ends at node %i\n", 
            matching_node, original_node);

/*    if (matching_node == original_node) {
        
        printf(" done\n");
        return;
    }

    matching_node = node_array[matching_node].predecessor;
    Print_Cycle (matching_node, original_node);
*/
    return;
}

/**  The Depth First Search algorithm is on pg 478 of CLR
 **/

int DFS_Visit(int u) {

    int v = 0;
    int number_adjacent = 0;
    int adjacent_node;
    
    parent = node_array[u].predecessor;

    node_array[u].visit_color = GRAY;

    if (node_array[parent].paint_color == RED) {

        node_array[u].paint_color = BLUE;

    } else {

        node_array[u].paint_color = RED;
    }

    /**  Find out how many adjacent nodes there are.
     **/

    while (node_array[u].adjacent_nodes[v] != 0) {  
     
          v++;
          number_adjacent++;  
    }

    for (v=0; v<number_adjacent; v++) {
        
        adjacent_node = node_array[u].adjacent_nodes[v];

        /** Look at all the adjacent nodes.  If we find one with the same 
         ** color, then we have an odd cycle.  Print it out and return 
         ** DIDNT_WORK
         **/

      if (node_array[adjacent_node].visit_color == GRAY) {

          if (node_array[adjacent_node].paint_color == 
              node_array[u].paint_color) {

              Print_Cycle(adjacent_node, u);
              return DIDNT_WORK;
          }
      }

        if (node_array[adjacent_node].visit_color == WHITE) {

            node_array[adjacent_node].predecessor = u;

            if (DFS_Visit(adjacent_node) != 1) {
                printf("Error with recursive call: DFS_Visit()\n");
	    }
        return WORKED;
        }
    }
    node_array[u].visit_color = BLACK;
    return WORKED;
}

int Depth_First_Search() {

    int u, return_value;
        
    /** Initialize all vertices visit color to white and vertices predecessors 
     ** to zero.
     **/
    for (u=1; u<NUM_OF_NODES+1; u++) {
         node_array[u].visit_color = WHITE;
         node_array[u].predecessor = 0;
    }

    for (u=1; u<NUM_OF_NODES+1; u++) {

         if (node_array[u].visit_color == WHITE) {     
             return_value = DFS_Visit(u);

             if (return_value != WORKED) {
                 return DIDNT_WORK;
	     }
         }
    }
    return WORKED;
}

void main(void) {
    
    int i = 0;
    int j = 0;
    int number_of_nodes = 0;
    int current_node = 0; 
    int adjacent_node = 0;
    FILE *graph_file_ptr;

    /**  Initialize all the adjacent nodes to zero. 
     **/

    for (i=0; i<NUM_OF_NODES; i++) {
        for(j=0; j<50; j++) {
            node_array[i].adjacent_nodes[j] = 0;
        }
    }

    /**  Open the graph file. 
     **/
       
    if ((graph_file_ptr = fopen("largegraph2", "r")) == NULL) {
         printf("Error cannot open file 'smallgraph' for reading. \n");
    }      
    
    /**  Read in the number of nodes (|V|).  
     **/
       
    fscanf(graph_file_ptr, "%i", &number_of_nodes);

   /**  Read the file one line at a time, and start building the adjacency
    **  list for each node 
    **/

    while 
   (fscanf(graph_file_ptr, "%i %i\n", ¤t_node, &adjacent_node) == 2) {

        i = 0;

        /**  Find the first empty slot in the current node's adjacency list
         **  and add the adjacent node to it.
         **/
        while (node_array[current_node].adjacent_nodes[i] != 0) { i++; }
        node_array[current_node].adjacent_nodes[i] = adjacent_node;

        i = 0;

        /**  Since this is an undirected graph we also have to
         **  find the first empty slot in the adjacent node's adjacency list
         **  and add the current node to it.
         **/
        while (node_array[adjacent_node].adjacent_nodes[i] != 0) { i++; }
        node_array[adjacent_node].adjacent_nodes[i] = current_node;
    }
            
    if (fclose(graph_file_ptr)) {
        printf("Problem closing smallgraph file...\n");
    }

    /** Start the Depth First Search algorithm.
     **/

    if (Depth_First_Search() == WORKED) {

        printf("This graph is two-colorable.\n");
        for (i=0; i<number_of_nodes; i++) {
            j = 0;

            while (node_array[i].adjacent_nodes[j] != 0) {
                
                adjacent_node = node_array[i].adjacent_nodes[j];
                printf("node = %i color = %i ", i, node_array[i].paint_color);
                printf("adjacent node = %i paint_color = %i\n", 
                        adjacent_node, node_array[adjacent_node].paint_color);
                j++;
	   }
       }
    }
}
/**  The Depth First Search algorithm on pg 478 of CLR was chosen
 **  because of it's running time.  It runs in O(|V| + |E|) steps.
 **
 **  Time of smallgraph
 **  el12> time assignment2
 **  1.468u 0.756s 0:02.28 96.9% 0+66k 0+0io 0pf+0w
 **
 **  Time of largegraph1
 **  el12> time assignment2
 **  9.699u 0.853s 0:11.49 91.7% 0+106k 0+1io 0pf+0w
 **
 **  Time of largegraph2
 **  el12> time assignment2
 **  10.887u 0.880s 0:12.60 93.3% 0+108k 0+1io 0pf+0w
 **
 **  el12> machine
 **  alpha