/* 
 * Code example for CP264 Data Structures II
 * Graph representation by adjacency list with basic operations
 * HBF
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>

typedef struct node {
  int vertex;
  struct node *next;
} node;

/*
 * generate a random directed graph
*/
void random_graph(node *adj[], int n);

/*
 * make a direct graph bidirectional
*/
void bidirect_graph(node *adj[], int node_number);
void create_graph(node *adj[], int n);
void display_graph(node *adj[], int n);
int add_edge(node *adj[], int n, int from, int to);
int delete_edge(node *adj[], int n, int from, int to);


void delete_graph(node *adj[], int n);
void display_bforder(node *adj[], int order, int start);
int bfs(node *adj[], int order, int start, int key);
void display_dforder(node *adj[], int order, int start);
int reachable_count(node *adj[], int order, int start);

void display_dforder_recursive(node *adj[], int order, int visited[], int start);

int main(int argc, char *args[]) {
  int n = 10, i;
  if (argc >1) n = atoi(args[1]);
  
  //declear adjacent list, initialize the graph
  node *adj[n];
  for (i = 0; i < n; i++) adj[i] = NULL;
  
  // add edges  
  for (i = 0; i < n-1; i++) {
    add_edge(adj, n, i, i+1);
  }
  add_edge(adj, n, n-1, 0);
  printf("\nDisplay Graph:");
  display_graph(adj, n);
  printf("\nReach count: %d\n", reachable_count(adj, n, 0));
  
  
  // delete edges
  for (i = 0; i < n-1; i++) {
    if (i%2 == 0)
    delete_edge(adj, n, i, i+1);
  }
  printf("\nDisplay Graph:");
  display_graph(adj, n);
  printf("\nReach count: %d\n", reachable_count(adj, n, 0));
  
  //delete the graph
  delete_graph(adj, n);   
  
 
  printf("\nGenerate random graph:");
  random_graph(adj, n);
 
  printf("\nDisplay Graph:");
  display_graph(adj, n);
  
  printf("\nbredth-first-order: "); 
  display_bforder(adj, n, 0); 
 
  int key = 7; 
  printf("\nbfs(%d)=%d\n", key, bfs(adj, n, 0, key));   
  
  printf("\ndepth-first-order: ");
  display_dforder(adj, n, 0);
  
  
  printf("\nConnectivity:");  
  int count = reachable_count(adj, n, 0);
  if (count == n) 
	  printf("\nconnected\n");
  else 
	  printf("\nnot connected\n");
  
  
  int visite[n]; 
  for (i=0; i<n; i++) visite[i] = 0;
  printf("\ndepth-first-order by recursive algorithm:\n");
  display_dforder_recursive(adj, n, visite, 0);
 
 
  delete_graph(adj, n);
 
 return 0;
}

void random_graph(node *adj[], int node_number) {
  node *new_node, *last;
  int i, j, k, h, d, val, flag;
  int neighbors[node_number];
  srand(time(NULL));

  for (i = 0; i < node_number; i++) {
    last = NULL;
    d = rand() % node_number;
  
    flag = 1;
    neighbors[0] = i;
    
    for (k = 1; k <= d; k++) {
      val = rand() % node_number;

      while (flag) {
        val = rand() % node_number;
        for (h=0; h<k; h++) {
          if (val == neighbors[h]) break;
        }
        if (h >= k) flag = 0;
      }

      neighbors[k] = val;
      flag = 1;
    }

    for (j = 1; j <= d; j++) {
      new_node = (node *) malloc(sizeof(node));
      new_node->vertex = neighbors[j];
      new_node->next = NULL;
      if (adj[i] == NULL)
        adj[i] = new_node;
      else
        last->next = new_node;
      last = new_node;
    }
  }
}

void  bidirect_graph(node *adj[], int node_number) {
  node *new_node;
  int i, j;
  
  node *c,  *prev = NULL, *p = NULL;

  for (i = 0; i < node_number; i++) {
    c = adj[i];
     
    while (c) {
      j = c->vertex;
      prev = NULL;
      p = adj[j];
      while (p) {
        if (p->vertex == i) {
          break;
        }         
        else {
          prev = p;
          p = p->next;
        }         
      }
      if (p==NULL) { 
        new_node = (node *) malloc(sizeof(node));
        new_node->vertex = i;
        new_node->next = NULL;
         
        if (prev == NULL) {
          adj[j] = new_node;
        } else {
          prev->next = new_node;
        }
      }
      c = c->next;
    }
  }
}

void create_graph(node *adj[], int node_number) {
  node *new_node, *last;
  int i, j, n, val;
  for (i = 0; i < node_number; i++) {
    last = NULL;
    printf("\nEnter the number of neighbors of %d: ", i);
    scanf("%d", &n);
    for (j = 1; j <= n; j++) {
      printf("\nEnter the neighbor %d of %d: ", j, i);
      scanf("%d", &val);
      new_node = (node *) malloc(sizeof(node));
      new_node->vertex = val;
      new_node->next = NULL;
      if (adj[i] == NULL)
        adj[i] = new_node;
      else
        last->next = new_node;
      last = new_node;
    }
  }
}

void display_graph(node *adj[], int node_number) {
  node *ptr;
  int i;
  printf("\nnode id : list of neighbor node id");
  for (i = 0; i < node_number; i++) {
    ptr = adj[i];
    printf("\n%d :", i);
    while (ptr != NULL) {
      printf(" %d", ptr->vertex);
      ptr = ptr->next;
    }
  }
}

int add_edge(node *adj[], int n, int from, int to) {
  if (0 > from || from > n || 0 > to || to > n) return -1;

  node *prev = NULL, *ptr = adj[from];  
  while (ptr != NULL) {
    if (ptr->vertex == to) return 0;
    else {
      prev = ptr; 
      ptr = ptr->next;
    }
  }
  if (ptr==NULL) { 
    node *new_node = (node *) malloc(sizeof(node));
    new_node->vertex = to;     
	new_node->next = NULL;
     
    if (prev == NULL) {
      adj[from] = new_node;
    } else {
      prev->next = new_node;
    }
  }
  return 1;
}

int delete_edge(node *adj[], int n, int from, int to) {
  if (0 > from || from > n || 0 > to || to > n) return -1;
  node *prev = NULL, *ptr = adj[from];
  while (ptr != NULL) {
    if (ptr->vertex == to) {
      if (prev == NULL) {
        adj[from] = ptr->next;
        free(ptr);
      } else {
        prev->next = ptr->next;
        free(ptr);
      }
      return 1;
    } else {
      prev = ptr; 
      ptr = ptr->next;
    }
  }
  return 0;
}

void delete_graph(node *adj[], int node_number) {
  int i;
  node *temp, *ptr;
  for (i = 0; i <node_number; i++) {
    ptr = adj[i];
    while (ptr != NULL) {
      temp = ptr;
      ptr = ptr->next;
      free(temp);
    }
    adj[i] = NULL;
  }
  printf("\nGraph is deleted");
}


void display_bforder(node *adj[], int order, int start) {
  int queue[order], rear = -1, front = -1, i;
  queue[++rear] = start;
  int visited[order]; 
  for (i=0; i<order; i++) visited[i] = 0; 
  
  visited[start] = 1;
  node *p = NULL;
  while (rear != front) {
    start = queue[++front];
    printf("%d ", start);
    p = adj[start];
    while (p) {
      i = p->vertex;
      if (visited[i] == 0) {
        visited[i] = 1;
        queue[++rear] = i;
      }
      p = p->next;
    }    
  }
}

int bfs(node *adj[], int order, int start, int key) {
  int queue[order], rear = -1, front = -1, i;
  queue[++rear] = start;
  int visited[order]; 
  for (i=0; i<order; i++) visited[i] = 0; 
  
  
  visited[start] = 1;
  node *p = NULL;
  while (rear != front) {
    start = queue[++front];
	
	if (key == start) return start;
   
    p = adj[start];
    while (p) {
      i = p->vertex;
      if (visited[i] == 0) {
        visited[i] = 1;
        queue[++rear] = i;
      }
      p = p->next;
    }    
  }
  return -1;
}


void display_dforder(node *adj[], int order, int start) 
{
  int stack[order];
  int top = -1, i;
  int visited[order]; 
  for (i=0; i<order; i++) visited[i] = 0; 
  
  
  visited[start] = 1;
  stack[++top] = start;
  node *p = NULL;
  while (top != -1) {
    start = stack[top--];
    printf("%d ", start);
    p = adj[start];
    while (p) {
      i = p->vertex;
      if (visited[i] == 0) {
        stack[++top] = i;
        visited[i] = 1;
      }  
      p = p->next;
    }
  }
}


int reachable_count(node *adj[], int order, int start) 
{
  int stack[order], i;
  int visited[order];
  for (i = 0; i<order; i++) visited[i] = 0;
  int top = -1;
  visited[start] = 1;
  stack[++top] = start;
  node *p = NULL;
  while (top != -1) {
    start = stack[top--];
    p = adj[start];
    while (p) {
      i = p->vertex;
      if (visited[i] == 0) {
        stack[++top] = i;
        visited[i] = 1;
      }  
      p = p->next;
    }
  }
  int count = 0;
  for (i = 0; i<order; i++) 
    if (visited[i] == 1) count++;
  
  return count;
}


void display_dforder_recursive(node *adj[], int order, int visited[], int start) 
{
  int i;
  node *p = NULL;
  visited[start] = 1;
  printf("%d ", start);
  p = adj[start];
  while (p) {
    i = p->vertex;
    if (visited[i] == 0) {
      display_dforder_recursive(adj, order, visited, i);
    }    
    p = p->next;
  }
}





/*
Display Graph:
node id : list of neighbor node id
0 : 1
1 : 2
2 : 3
3 : 4
4 : 5
5 : 6
6 : 7
7 : 8
8 : 9
9 : 0
Reach count: 10

Display Graph:
node id : list of neighbor node id
0 :
1 : 2
2 :
3 : 4
4 :
5 : 6
6 :
7 : 8
8 :
9 : 0
Reach count: 1

Graph is deleted
Generate random graph:
Display Graph:
node id : list of neighbor node id
0 : 2 9 3 7 5 1 8
1 : 0 6 2
2 : 5 4 0 3 6 7 8
3 : 9 2 7 5 4 0 8
4 : 9 7 3 8 6 0 2 1 5
5 : 2
6 : 7
7 : 3 9 1 4 6
8 : 0
9 : 4 6 1 0 8 3 5 7
bredth-first-order: 0 2 9 3 7 5 1 8 4 6
bfs(7)=7

depth-first-order: 0 8 1 6 5 7 4 3 9 2
Connectivity:
connected

depth-first-order by recursive algorithm:
0 2 5 4 9 6 7 3 8 1
Graph is deleted
 */