/* 
 * Code example for CP264 Data Structures II
 * Graph representation by linked node
 * HBF
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>

struct node;

typedef struct adjnode {
  int weight;        // edge weight
  struct node *to;   // struct node type pointer to a neighbor node
  struct adjnode *next; // next neighbor node
} ADJNODE; 

typedef struct node {
  int id;            // node id or identifier
  int data;          // node data or node weight 
  struct adjnode *neighbor;  // pointer to the linked list of neighbors
} NODE; 

typedef struct graph {
  int order;
  NODE **nodes;  //node pointer array
} LNGRAPH; 

ADJNODE *new_adjnode(NODE *to, int weight);
NODE *new_node(int id, int value);
LNGRAPH *new_graph(int n);
void display_graph(LNGRAPH *g);
int add_edge(LNGRAPH *g, NODE *from, NODE *to, int weigth);
int delete_edge(LNGRAPH *g, NODE *from, NODE *to);
void clean_graph(LNGRAPH **gp);

int main(int argc, char *args[]) {
  int n = 10;
  if (argc >1) n = atoi(args[1]);
 
  printf("create an empty linked graph\n");
  LNGRAPH *g = new_graph(10);
  display_graph(g);
  
  printf("add nodes\n");
  int i;
  for (i = 0; i < n; i++) {
    g->nodes[i] =  new_node(i, i*2);
  }
  display_graph(g);
  
  printf("add edges\n");      
  for (i = 0; i < n; i++) {
    add_edge(g, g->nodes[i],  g->nodes[(i+1) % n], i+10);
	add_edge(g, g->nodes[i],  g->nodes[(i+2) % n], i+20);
  }
  display_graph(g);
  
  printf("delete edges\n");
  for (i = 0; i < n; i++) {
    delete_edge(g, g->nodes[i],  g->nodes[(i+1) % n]);
  }
  display_graph(g);
  
  printf("clean graph\n");
  clean_graph(&g);
  
  display_graph(g);
 
  return 0;
}

ADJNODE *new_adjnode(NODE *to, int weight)
{ 
  ADJNODE *np = (ADJNODE*) malloc(sizeof(ADJNODE));
  np->to = to;
  np->weight = weight;
  np->next = NULL;
  return np;
}

NODE *new_node(int id, int value)
{
  NODE *np = (NODE*) malloc(sizeof(NODE));
  np->id = id;  
  np->data = value;
  np->neighbor = NULL;
  return np;
}

LNGRAPH *new_graph(int n)
{
  LNGRAPH *np = (LNGRAPH*) malloc(sizeof(LNGRAPH));
  np->order = n;
  np->nodes = (NODE**) malloc(n*sizeof(NODE*));
  int i;
  for (i=0; i<n; i++) 
	 np->nodes[i] = NULL;
  return np;
}

void display_graph(LNGRAPH *g) {
  if (g == NULL) printf("empty");
  int n = g->order;
  ADJNODE *ptr;
  int i;
  for (i = 0; i < n; i++) {
    if (g->nodes[i] == NULL) continue;
    printf("node id: %d, data: %d, ", g->nodes[i]->id, g->nodes[i]->data);
	ptr = g->nodes[i]->neighbor;
	while (ptr != NULL) {
	  printf("(%d, %d, %d) ",  g->nodes[i]->id, ptr->to->id, ptr->weight);
      ptr = ptr->next;
    }
	printf("\n");
  }
}

int add_edge(LNGRAPH *g, NODE *from, NODE *to, int weight)
{  
  int i;
  int n = g->order;
  for (i=0; i<n; i++) {
	 if (from == g->nodes[i]) break; 
  }
  ADJNODE *adjnode = new_adjnode(to, weight);
  
  adjnode->next = g->nodes[i]->neighbor;
  g->nodes[i]->neighbor = adjnode;
   	
  return 0;	
}

int delete_edge(LNGRAPH *g, NODE *from, NODE *to)
{
  ADJNODE *ptr, *prev;
  int i;
  int n = g->order;
  for (i=0; i<n; i++) {
	 if (from == g->nodes[i]) break; 
  }
  if (i == n) return 0;
  
  ptr = g->nodes[i]->neighbor;
  prev = NULL;
  
  while (ptr != NULL && ptr->to != to) {
    prev = ptr;
    ptr = ptr->next;
  }
  
  if (ptr == NULL) return 0;
  
  if (prev == NULL) 
	g->nodes[i]->neighbor = NULL;
  else {
	prev->next = ptr->next;  
  }
  free(ptr);

  return 1;	
}

void clean_graph(LNGRAPH **gp) {
  LNGRAPH *g = *gp;
  if (g == NULL) return;
  ADJNODE *ptr, *temp;
  int n = g->order;
  int i;
  for (i = 0; i<n; i++) {
	if (g->nodes[i] == NULL) continue;
    ptr = g->nodes[i]->neighbor;
    while (ptr != NULL) {
      temp = ptr;
      ptr = ptr->next;
	  free(ptr);
    }
    free(g->nodes[i]);	
  }
  *gp = NULL;
}

/*
create an empty linked graph
add nodes
node id: 0, data: 0,
node id: 1, data: 2,
node id: 2, data: 4,
node id: 3, data: 6,
node id: 4, data: 8,
node id: 5, data: 10,
node id: 6, data: 12,
node id: 7, data: 14,
node id: 8, data: 16,
node id: 9, data: 18,
add edges
node id: 0, data: 0, (0, 2, 20) (0, 1, 10)
node id: 1, data: 2, (1, 3, 21) (1, 2, 11)
node id: 2, data: 4, (2, 4, 22) (2, 3, 12)
node id: 3, data: 6, (3, 5, 23) (3, 4, 13)
node id: 4, data: 8, (4, 6, 24) (4, 5, 14)
node id: 5, data: 10, (5, 7, 25) (5, 6, 15)
node id: 6, data: 12, (6, 8, 26) (6, 7, 16)
node id: 7, data: 14, (7, 9, 27) (7, 8, 17)
node id: 8, data: 16, (8, 0, 28) (8, 9, 18)
node id: 9, data: 18, (9, 1, 29) (9, 0, 19)
delete edges
node id: 0, data: 0, (0, 2, 20)
node id: 1, data: 2, (1, 3, 21)
node id: 2, data: 4, (2, 4, 22)
node id: 3, data: 6, (3, 5, 23)
node id: 4, data: 8, (4, 6, 24)
node id: 5, data: 10, (5, 7, 25)
node id: 6, data: 12, (6, 8, 26)
node id: 7, data: 14, (7, 9, 27)
node id: 8, data: 16, (8, 0, 28)
node id: 9, data: 18, (9, 1, 29)
clean graph
empty
*/