/*  
 *  glrtest.c
 *  Test module for LLR/GLR 0.2 
 *  (c) Lluis Ros
 *
 *  Creation: April 1995
 *  Revision: December 2005   
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include "general.h"
#include "llr.h"
#include "glr.h"
#include "glrtest.h"


/*-----------------------------------------------------------------------------------------------*/
void menu()
{   
    char option;
    graph G=NULL;
    graph Gdup=NULL;
    graph_vertex pv;
    list adjacent;
    list curr;
    status err;
    int i;
    list cycles;

    printf("\nLists & Graphs 0.1 - Test program\n"); 
    printf("\n(c) Lluis Ros 1996 - 2007\n"); 
    printf("\n\n\n");

    do{
      /********************************
       * Main menu
       ********************************/
      printf("\n\nOptions \n");
      printf("-------------------------------------\n");
      printf("1.- Load, print and destroy K4\n");
      printf("2.- Load, print and destroy 4-cycles\n");
      printf("3.- Test copy_adjacent on K4\n");
      printf("4.- Test duplicate_graph on K4\n");
      printf("5.- Test print_graph on K4\n");
      printf("6.- Test destroy_graph on K4 (to detect eventual memory leakages)\n");
      printf("7.- Test detect_fundamental_cycles on K4\n");
      printf("8.- Test delete_vertex_and_edges() on K4\n");
      printf("9.- Test traverse\n");
      printf("a.- Test breadth_first\n");
      printf("b.- Test coordenatize_subgraph()\n");
      printf("0.- Quit\n");
      printf("\nSelect option? ");
      option=getchar();
      
      switch(option)
	{
	case '1':
	  /******************************************************
	   * Load K4 (A graph with specific data)
	   ******************************************************/
	  /* Load K4 */
	  if(build_K4(&G)==ERROR)
	    glr_error("Error:: build_K4() failed in menu()");

	  /* Print its skeleton */
	  print_graph_skeleton(stdout,G);

	  /* Destroy it */
	  destroy_graph(&G,free_specific_vertex_data,free_specific_edge_data);
	  break;

	case '2':
	  /******************************************************
	   * Load "four cycles" (A graph without specific data)
	   ******************************************************/
	  if(build_four_cycles(&G)==ERROR)
	    glr_error("Error:: build_four_cycles() failed in menu()");
	  print_graph_skeleton(stdout,G);
	  destroy_graph(&G,NULL,NULL);
	  break;

	case '3':
	  /******************************************************
	   * Test copy_adjacent
	   ******************************************************/

	  /* Load K4 */
	  if(build_K4(&G)==ERROR)
	    glr_error("Error:: build_K4() failed in menu()");

	  /* Copy and print the adjacent list of all vertices */
	  for(pv=G;pv!=NULL;pv=NEXT(pv)) 
	    {
	      init_list(&adjacent);
	      if(copy_adjacent(pv,&adjacent)==ERROR)
		glr_error("Error:: copy_adjacent failed");
	      printf("Adj. vertices of vertex %d: ", VERTEX_NUMBER(pv)); 
	      for(curr=adjacent;curr!=NULL;curr=NEXT(curr))
		{
		  printf("%d ", VERTEX_NUMBER(curr));
		}
	      printf("\n");
	      destroy_list(&adjacent,NULL);
	    }
	
	  /* Destroy the graph */
	  destroy_graph(&G,free_specific_vertex_data,free_specific_edge_data);

	  break;

	case '4':
	  /******************************************************
	   * Test duplicate_graph
	   ******************************************************/
	  /* Load the graph */
	  if(build_K4(&G)==ERROR)
	    glr_error("Error:: build_K4() failed in menu()");
	  
	  /* Duplicate and print it */
	  err = duplicate_graph(G,&Gdup,copy_vertex_data,copy_edge_data);
	  if(err==ERROR)
	    glr_error("Error:: duplicate_graph() failed in menu()");
	  print_graph(stdout,Gdup,print_vertex_data,print_edge_data);

	  /* destroy both graphs */
	  destroy_graph(&G,free_specific_vertex_data,free_specific_edge_data);
	  destroy_graph(&Gdup,free_specific_vertex_data,free_specific_edge_data);

	  break;

	case '5':
	  /*******************************************************
	   * Test print_graph
	   *******************************************************/
	  /* Load the graph */
	  if(build_K4(&G)==ERROR)
	    glr_error("Error:: build_K4() failed in menu()");

	  print_graph(stdout,G,print_vertex_data,print_edge_data);
	  destroy_graph(&G,free_specific_vertex_data,free_specific_edge_data);

	  break;

	case '6':
	  /********************************************************
	   * Test destroy_graph 
	   * (Use top to monitor possible memory leakages)
	   ********************************************************/
	  for(i=0;i<1000000;i++)
	    {
	      build_K4(&G);
	      destroy_graph(&G,free_specific_vertex_data,free_specific_edge_data);
	      printf("Graph loaded and destroyed %d times\n", i);
	    }
	  break;

	case '7':
	  /********************************************************
	   * Test detect_fundamental_cycles
	   ********************************************************/
	  /* Build and print K4 */
	  build_K4(&G);
	  print_graph(stdout,G,print_vertex_data,print_edge_data);

	  /* Detect cycles, print them, destroy them */
	  init_list(&cycles);
	  detect_fundamental_cycles(G,&cycles,NULL);
	  print_list_cycles(stdout,cycles);
	  destroy_list(&cycles,free_cycles_data);

	  /* Print K4 (see how the labels and sense fields of each vertex have changed */
	  print_graph(stdout,G,print_vertex_data,print_edge_data);

	  /* Print a graph analysis */
	  print_graph_analysis(stdout,G);

	  /* Destroy the graph */
	  destroy_graph(&G,free_specific_vertex_data,free_specific_edge_data);
	  break;
	case '8':
	  /********************************************************
	   * Test delete_vertex_and_edges
	   ********************************************************/
	  /* Build and print K4 */
	  build_K4(&G);
	  print_graph(stdout,G,print_vertex_data,print_edge_data);

	  /* Print a graph analysis */
	  print_graph_analysis(stdout,G);

	  /* Delete vertex "1" and print K4 again to see it disappears */
	  err = delete_vertex_and_edges(&G,1,free_specific_vertex_data,free_specific_edge_data);
	  if(err==ERROR)
	    glr_error("Errror: could not delete vertex and incident edges in menu()");
	  print_graph(stdout,G,print_vertex_data,print_edge_data);

	  /* Print a graph analysis */
	  print_graph_analysis(stdout,G);

	  /* Destroy the graph */
	  destroy_graph(&G,free_specific_vertex_data,free_specific_edge_data);
	  break;
	case '9':
	  {
	    /********************************************************
	     * Test traverse
	     ********************************************************/

	    list roots;	  

	    /* Build and print the graph */
	    //build_K4(&G);
	    build_tree_plus_two_chords(&G);
	    print_graph_skeleton(stdout,G);

	    /* Traverse graph */
	    init_list(&roots);
	    err=insert(&roots,(generic_ptr)G);
	    if(err==ERROR)
	      glr_error("Error:: Failed to insert vertex in menu()");

	    traverse_graph(BF,roots,NULL,NULL,NULL,NULL,NULL);

	    /* Print the graph */
	    //print_graph(stdout,G,NULL,NULL);

	    /* Destroy the graphs and lists */
	    destroy_graph(&G,NULL,NULL);
	    destroy_list(&roots,NULL);
	    break;
	  }
	case 'a':	
	  {
	    /********************************************************
	     * Test breadth first
	     ********************************************************/

	    list roots, visited, chords;
	    generic_ptr output;

	    /* Build and print the graph */
	    //build_tree_plus_two_chords(&G);
	    build_tree_plus_two_chords(&G);
	    //build_K4(&G);	  
	    //build_four_cycles(&G);
	    print_graph_skeleton(stdout,G);
	    
	    init_list(&roots);
	    err=insert(&roots,(generic_ptr)G);
	    if(err==ERROR)
	      glr_error("Error:: Failed to insert vertex in menu()");

	    /* Traverse graph in breadth 1st order*/
	    breadth_first(roots,&visited,&chords,NULL,NULL,NULL,&output);

	    /* Print the graph */
	    //print_graph(stdout,G,NULL,NULL);

	    /* Print the lists visited and chords */
	    fprintf(stdout,"List of visited vertices is\n");
	    print_prolog_list(stdout,visited,print_vertex_identifyier);
	    fprintf(stdout,"\nList of chords found is\n");
	    print_prolog_list(stdout,chords,print_chord_data);

	    /* Destroy the graphs and lists */
	    destroy_graph(&G,NULL,NULL);
	    destroy_list(&roots,NULL);
	    destroy_list(&visited,NULL);
	    destroy_list(&chords,NULL);  // <---- remove its data too!!!!
	    break;
	  }
	case 'b':
	  {
	    /********************************************************
	     * Test coordenatize_subgraph
	     ********************************************************/

	    list roots;	  

	    /* Build and print the graph */
	    build_tree_plus_two_chords(&G);
	    print_graph_skeleton(stdout,G);

	    /* Traverse graph */
	    init_list(&roots);
	    err=insert(&roots,(generic_ptr)G);
	    if(err==ERROR)
	      glr_error("Error:: Failed to insert vertex in menu()");

	    coordenatize_subgraph(roots,NULL);

	    /* Print the graph */
	    print_graph(stdout,G,NULL,NULL);

	    /* Destroy the graphs and lists */
	    destroy_graph(&G,NULL,NULL);
	    destroy_list(&roots,NULL);
	    break;
	  }
	case '0':
	  printf("Exiting ...\n");
	  exit(0);
	  break;
	default:
	  printf("Bad option\n");
	}

      /* get rid of the carriage return still present in the buffer */
      getchar(); 
    } while(option!='0');
}
/*-----------------------------------------------------------------------------------------------*/
void print_node_vertex(FILE* fd, list curr)
{
  fprintf(fd, "%d", VERTEX_NUMBER(curr));
}
/*-----------------------------------------------------------------------------------------------*/
status build_four_cycles(graph* p_G)
/*
 * Builds a graph with four cycles.
 */
{
  int i;

  if(init_graph(p_G)==ERROR)
    glr_error("Error:: init_graph() failed in four_cycles()");

  /* Add all vertices */
  for(i=1; i<=13; i++)
    if(add_vertex(p_G, i, NULL)==ERROR)
      glr_error("Error:: add_vertex() failed in four_cycles()");

  /* Add all edges */
  if(add_edge(*p_G, 1, 2, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in four_cycles()");
  if(add_edge(*p_G, 2, 3, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in four_cycles()");
  if(add_edge(*p_G, 3, 4, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in four_cycles()");  
  if(add_edge(*p_G, 4, 5, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in four_cycles()");
  if(add_edge(*p_G, 5, 6, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in four_cycles()");
  if(add_edge(*p_G, 6, 7, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in four_cycles()");
  if(add_edge(*p_G, 7, 1, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in four_cycles()");
  if(add_edge(*p_G, 5, 8, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in four_cycles()");
  if(add_edge(*p_G, 8, 9, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in four_cycles()");
  if(add_edge(*p_G, 9, 10, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in four_cycles()");
  if(add_edge(*p_G, 10, 6, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in four_cycles()");
  if(add_edge(*p_G, 9, 11, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in four_cycles()");
  if(add_edge(*p_G, 11,12, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in four_cycles()");
  if(add_edge(*p_G, 12, 7, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in four_cycles()");
  if(add_edge(*p_G, 12, 13, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in four_cycles()");
  if(add_edge(*p_G, 13, 1, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in four_cycles()");

  return(OK);
}
/*--------------------------------------------------------------------*/
status build_tree_plus_two_chords(graph* p_G)
/*
 * Builds a (balanced) binary tree (with three levels) plus two chords
 */
{
  int i;

  /* init graph */
  if(init_graph(p_G)==ERROR)
    glr_error("Error:: init_graph() failed in build_tree_plus_two_chords()");

  /* Add all vertices */
  for(i=1; i<=7; i++)
    if(add_vertex(p_G, i, NULL)==ERROR)
      glr_error("Error:: add_vertex() failed in build_tree_plus_two_chords");
  
  /* Add all edges */
  if(add_edge(*p_G, 1, 2, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in build_tree_plus_two_chords()");
  if(add_edge(*p_G, 1, 3, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in build_tree_plus_two_chords()");
  if(add_edge(*p_G, 2, 4, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in build_tree_plus_two_chords()");  
  if(add_edge(*p_G, 2, 5, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in build_tree_plus_two_chords()");
  if(add_edge(*p_G, 3, 6, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in build_tree_plus_two_chords()");
  if(add_edge(*p_G, 3, 7, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in build_tree_plus_two_chords()");
  if(add_edge(*p_G, 1, 5, NULL)==ERROR)
    glr_error("Error:: add_edge() failed in build_tree_plus_two_chords()");

/*   if(add_edge(*p_G, 4, 6, NULL)==ERROR) */
/*     glr_error("Error:: add_edge() failed in build_tree_plus_two_chords()"); */
/*   if(add_edge(*p_G, 5, 7, NULL)==ERROR) */
/*     glr_error("Error:: add_edge() failed in build_tree_plus_two_chords()"); */
  
  return(OK);
}
/*--------------------------------------------------------------------*/
status build_K4(graph* p_G)
/*
 * Builds a K4 graph (the complete graph of four vertices).
 * This also exemplifies how to store specific data in each 
 * vertex or edge. 
 */
{
  int i;
  my_specific_vertex_data *svd;
  my_specific_edge_data *sed[6];

  if(init_graph(p_G)==ERROR)
    glr_error("Error:: init_graph() failed in build_K4()");

  /* Add all vertices */
  for(i=1; i<=4; i++)
    {
      /* Memory allocation and assignment of specific vertex data */
      svd = (my_specific_vertex_data*)malloc(sizeof(my_specific_vertex_data));
      if (svd == NULL)
	glr_error("Error:: memory allocation failed in build_K4()");
      svd->potential = 10.0;
      sprintf(svd->name, "I'm a vertex");  
  
      /* Vertex addition */
      if(add_vertex(p_G, i, (generic_ptr)svd)==ERROR)
	glr_error("Error:: add_vertex() failed in build_K4");
    }

  /* Memory allocation and assignment of specific edge data */
  for(i=0;i<6;i++)
    {
      sed[i] = (my_specific_edge_data*)malloc(sizeof(my_specific_edge_data));
      if (sed[i] == NULL)
	glr_error("Error:: memory allocation failed in build_K4()");
      sed[i]->flow=1000.0;
      sprintf(sed[i]->name, "I'm an edge");  
    }

  /* Add all edges */
  if(add_edge(*p_G, 1, 2, (generic_ptr)sed[0])==ERROR)
    glr_error("Error:: add_edge() failed in build_K4()");
  if(add_edge(*p_G, 2, 3, (generic_ptr)sed[1])==ERROR)
    glr_error("Error:: add_edge() failed in build_K4()");
  if(add_edge(*p_G, 3, 4, (generic_ptr)sed[2])==ERROR)
    glr_error("Error:: add_edge() failed in build_K4()");  
  if(add_edge(*p_G, 1, 4, (generic_ptr)sed[3])==ERROR)
    glr_error("Error:: add_edge() failed in build_K4()");
  if(add_edge(*p_G, 1, 3, (generic_ptr)sed[4])==ERROR)
    glr_error("Error:: add_edge() failed in build_K4()");
  if(add_edge(*p_G, 2, 4, (generic_ptr)sed[5])==ERROR)
    glr_error("Error:: add_edge() failed in build_K4()");
  
  return(OK);
}
/*-----------------------------------------------------------------------------------------------*/
status print_vertex_data(FILE* fd, generic_ptr svd)
{
  my_specific_vertex_data* msvd;

  if(fd==NULL || svd==NULL)
    return(ERROR);

  msvd = (my_specific_vertex_data*)svd;  
  fprintf(fd, "\t\tPotential = %.2f\n", msvd->potential);
  fprintf(fd, "\t\tName = %s\n", msvd->name);

  return(OK);
}
/*-----------------------------------------------------------------------------------------------*/
status print_edge_data(FILE* fd, generic_ptr sed)
{
  my_specific_edge_data* msed;

  if(fd==NULL || sed==NULL)
    return(ERROR);

  msed = (my_specific_edge_data*)sed;
  fprintf(fd, "\t\t\t\tFlow = %.2f\n", msed->flow);
  fprintf(fd, "\t\t\t\tName = %s\n", msed->name);

  return(OK);
}
/*-----------------------------------------------------------------------------------------------*/
status copy_vertex_data(generic_ptr olddata, generic_ptr* newdata)
{
  my_specific_vertex_data *svd_old, *svd_new;

  if(olddata==NULL)
    return(ERROR);

  svd_old = (my_specific_vertex_data*)olddata; 
  svd_new = (my_specific_vertex_data*)malloc(sizeof(my_specific_vertex_data));
  if(svd_new==NULL)
    return(ERROR);

  svd_new->potential = svd_old->potential;
  sprintf(svd_new->name,"%s",svd_old->name);

  *newdata = (generic_ptr)svd_new;
 
  return(OK);
}
/*-----------------------------------------------------------------------------------------------*/
status copy_edge_data(generic_ptr olddata, generic_ptr* newdata)
{
  my_specific_edge_data *sed_old, *sed_new;

  if(olddata==NULL)
    return(ERROR);

  sed_old = (my_specific_edge_data*)olddata; 
  sed_new = (my_specific_edge_data*)malloc(sizeof(my_specific_edge_data));
  if(sed_new==NULL)
    return(ERROR);

  sed_new->flow = sed_old->flow;
  sprintf(sed_new->name,"%s",sed_old->name);

  *newdata = (generic_ptr)sed_new;
 
  return(OK);
}
/*-----------------------------------------------------------------------------------------------*/
void free_specific_vertex_data(generic_ptr data)
{
  my_specific_vertex_data* msvd;

  if(data==NULL)
    glr_error("Error:: attempting to delete empty data in free_specific_vertex_data()");

  msvd = (my_specific_vertex_data*)(data);
  free(msvd);
}
/*-----------------------------------------------------------------------------------------------*/
void free_specific_edge_data(generic_ptr data)
{
  my_specific_edge_data* msed;

  if(data==NULL)
    glr_error("Error:: attempting to delete empty data in free_specific_vertex_data()");

  msed = (my_specific_edge_data*)(data);
  free(msed);
}
/*-----------------------------------------------------------------------------------------------*/
int main(void)
{
    menu();
    return(0);
}
/*-----------------------------------------------------------------------------------------------*/