/*
This file implements an undirected graph structure.
Copyright (C) 2004 The University of Texas at Austin

This program is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your option)
any later version.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc., 59
Temple Place - Suite 330, Boston, MA 02111-1307, USA.

Email: usman@cs.njit.edu
Mail: Usman Roshan, Department of Computer Sciences, NJIT-CCS, Computer
Science Department, GITC 4400, University Heights, Newark, NJ 07102
*/
/* Implemented as a doubly linked list of nodes and edges */
/*
 * ! \file ugraph.h \brief Contains definitions for an undirected graph
 * structure
 */

#ifndef UGRAPH
#define UGRAPH

#include<hashtable2.h>

/* ! \brief A node is just a pointer to a node_struct */
typedef struct node_struct *node;

/* ! \brief An edge is just a pointer to an edge_struct */
typedef struct edge_struct *edge;

/* ! \brief A ugraph is just a pointer to a ugraph_struct */
typedef struct ugraph_struct *ugraph;

/*
 * ! \brief Representation of a node structure in an undirected graph. The
 * set of nodes is stored as a doubly linked list.
 */
struct node_struct {

	/* !Previous node in the list of nodes */
	node            prev;

	/* !Next node in the list of nodes */
	node            next;

	/* !First adjacent edge in the list of edges */
	edge            first_edge;

	/* !Last adjacent edge in the list of edges */
	edge            last_edge;

	/* !Degree of node */
	int             degree;

	/* !Unique ID of node */
	unsigned        id;

	/* !Pointer to auxillary variables, if any; similar to templates */
	void           *aux_vars;
};

/*
 * ! \brief Representation of an edge structure in an undirected graph. The
 * set of edges is stored as a doubly linked list.
 */
struct edge_struct {

	/* !Node at one endpoint of the edge */
	node            u;

	/* !Node at the other endpoint of the edge */
	node            v;

	/* !The previous edge in the list of edges */
	edge            prev;

	/* !The next edge in the list of edges */
	edge            next;

	/* !Stores the next edge in the list of adjacent edges to node u */
	edge            u_next;

	/* !Stores the previous edge in the list of adjacent edges to node u */
	edge            u_prev;

	/* !Stores the next edge in the list of adjacent edges to node v */
	edge            v_next;

	/* !Stores the previous edge in the list of adjacent edges to node v */
	edge            v_prev;

	/* !Unique ID of node */
	unsigned        id;

	/* !Pointer to auxillary variables, if any; similar to templates */
	void           *aux_vars;
};

/*
 * ! \brief An undirected graph is represented as two doubly linked lists,
 * one of nodes and the other of edges.
 */
struct ugraph_struct {

	/* !First edge in the edge list of the graph */
	edge            first_edge;

	/* !Last edge in the edge list of the graph */
	edge            last_edge;


	/* !First node in the node list of the graph */
	node            first_node;

	/* !Last node in the node list of the graph */
	node            last_node;

	/* !Number of edges */
	int             n_edges;

	/* !Number of nodes */
	int             n_nodes;

	/* !Max ID number of edges */
	unsigned        id_edges;

	/* !Max ID number of nodes */
	unsigned        id_nodes;
};

/* ! \brief Create a new node in constant time. */
node            new_node(ugraph G, void *aux_vars_);

/* ! \brief Delete a node and all edges adjacent to it in O(degree(u)) time. */
void            del_node(ugraph G, node u);

/* ! \brief Create a new edge in constant time. */
edge            new_edge(ugraph G, node u, node v, void *aux_vars_);

/* ! \brief Delete an edge in constant time */
void            del_edge(ugraph G, edge e);

/* ! \brief Create a new undirected graph in constant time. */
ugraph          new_graph();

/* ! \brief Delete the graph in O(#edges + #nodes) time. */
void            del_graph(ugraph G);

/*
 * ! \brief Print the adjacency list representation of a graph in O(#edges +
 * #nodes) time.
 */
void            print_graph(ugraph G);

/* ! \brief Return the node opposite node u on edge e in constant time. */
node            opposite(node u, edge e);

/* copy src into desination. dest must be empty but a created graph */
void            assign_graph(ugraph dest, ugraph src);

#endif