#ifndef GLRH
#define GLRH

/*************************************************************************************************
 * GLR 1.0 - Graph Library
 *
 * Author:
 *
 *     Lluís Ros (c) 1995-2007
 *     Institut de Robōtica i Informātica Industrial (CSIC-UPC)
 *     Llorens Artigas 4-6, 2a planta
 *     08028 Barcelona
 *     Web: http://www-iri.upc.es/people/ros
 *     E-mail: llros@iri.upc.es
 *
 * What is GLR?
 *
 *     GLR is a library of functions to handle undirected graphs. The 
 *     implementation of GLR's functions makes use of many low level
 *     functions included in the companion library LLR. Mainly, the 
 *     routines in GLR allow creating/destroying the graph, traversing it
 *     in depth-first or breadth-first order, and finding the set of 
 *     fundamental cycles. Complementary routines are included to print 
 *     the graph and analyze it, as documented below.
 *
 * Associated files:
 *
 *     glr.c glr.h llr.c llr.h
 *
 * Conditions of use:
 *
 *     The following software may be used by anyone (hereafter the "user") agreeing with the 
 *     following conditions:
 *
 *     1. The user will only use the software for nonprofit, nonmilitary purposes. 
 *        Any commercial use of this software requires the obtention of an appropriate 
 *        software license jointly issued by the author and the Institut de Robōtica 
 *        i Informātica Industrial (UPC/CSIC). Should you be interested in such license,
 *        please contact the author at the address above.
 *     2. On any publication reporting results using this software, the user commits
 *        to make a reference to the software, as follows:
 *
 *          L. Ros, "Graph Library 1.0, A software library to handle polymorphic graphs".
 *          Institut de Robōtica i Informātica Industrial (CSIC/UPC), Barcelona, Spain. 
 *          Available through http://www-iri.upc.es/people/ros
 *
 *     3. The user will report the software's author about any trouble he meets in the use of
 *        this software. The author will remove bugs, if any, at his earliest convenience.
 *     4. The author assumes no responsibility for any trouble or damage caused by the
 *        user when using this software for any purpose.
 *     5. The user will notify the author (to the address given above) that she will use the 
 *        software. In her notification the user is asked to please identify herself, to state 
 *        she accepts these conditions, and briefly report the purpose for which the software 
 *        will be used.
 *  
 * A note on the programming style:
 *
 *     Although all routines are by myself, the programming style follows 
 *     the book by Jeffrey Esakov & Tom Weiss "Data Structures, an Advanced 
 *     Approach Using C". The code in GLR implements most of this book's 
 *     primitive operations over the 'graph abstract data type' and many 
 *     others I added. The main differences between my implementation and 
 *     Esakov and Weiss's are as follows:
 *     
 *        1 - I do not assume a static vertex set. I.e., you may add or remove 
 *            vertices from the graph as the computations go on. To this end, the 
 *            set of vertices has been stored in a dynamic list rather than in 
 *            a statically-dimensioned vector. 
 *        2 - I allow vertices to have the label you want (in the book they 
 *            must be numbered from 1 to n). 
 *        3 - Both edges and vertices may store information (only edges 
 *            can in the book).
 *        4 - The user can provide routines to decide whether a given edge is 
 *            traversable (see pointer p_is_reachable below) by the graph traverse
 *            (Section 3) and cycle search (Section 4) functions.
 *
 * The functions are organized into the following sections:
 *
 *    Section 1 - Graph constructors
 *        Functions to construct a graph, and add individual vertices and edges
 *    Section 2 - Graph destructors
 *        Functions to destroy a graph, and delete individual vertices and edges
 *    Section 3 - Graph traverse functions
 *        Functions to perform actions on vertices/edges while traversing the graph
 *    Section 4 - Detection of fundamental cycles and connected components
 *        Functions to compute a fundamental cycle basis and detect connected components
 *    Section 5 - Graph analysis functions
 *        Functions to analyze the graph (count #vertices, #edges, #components, #cycles,...)
 *    Section 6 - Graph printing and drawing functions
 *        Functions to print the graph, and related data structures
 *    Section 7 - Miscelaneous functions
 *        Miscelaneous functions
 *
 * Acknowledgements: 
 *
 *    Special thanks to Pablo Jimenez, Manel Guerris, Albert Castellet, Gorka Bonals, and 
 *    Josep M. Porta for using GLR on different contexts, and for suggesting improvements 
 *    to the code.
 *
 ************************************************************************************************/

#include "general.h"
#include "llr.h"

/********************************************************************
 *  graph type
 ********************************************************************/
typedef list graph;  /* A graph is simply a list of vertices */

/********************************************************************
 *  graph_vertex and vertex_data types.
 ********************************************************************/

typedef list graph_vertex;       // Graph vertex data type
typedef list graph_edge;         // Graph_edge data type
typedef unsigned int vertex_id;  // Vertex_id data type

typedef struct
{
  vertex_id vertex_number;       // Numerical identifyier of the vertex 
  graph_vertex parent;           // Parent vertex during a traversal
  graph_edge emanating;          // List of edges emanating from the vertex 
  boolean visited;               // Visited flag used in traversal routines 
  int status;                    // Multipurpose label, e.g. used when traversing the graph 
  list labels;                   // Labels of fundamental cycles through this vertex 
  double x, y;                   // (x,y) coords of the vertex (for eventual plots) 
  generic_ptr specific_data;     // Pointer to the data stored in the vertex 
} vertex_data;

/* 
 * Accessor macros of a vertex 
 */

#define VERTEX_NUMBER(V)        (((vertex_data*)DATA(V))->vertex_number)
#define PARENT(V)               (((vertex_data*)DATA(V))->parent)
#define EMANATING(V)	        (((vertex_data*)DATA(V))->emanating)
#define VISITED(V)              (((vertex_data*)DATA(V))->visited)
#define STATUS(V)               (((vertex_data*)DATA(V))->status)
#define THISLABEL(L)            (*((int*)DATA(L)))
#define LABELS(V)               (((vertex_data*)DATA(V))->labels)
#define Xcoord(V)               (((vertex_data*)DATA(V))->x)
#define Ycoord(V)               (((vertex_data*)DATA(V))->y)
#define SPECIFIC_VERTEX_DATA(V) (((vertex_data*)DATA(V))->specific_data)

/********************************************************************
 *  edge_data type
 ********************************************************************/
typedef struct{
  vertex_id vertex_ini;     /* Vertex id of the initial vertex of this edge */
  vertex_id vertex_number;  /* Vertex id of the final vertex of this edge */
  list vertex_ptr;          /* Vertex pointer of the final vertex of this edge */
  int copy;                 /* 1 or 2, depending of whether this is the (i,j) or 
			     * the (j,i) copy of the edge. See the function 
			     * add_edge_with_ptrs. 
                             */ 
  int sense;                 /* Sense of a vertex during a depth-1st seach 
                              * (UP, DOWN, or NOSENSE), as defined below. 
			      */
  list labels;               /* Labels of fundamental cycles through this edge */
  generic_ptr specific_data; /* Pointer to the data stored in the edge */
} edge_data;

/* 
 * Accessor macros of an edge
 */

#define SOURCE(E)             (((edge_data*)DATA(E))->vertex_ini)
#define DESTINATION(E)        (((edge_data*)DATA(E))->vertex_number)
#define VERTEX_PTR(E)         (((edge_data*)DATA(E))->vertex_ptr)
#define COPY(E)               (((edge_data*)DATA(E))->copy)
#define SENSE(E)              (((edge_data*)DATA(E))->sense)
#define SPECIFIC_EDGE_DATA(E) (((edge_data*)DATA(E))->specific_data)
#define EDGE_LABELS(E)        (((edge_data*)DATA(E))->labels)

/********************************************************************
 *  Traversal data type
 ********************************************************************/
typedef struct {
  graph_vertex vertex_ptr; /* Pointer to the traversed vertex in the graph */
  graph_vertex parent_ptr; /* Pointer to the parent of the vertex */
  graph_edge edge_ptr;     /* Pointer to the edge they define */
} traversed_vertex_data;

#define TRAVERSED_VTX_PTR    (((traversed_vertex_data*)DATA(C))->vertex_ptr)
#define TRAVERSED_VTX_PARENT (((traversed_vertex_data*)DATA(C))->parent_ptr)
#define TRAVERSED_VTX_EDGE   (((traversed_vertex_data*)DATA(C))->edge_ptr)

/********************************************************************
 *  Chord data type
 ********************************************************************/
typedef struct {
  graph_vertex chord_vertex1; /* One vertex of the chord */
  graph_vertex chord_vertex2; /* The other vertex of the chord */
  graph_edge chord_edge;      /* label of this cycle */
} chord_data;

#define CHORD_VERTEX1(C) (((chord_data*)DATA(C))->chord_vertex1)
#define CHORD_VERTEX2(C) (((chord_data*)DATA(C))->chord_vertex2)
#define CHORD_EDGE(C)    (((chord_data*)DATA(C))->chord_edge)


/********************************************************************
 *  Cycle_data type
 ********************************************************************/
typedef struct {
  list vertices; /* list of vertices of the cycle */
  list edges;    /* list of edges of the cycle */
  int label;     /* label of this cycle */
} cycle_data;
  
#define CYC_VERTICES(C) (((cycle_data*)DATA(C))->vertices)
#define CYC_EDGES(C)    (((cycle_data*)DATA(C))->edges)
#define CYC_LABEL(C)    (((cycle_data*)DATA(C))->label)

/********************************************************************
 *  Other macros
 ********************************************************************/

#define UP 1     
#define DOWN 0
#define NOSENSE -1

/* Possible status for a vertex (in graph traverse functions) */
#define NOLABEL    0    
#define INFRONT    1
#define PROCESSED  2

/* end condition for the up() function */
#define BY_NODE_ID 1
#define BY_LABEL 0

/* labeling mode for up() */
#define DOLABEL 1
#define DONTLABEL 0

/* Graph traversal modes: BF="breadth-first" DF="depth first" */
#define BF 1
#define DF 2

/* x and y margins and gaps when drawing the graph */
#define XMARGIN 0.0
#define YMARGIN 0.0
#define XGAP 12.0
#define YGAP 18.0


/********************************************************************
 *  Primitive operations of the "graph" abstract data type
 ********************************************************************/

/*
 * Section 1 - Graph constructors
 */

status  init_graph(graph *p_G);
status  add_vertex(graph* p_G, vertex_id vertex_number, generic_ptr specific_data);
status  append_vertex(graph* p_G, vertex_id vertex_number, generic_ptr specific_data);
status  insert_vertex(graph* p_G, vertex_id vertex_number, generic_ptr specific_data);
status  add_edge(graph G, vertex_id vertex1, vertex_id vertex2, generic_ptr specific_data);
status  add_edge_with_pointers(graph_vertex pv1, graph_vertex pv2, generic_ptr specific_data);
status  edge_append(list* p_L, vertex_id vertex_ini, vertex_id vertex_number, 
		    generic_ptr specific_data, graph_vertex vertex_ptr, int copy);
status  duplicate_graph(graph G1, graph* G2, 
			status (*p_copy_vertex)(generic_ptr,generic_ptr*), 
			status (*p_copy_edge)(generic_ptr,generic_ptr*));

/*
 * Section 2 - Graph destructors
 */

void   destroy_graph(graph* p_G, 
		     void (*p_free_specific_vertex_data)(generic_ptr),
		     void (*p_free_specific_edge_data)(generic_ptr));
status destroy_graph_specific_data(graph G, 
				   void (*p_free_specific_vertex_data)(generic_ptr),
				   void (*p_free_specific_edge_data)(generic_ptr));
status delete_vertex(graph* p_G, vertex_id vertex_number, 
		     void (*p_free_specific_edge_data)(generic_ptr));
status delete_vertex_with_pointer(graph* p_G, graph_vertex vertex_ptr, 
				  void (*p_free_specific_edge_data)(generic_ptr));
status delete_vertex_and_edges(graph* p_G, vertex_id vertex_number, 
			       void (*p_free_specific_vertex_data)(generic_ptr),
			       void (*p_free_specific_edge_data)(generic_ptr));
status delete_vertex_and_edges_with_pointer(graph* p_G, graph_vertex vertex_ptr,
					    void (*p_free_specific_vertex_data)(generic_ptr),
					    void (*p_free_specific_edge_data)(generic_ptr));
status delete_edge(graph G, vertex_id vid1, vertex_id vid2, 
		   void (*p_free_specific_edge_data)(generic_ptr));
status delete_edge_with_pointers(graph_vertex origin1, graph_edge destin1, 
				 graph_vertex origin2, graph_edge destin2, 
				 void (*p_free_specific_edge_data)(generic_ptr));


/*
 * Section 3 - Graph traverse functions
 */
void traverse_graph(int mode, list roots,
		    boolean (*p_is_reachable)(graph_edge,graph_vertex),
		    status  (*p_fwd_process)(graph_vertex,graph_vertex,generic_ptr*,generic_ptr*),
		    status  (*p_bwd_process)(graph_vertex,graph_vertex,generic_ptr*,generic_ptr*),
		    generic_ptr* input,
		    generic_ptr* output);

void traverse_graph_recursive(int mode, list* front,
			      boolean (*p_is_reachable)(graph_edge,graph_vertex),
			      status  (*p_fwd_process)(graph_vertex,graph_vertex,generic_ptr*,generic_ptr*),
			      status  (*p_bwd_process)(graph_vertex,graph_vertex,generic_ptr*,generic_ptr*),
			      generic_ptr* input,
			      generic_ptr* output);

void breadth_first(list roots, list* visited, list* chords, 
		   boolean (*p_is_reachable)(graph_edge,graph_vertex),
		   status  (*p_fwd_process)(graph_vertex,graph_vertex,generic_ptr*,generic_ptr*),
		   generic_ptr* input,
		   generic_ptr* output);
status  simply_visit_all(graph G);
status  depth_first(graph G, graph_vertex vertex_ptr, status (*p_visit_f)(list));
status  depth_first_vertices_edges(graph G, graph_vertex vertex_ptr, 
				   boolean (*p_is_reachable)(list,list),
				   status  (*p_action_vertex_before)(list),
				   status  (*p_action_edge_before)(list,list,list),
				   status  (*p_action_edge_after)(list,list,list));

status  mark_all_unvisited(graph G);
status  mark_senses_down(graph G, graph_vertex vertex_ptr, boolean (*p_is_reachable)(list,list) );
status  mark_senses_down2(graph G, graph_vertex vertex_ptr, boolean (*p_is_reachable)(list,list) );
void    clear_all_senses(graph G);

/*
 * Section 4 - Detection of fundamental cycles and connected components
 */

status  detect_fundamental_cycles(graph G, list* cycles,boolean (*p_is_reachable)(list,list)); 
void    free_cycles_data(generic_ptr data);
status  connected_components(graph G, list* components);

/*
 * Section 5 - Graph analysis functions
 */

void    analyze_graph(graph G, FILE* fd);
int     count_vertices(graph G);
int     count_edges(graph G);
int     degree(graph_vertex vertex_ptr);
status  count_vertices_edges_component(list component, int* nvertices, int* nedges);

/*
 * Section 6 - Graph printing and drawing functions
 */
void print_graph(FILE* fd, graph G, 
		 status(*p_print_vertex)(FILE*, generic_ptr), 
		 status(*p_print_edge)(FILE*, generic_ptr));
void print_graph_skeleton(FILE* fd, graph G);
void print_graph_analysis(FILE* fd, graph G);
void print_label_id(FILE* fd, list label_ptr);
void print_vertex_number(FILE* fd, graph_vertex vertex_ptr);  /* <----- to remove it in the future versions */
void print_vertex_identifyier(FILE* fd, list node_of_list);
void print_chord_data(FILE* fd, list node_of_list);
void print_list_vertices(FILE* fd, list vertices);
void print_list_cycles(FILE* fd, list cycles);
void coordenatize_subgraph(list roots, boolean (*p_is_reachable)(list,list));
void reset_coordenatize_vertex();
status coordenatize_vertex(graph_vertex vertex_ptr, graph_vertex parent_ptr, 
			 generic_ptr* input, generic_ptr* output);

/*
 * Section 7 - Miscelaneous functions
 */

boolean empty_graph(graph G);
status  copy_roots_to_front(generic_ptr data_roots, generic_ptr* pdata_front);
status  copy_adjacent(graph_vertex pv, list* adjacent);
int     cmp_vertex(generic_ptr p_datapointer1, generic_ptr p_datapointer2);
list    find_vertex(graph G, vertex_id vertex_number);
list    find_destin(list Edges, vertex_id vertex_number);
list    find_destin_with_pointer(list Edges, graph_vertex pv);
void    find_edge_vertices(graph_edge pe, graph_vertex* pv1, graph_vertex* pv2);
void    find_chords(list roots, list* chords, boolean (*p_is_reachable)(graph_edge,graph_vertex));
void    glr_error(char* error);
status  dummy_visit(graph_vertex vertex_ptr, graph_vertex parent_vertex_ptr,
		    generic_ptr* input, generic_ptr* output);
boolean edge_is_labelled(graph_edge e, int i);
void    label_edge(graph_edge e, int l);

#endif /* GLRH */