/*****************************************
 * file: graph.cpp
 * author: 
 * data : 15:00 2006-11-15
 * copyright: free software & hardware
 * to-do: the implamtation of the graph and it's method
 *****************************************/
#include <stdio.h>
#ifdef WIN32	/* if windows we can use the assert() function */
#	include <assert.h>
#else 
#	define assert(a)
#endif
#include <list>		/* for using the std class list */
#include <vector>	/* for using the std vector class */
#include "graph.h"

/* init the graph 
 * set adj[][] = {0}
 * set size = 0
 */
int init_graph(graph *g)
{
  int i,j;
  assert(g != NULL);
  g->size = 0;
  for(i=0;i<MAX_SIZE;i++)
    for(j=0;j<MAX_SIZE;j++)
      g->adj[i][j] = 0;
  return 0;
}

/* copy the graph s to graph d
 */
int copy_graph(graph *s,graph *d)
{
  d->size = s->size;
  for(size_t i=0;i<s->size; i++){
    for(size_t j=0; j < s->size ; j++){
      d->adj[i][j] = s->adj[i][j];
    }
  }
  return 0;
}
/* read a graph from "graph.txt"
 * Each row of the file represents a link connecting the node on the first and second columns
 */
int read_graph(graph *g)
{
  FILE *fd;
  unsigned int src,dst;
	
  assert(g != NULL);
  fd = fopen("graph.txt","r");
  if( -1 == (int)fd ){
    return -1;	/* error while open the file */
  }
  while( fscanf(fd,"%d %d",&src,&dst) != EOF ){	/* read from the file line by line */
    if(src >= MAX_SIZE || dst >= MAX_SIZE){
      return -1;	/* the number of the bertex must small then 50 */
    }
    if(src >= g->size) g->size = src + 1;	/* get the size */
    if(dst >= g->size) g->size = dst + 1;
    g->adj[src][dst] = 1;	/* so there is a connection between src and dst */
    g->adj[dst][src] = 1;	/* because it is a undirected graph */
  }
  fclose(fd);
  return 0;	/* success return 0 */
}
/* reads the graph structure and prints the graph in the following format: 
 *		v-- a list of its adjacent vertices 
 */
int print_graph(graph *g)
{
  size_t i,j;
	
  assert(g != NULL);
  for(j=0;j<g->size;j++){
    printf("%d -- ",j);
    for(i=0;i<g->size;i++){
      if(g->adj[j][i])	/* if v--i then g->adj[v][i] will equ to 1 */
	printf("%d,",i);
    }
    printf("\n");
  }
  return 0;
}
/* takes a graph G, a source node s, and a destination d as parameters, 
 * and returns the length of the shortest path from s to d. 
 * Bonus:Print the node sequence of the shortest path.
 */
typedef struct _node
{
  int index;			/* vertex index in the graph */
  int father;			/* father's index in the array */
} node;
int shortest_path(graph *g,unsigned int s,unsigned int d) /* use BFS */
{
  std::vector<node> bfs_array;
  unsigned int now_point = 0;		/* the element's index in the bfs_array */
  int is_visited[MAX_SIZE] = {0};	/* the flag array to notify if the vertex has visited */

  assert(g != NULL);
  if(s < 0 || s >= g->size || d < 0 || d >= g->size){ /* use the wrong argument */
    return -1;
  }
  while(1){
    node n;			/* the temp node,use for operation */
    if(bfs_array.size() == 0){	/* have no element we put the first one in it */
      n.index = s;		/* the first element is source vertex "s" */
      n.father = -1;		/* have no father */
      bfs_array.push_back(n);	/* put into array */
      is_visited[s] = 1;	/* now vertex "s" is visited */
      continue;
    }
    for(unsigned int j = 0; j < g->size; j ++){ /* put each one connected to vertex into the array  */
      int vertex = bfs_array[now_point].index;
      if(g->adj[vertex][j] == 1 && is_visited[j] == 0){ /* there is a connection between vertex and j and j has'nt been visited */
	n.index = j;
	n.father = now_point;	/* j's father is vertex, and vertex's index number is now_point */
	bfs_array.push_back(n);
	is_visited[j] = 1;	/* j has been visited */
	if(j == d){
	  now_point = bfs_array.size() - 1 ;
	  goto FINDED;	/* arrive at d!!! */
	}
      }
    }
    now_point ++;
    if(now_point >= bfs_array.size()){ /* there is no element remain */
      break;
    }
  }
  return -1;			/* s not connected with d return -1 */

 FINDED:			/* if s can arrive at d then do the following things */
  int len = 0;
  while(bfs_array[now_point].father != -1 && bfs_array[now_point].index != s){ // print the path one by one
    printf("%d----",bfs_array[now_point].index);
    now_point = bfs_array[now_point].father;
    len ++;	
  }
  printf("%d\n",bfs_array[now_point].index);
  return len;	/* return the length of the path */
}
/* to test the graph g if it is connected 
 * in an other word, if it is a forest
 *  use the algorthm warshall, see the book "introduction to the design & analysis of algorithms"
 */
int is_connected(graph *g)
{
  unsigned int i,j,k;
  graph tmp;

  assert(g != NULL);
  copy_graph (g, &tmp);
  for(k = 0; k < tmp.size ; k++)
    for(i = 0 ; i < tmp.size ; i++)
      for(j = 0 ; j < tmp.size ; j++){
	if(tmp.adj[i][j] == 1) continue;
	if(tmp.adj [i][k] == 1 && tmp.adj [k][j] == 1){
	  tmp.adj [i][j] = 1;
	}
      }
  for(i = 0; i< tmp.size; i++)	/* if the elements in tmp matrix are all 1s then it is connected */
    for(j = 0; j < tmp.size; j++){
      if(tmp.adj [i][j] == 0) return 0;
    }
  return 1;
}
/* to test the graph if it is a tree
 */
int is_tree(graph *g)
{
  assert (g != NULL);
  if(is_connected(g) && !has_cycle(g,0)) /* if the graph is connect and has no cycle then it is a tree */
    return 1;
  return 0;
}
/* to test the graph if it has a cycle,
 * if it has print it
 */
int has_cycle(graph *g,int print)
{
  std::vector<node> bfs_array;
  unsigned int i,now_point = 0;		/* the element's index in the bfs_array */
  int is_visited[MAX_SIZE] = {0};	/* the flag array the notify if the vertex has visited */
  int result = 0;

  while(1){
    node n;			/* the temp node,use for operation */
    if(bfs_array.size() == 0){	/* have no element we put the first one in it */
      for(i=0; i<g->size; i++)
	if(is_visited[i] == 0){
	  n.index = i;		/* the first element is source vertex "s" */
	  n.father = -1;		/* have no father */
	  is_visited[i] = 1;	/* now vertex "s" is visited */
	  bfs_array.push_back(n);	/* put into array */
	  break;
	}
      if(bfs_array.size() == 0) return result;
      continue;
    }
    for(unsigned int j = 0; j < g->size; j ++){ /* put each one connected to vertex into the array  */
      int vertex = bfs_array[now_point].index;
      if(g->adj[vertex][j] == 1 && is_visited[j] == 0){ /* there is a connection between vertex and j and j has'nt been visited */
	n.index = j;
	n.father = now_point;	/* j's father is vertex, and vertex's index number is now_point */
	bfs_array.push_back(n);
	is_visited[j] = 1;	/* j has been visited */
      } else if(g->adj[vertex][j] == 1 && is_visited[j] == 1){
	if(j != bfs_array[now_point].father){ /* there is a cycle */
	  result = 1;
	  if(print == 1){	/* print the cycle */
	    printf("%d",j);
	    int tmp_point = now_point;
	    while(g->adj [ bfs_array[tmp_point].index ][j]  != 1 || tmp_point == now_point){
	      printf ("----%d",bfs_array[tmp_point].index);
	      tmp_point = bfs_array[tmp_point].father;
	    }
	    printf ("----%d",bfs_array[tmp_point].index);
	    printf("----%d\n",j);
	  }
	}
      }
    }
    now_point ++;
    if(now_point >= bfs_array.size()){ /* there is no element remain */
      bfs_array.resize(0);
    }
  }
  return result;			/* s not connected with d return -1 */
}