Laboratori-ASD/Laboratorio 8/Esercizio 2/Graph.c

// Laboratorio 8 - Esercizio 2 - Graph.c
// Matteo Schiff - s295565

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "Graph.h"
#include "ST.h"

typedef struct node *link;
struct node
{
    int id;
    int wt;
    link next;
};

struct graph
{
    int V;
    int E;
    int **madj;
    link *ladj;
    link z;
    ST tab;
};

static link newNode(int id, int wt, link next)
{
    link t = (link)malloc(sizeof(*t));
    t->id = id;
    t->wt = wt;
    t->next = next;
    return t;
}

static void freeList(link t, link z)
{
    link q, x = t;
    if (t == z)
        return;

    while (x != z)
    {
        q = x->next;
        free(x);
        x = q;
    }
}

static int searchList(link t, link z, int id)
{
    for (link x = t; x != z; x = x->next)
    {
        if (x->id == id)
            return 1;
    }

    return 0;
}

static Edge EDGEcreate(int v, int w, int wt)
{
    Edge e;
    e.v = v;
    e.w = w;
    e.wt = wt;
    return e;
}

// Questa variabile è usata dalla funzione `vertexCompare` che è chiamata da qsort
Graph tmpG;

static int vertexCompare(const void *a, const void *b)
{
    return (strcmp(STsearchByIndex(tmpG->tab, (*(Edge *)a).w).name, STsearchByIndex(tmpG->tab, (*(Edge *)b).w).name));
}

static void EDGEsort(Edge *edges, int N, Graph G)
{
    tmpG = G;
    qsort(edges, N, sizeof(Edge), vertexCompare);
}

Graph GRAPHload(FILE *fin)
{
    int lines = 0, wt;
    Graph G;

    Item item1, item2;

    for (char c = getc(fin); c != EOF; c = getc(fin))
        if (c == '\n') // Se leggo un newline aumento il numero delle linee
            lines = lines + 1;

    fseek(fin, 0, SEEK_SET);

    G = GRAPHinit(2 * lines); // Alloco sovrastimando il numero di vertici
    for (int i = 0; i < lines; i++)
    {
        item1 = ITEMread(fin);
        item2 = ITEMread(fin);
        fscanf(fin, " %d", &wt);

        int id1 = GRAPHgetIndex(G, item1);
        int id2 = GRAPHgetIndex(G, item2);

        GRAPHinsertE(G, id1, id2, wt);
    }

    return G;
}

void GRAPHinsertE(Graph G, int v, int w, int wt)
{
    if (G->madj[v][w] == 0)
        G->E++;
    G->madj[v][w] = 1;
    G->madj[v][w] = wt;
    G->madj[w][v] = 1;
    G->madj[w][v] = wt;
}

void GRAPHremoveE(Graph G, int v, int w)
{
    if (G->madj[v][w] != 0)
        G->E--;
    G->madj[v][w] = 0;
    G->madj[w][v] = 0;
}

static int **MATRIXinit(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;
}

static link *LISTinit(int V, link z)
{
    link *list = (link *)malloc(V * sizeof(link));
    for (int v = 0; v < V; v++)
        list[v] = z;

    return list;
}

Graph GRAPHinit(int V)
{
    Graph G = malloc(sizeof *G);
    G->V = 0;
    G->E = 0;
    G->madj = MATRIXinit(V, V, 0);
    G->z = newNode(-1, -1, NULL);
    G->ladj = LISTinit(V, G->z);
    G->tab = STinit(V);
    return G;
}

void GRAPHfree(Graph G)
{
    int i;
    for (i = 0; i < G->V; i++)
        free(G->madj[i]);
    free(G->madj);
    for (i = 0; i < G->V; i++)
    {
        freeList(G->ladj[i], G->z);
    }
    free(G->ladj);
    free(G->z);
    STfree(G->tab);
    free(G);
}

int GRAPHgetIndex(Graph G, Item item)
{
    int id = STsearch(G->tab, item);
    if (id == -1)
    {
        id = STinsert(G->tab, item);
        G->V++;
    }
    return id;
}

void GRAPHbuildLadj(Graph G)
{
    link t;

    for (int i = 0; i < G->V; i++)
    {
        freeList(G->ladj[i], G->z);
        G->ladj[i] = G->z;
    }

    for (int i = 0; i < G->V; i++)
    {
        for (int j = 0; j < G->V; j++)
        {
            if (G->madj[i][j] != 0)
                G->ladj[i] = newNode(j, G->madj[i][j], G->ladj[i]);
        }
    }

    for (int i = 0; i < G->V; i++)
    {
        if (G->ladj[i] != G->z)
        {
            printf("%d", i);
            for (t = G->ladj[i]; t != G->z; t = t->next)
            {
                printf(" -> (%d,%d)", t->id, t->wt);
            }
            printf("\n");
        }
    }
}

static int checkAdjacencyM(Graph G, int id1, int id2, int id3)
{
    if (!G->madj[id1][id2] || !G->madj[id1][id3])
        return 0;

    if (!G->madj[id2][id1] || !G->madj[id2][id3])
        return 0;

    if (!G->madj[id3][id1] || !G->madj[id3][id2])
        return 0;

    return 1;
}

static int checkAdjacencyL(Graph G, int id1, int id2, int id3)
{
    if (!searchList(G->ladj[id1], G->z, id2) || !searchList(G->ladj[id1], G->z, id2))
        return 0;

    if (!searchList(G->ladj[id2], G->z, id1) || !searchList(G->ladj[id2], G->z, id3))
        return 0;

    if (!searchList(G->ladj[id3], G->z, id1) || !searchList(G->ladj[id3], G->z, id2))
        return 0;

    return 1;
}

void GRAPHCheckVertexAdiacency(Graph G)
{
        puts("Inserisci i tre vertici specificando per ogni vertice \"<nome> <subnet>\"");
    Item i1 = ITEMread(stdin);
    Item i2 = ITEMread(stdin);
    Item i3 = ITEMread(stdin);

    int id1 = STsearch(G->tab, i1);
    int id2 = STsearch(G->tab, i2);
    int id3 = STsearch(G->tab, i3);

    if (id1 == -1 || id2 == -1 || id3 == -1)
    {
        puts("Attenzione: vertici non validi");
        return;
    }

    if (checkAdjacencyM(G, id1, id2, id3))
    {
        puts("I vertici formano un sottografo completo");
    }
    else
    {
        puts("I vertici non formano un sottografo completo");
    }
}

void GRAPHprintOrdered(Graph G)
{
    Item *items = malloc(G->V * sizeof(Item));
    Edge *edges = malloc(G->V * sizeof(Edge));

    for (int i = 0; i < G->V; i++)
    {
        items[i] = STsearchByIndex(G->tab, i);
    }

    ITEMsort(items, G->V);

    for (int i = 0; i < G->V; i++)
    {
        int id = GRAPHgetIndex(G, items[i]);
        printf("%s %s:\n", items[i].name, items[i].subnet);

        // Crea lista di edges
        int N = 0;
        for (int j = 0; j < G->V; j++)
        {
            if (G->madj[id][j] != 0)
                edges[N++] = EDGEcreate(id, j, G->madj[id][j]);
        }

        EDGEsort(edges, N, G);

        for (int j = 0; j < N; j++)
        {
            printf("  - %s %s, peso %d\n", STsearchByIndex(G->tab, edges[j].w).name, STsearchByIndex(G->tab, edges[j].w).subnet, edges[j].wt);
        }
    }

    free(edges);
    free(items);
}