// Implementation of the undirected graph ADT using an adjacency matrix

// !!! DO NOT MODIFY THIS FILE !!!

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#include "Graph.h"

static bool validVertex(Graph g, Vertex v);

Graph GraphNew(int nV) {
    assert(nV > 0);

    Graph g = malloc(sizeof(*g));
    if (g == NULL) {
        fprintf(stderr, "error: out of memory\n");
        exit(EXIT_FAILURE);
    }

    g->nV = nV;

    // allocate memory for array of lists
    g->edges = malloc(nV * sizeof(bool *));
    if (g->edges == NULL) {
        fprintf(stderr, "error: out of memory\n");
        exit(EXIT_FAILURE);
    }
    for (int i = 0; i < nV; i++) {
        g->edges[i] = calloc(nV, sizeof(bool));
        if (g->edges[i] == NULL) {
            fprintf(stderr, "error: out of memory\n");
            exit(EXIT_FAILURE);
        }
    }

    return g;
}

void GraphFree(Graph g) {
    for (int i = 0; i < g->nV; i++) {
        free(g->edges[i]);
    }
    free(g->edges);
    free(g);
}

int GraphNumVertices(Graph g) {
    return g->nV;
}

void GraphInsertEdge(Graph g, int v, int w) {
    assert(validVertex(g, v));
    assert(validVertex(g, w));

    g->edges[v][w] = true;
    g->edges[w][v] = true;
}

void GraphShow(Graph g) {
    GraphPrint(g, stdout);
}

void GraphPrint(Graph g, FILE *out) {
    fprintf(out, "Number of vertices: %d\n", g->nV);
    fprintf(out, "Edges:\n");
    for (int i = 0; i < g->nV; i++) {
        fprintf(out, " %d:", i);
        for (int j = 0; j < g->nV; j++) {
            if (g->edges[i][j]) {
                fprintf(out, " %d", j);
            }
        }
        fprintf(out, "\n");
    }
}

// Check if vertex is valid in a graph
static bool validVertex(Graph g, Vertex v) {
    return (v >= 0 && v < g->nV);
}