/*
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