/*
 * "This code is from "Algorithms in C, Third Edition,"
 * by Robert Sedgewick, Addison-Wesley, 2002."
 * (Small edits by Y. Kohayakawa)
 */ 

#include <stdio.h>
#include <stdlib.h>
#include "GRAPH.h"
#include "ST.h"
typedef struct node *link;
struct node { int v; link next; };
struct graph { int V; int E; link *adj; };

Edge EDGE(int v, int w)
{
  Edge p;
  p.v = v; p.w = w;
  return p;
}

link NEW(int v, link next)
  { link x = malloc(sizeof *x);
    x->v = v; x->next = next;     
    return x;                         
  }
Graph GRAPHinit(int V)
  { int v;
    Graph G = malloc(sizeof *G);
    G->V = V; G->E = 0;
    G->adj = malloc(V*sizeof(link));
    for (v = 0; v < V; v++) G->adj[v] = NULL;
    return G;
  }

int GRAPHadj(Graph G, int v, int w)
  {
    link x;
    for (x = G->adj[v]; x != NULL; x = x->next)
      if (x->v == w)
	return 1;
    return 0;
  }

void GRAPHinsertE(Graph G, Edge e)
  { int v = e.v, w = e.w;
    if (!GRAPHadj(G, v, w) && (v != w))
      {
	G->adj[v] = NEW(w, G->adj[v]);
	G->adj[w] = NEW(v, G->adj[w]); 
	G->E++;
      }
  }
int GRAPHedges(Edge a[], Graph G)
  { int v, E = 0; link t;  
    for (v = 0; v < G->V; v++)
      for (t = G->adj[v]; t != NULL; t = t->next)
        if (v < t->v) a[E++] = EDGE(v, t->v); 
    return E;
  }

/* prog17.5 */

void GRAPHshow(Graph G)
  { int i;
    printf("%d vertices, %d edges\n", G->V, G->E);
    for (i = 0; i < G->V; i++)
      {
	link x;
        printf("%2d:", i);
	for (x = G->adj[i]; x != NULL; x = x->next)
	  printf(" %2d", x->v);
        printf("\n");
      }
  }

/* prog17.7.c */

int randV(Graph G)
  { return G->V * (rand() / (RAND_MAX + 1.0)); }
Graph GRAPHrand(int V, int E)
  { Graph G = GRAPHinit(V);
    while (G->E < E)
      GRAPHinsertE(G, EDGE(randV(G), randV(G)));
    return G;
  }

/* prog17.9 */

Graph GRAPHscan(int Vmax, int Emax)
  { char v[100], w[100];
    Graph G = GRAPHinit(Vmax);
    STinit();
    while (scanf("%99s %99s", v, w) == 2)
      GRAPHinsertE(G, EDGE(STindex(v), STindex(w)));
    return G;
  }

Graph GRAPHscan_noST(int Vmax, int Emax)
  { int v, w;
    Graph G = GRAPHinit(Vmax);
    while (scanf("%d %d", &v, &w) == 2)
      GRAPHinsertE(G, EDGE(v, w));
    return G;
  }