/*
 * "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"
struct graph { int V; int E; int **adj; };

/* prog17.4 */

int **MATRIXint(int r, int c, int val)
  { int i, j;
    int **t = malloc(r * sizeof(int *));
    for (i = 0; i < r; i++)
      t[i] = malloc(c * sizeof(int));
    for (i = 0; i < r; i++)
      for (j = 0; j < c; j++)
        t[i][j] = val;
    return t;
  }

/* prog17.3.c */

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

Graph GRAPHinit(int V)
  { Graph G = malloc(sizeof *G);
    G->V = V; G->E = 0;
    G->adj = MATRIXint(V, V, 0);
    return G;
  }
void GRAPHinsertE(Graph G, Edge e)
  { int v = e.v, w = e.w;
  if ((G->adj[v][w] == 0) && (v != w))
    {
      G->E++;
      G->adj[v][w] = 1; 
      G->adj[w][v] = 1;
    }
  }
void GRAPHremoveE(Graph G, Edge e)
  { int v = e.v, w = e.w;
    if (G->adj[v][w] == 1) G->E--;
    G->adj[v][w] = 0; 
    G->adj[w][v] = 0;
  }
int GRAPHedges(Edge a[], Graph G)
  { int v, w, E = 0;
    for (v = 0; v < G->V; v++)
      for (w = v+1; w < G->V; w++)
        if (G->adj[v][w] == 1) 
          a[E++] = EDGE(v, w); 
    return E;
  }

/* prog17.5 */

void GRAPHshow(Graph G)
  { int i, j; 
    printf("%d vertices, %d edges\n", G->V, G->E);
    for (i = 0; i < G->V; i++)
      {
        printf("%2d:", i);
        for (j = 0; j < G->V; j++)
          if (G->adj[i][j] == 1) printf(" %2d", j);
        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;
  }