/*****************************************
 * file: graph.h
 * author: 
 * data : 15:00 2006-11-15
 * copyright: free software & hardware
 * to-do: define some struct and function to handle the graph
 *****************************************/

#ifndef _GRAPH_
#define _GRAPH_
/* define the max number of vertexs in the graph
 * see the problem's request
 */
#define MAX_SIZE 50
/* define the struct of graph
 * we using a adjacency matrix to display a graph
 * the number of graph's vertexs must small then MAX_SIZE
 */
typedef struct _graph
{
	unsigned char adj[MAX_SIZE][MAX_SIZE];	/* the adjacency martix */
	size_t size;	/* how many vertex in the graph */
}graph;
/* init the graph 
 * set adj[][] = {0}
 * set size = 0
 */
int init_graph(graph *g);
/* copy the graph s to graph d
 */
int copy_graph(graph *s,graph *d);
/* 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);
/* reads the graph structure and prints the graph in the following format: 
 *		v-- a list of its adjacent vertices 
 */
int print_graph(graph *g);	
/* 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.
 */
int shortest_path(graph *g,unsigned int s,unsigned int d);
/* to test the graph g if it is connected 
 * in an other word, if it is a forrest
 */
int is_connected(graph *g);
/* to test the graph if it is a tree
 */
int is_tree(graph *g);
/* to test the graph if it has a cycle,
 * if it has print it
 * the argument "print" tell the function if you want print the cycle
 *		if print = 1 the cycle will print 
 *		else do not print it
 */
int has_cycle(graph *g, int print);
#endif	/* _GRAPH_ */