Laboratori-ASD/Laboratorio 9/Esercizio 1/Graph.c

// Laboratorio 9 - Esercizio 1 - Graph.c
// Matteo Schiff - s295565

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

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

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

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

static link newNode(int v, int wt, link next)
{
    link t = (link)malloc(sizeof(*t));
    t->v = v;
    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 v)
{
    for (link x = t; x != z; x = x->next)
    {
        if (x->v == v)
            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;
}

void GRAPHedges(Graph G, Edge *a)
{
    int v, E = 0;
    link t;
    for (v = 0; v < G->V; v++)
        for (t = G->ladj[v]; t != G->z; t = t->next)
            a[E++] = EDGEcreate(v, t->v, t->wt);
}

Graph GRAPHload(FILE *fin)
{
    int V, i, id1, id2, wt;
    char label1[MAX_LEN + 1], label2[MAX_LEN + 1];
    Graph G;
    fscanf(fin, "%d", &V);
    G = GRAPHinit(V);
    for (i = 0; i < V; i++)
    {
        fscanf(fin, "%s", label1);
        STinsert(G->tab, label1);
    }
    while (fscanf(fin, "%s %s %d", label1, label2, &wt) == 3)
    {
        id1 = STsearch(G->tab, label1);
        id2 = STsearch(G->tab, label2);
        if (id1 >= 0 && id2 >= 0)
            GRAPHinsertE(G, id1, id2, wt);
    }
    return G;
}

void GRAPHstore(Graph G, FILE *fout)
{
    int i;
    Edge *a;
    a = malloc(G->E * sizeof(Edge));
    GRAPHedges(G, a);
    fprintf(fout, "%d\n", G->V);
    for (i = 0; i < G->V; i++)
        fprintf(fout, "%s\n", STsearchByIndex(G->tab, i));
    for (i = 0; i < G->E; i++)
        fprintf(fout, "%s %s %d\n",
                STsearchByIndex(G->tab, a[i].v),
                STsearchByIndex(G->tab, a[i].w), a[i].wt);
    free(a);
}

void GRAPHinsertE(Graph G, int v, int w, int wt)
{
    G->ladj[v] = newNode(w, wt, G->ladj[v]);
    G->E++;
}

void GRAPHremoveE(Graph G, int v, int w)
{
    link x, p;
    for (x = G->ladj[v], p = NULL; x != G->z; p = x, x = x->next)
    {
        if (x->v == w)
        {
            if (x == G->ladj[v])
                G->ladj[v] = x->next;
            else
                p->next = x->next;
            break;
        }
    }
    G->E--;
    free(x);
}

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 = V;
    G->E = 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++)
    {
        freeList(G->ladj[i], G->z);
    }
    free(G->ladj);
    free(G->z);
    STfree(G->tab);
    free(G);
}

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

int GRAPHEdgeCount(Graph G)
{
    return G->E;
}

// funzione che restituisce in `backEdges` tutti i vertici di tipo backward
void searchBackwardEdgesR(Graph G, Edge e, int *time,
                          int *pre, int *post, Edge *backEdges, int *backEdgesNum)
{
    pre[e.w] = (*time)++;
    for (link t = G->ladj[e.w]; t != G->z; t = t->next)
        if (pre[t->v] == -1)
            searchBackwardEdgesR(G, EDGEcreate(e.w, t->v, t->wt), time, pre, post, backEdges, backEdgesNum);
        else
        {
            if (post[t->v] == -1)
                backEdges[(*backEdgesNum)++] = EDGEcreate(e.w, t->v, t->wt);
        }
    post[e.w] = (*time)++;
}

void GRAPHFindCardMinDAG(Graph G, int *cardinality, Edge *edges)
{
    int *pre = (int *)malloc(G->V * sizeof(int));
    int *post = (int *)malloc(G->V * sizeof(int));
    Edge **backEdges = malloc(G->V * sizeof(Edge *));
    int *cards = (int *)malloc(G->V * sizeof(int));

    for (int i = 0; i < G->V; i++)
    {
        backEdges[i] = malloc(G->E * sizeof(Edge));
        for (int j = 0; j < G->E; j++)
        {
            backEdges[i][j] = EDGEcreate(0, 0, 0);
        }
    }

    int minCard = -1;

    for (int i = 0; i < G->V; i++)
    {
        int time = 0;
        cards[i] = 0;
        for (int j = 0; j < G->V; j++)
        {
            pre[j] = -1;
            post[j] = -1;
        }

        // per rendere un grafo un DAG bisogna togliere tutti gli archi backward
        searchBackwardEdgesR(G, EDGEcreate(i, i, 0), &time, pre, post, backEdges[i], &cards[i]);
        for (int j = 0; j < G->V; j++)
            if (pre[j] == -1)
                searchBackwardEdgesR(G, EDGEcreate(j, j, 0), &time, pre, post, backEdges[i], &cards[i]);

        // inizio a memorizzare la cardinalità minima
        if (cards[i] < minCard || minCard == -1)
        {
            minCard = cards[i];
        }
    }

    free(post);
    free(pre);

    int curWeight, idMaxWeight = 0, maxWeight = -1;

    if (minCard == 0)
    {
        puts("Il grafo è già un DAG, non si deve fare nulla");
        *cardinality = 0;
    }
    else
    {
        puts("Insiemi di archi da rimuovere con cardinalità minima: ");
        for (int i = 0; i < G->V; i++)
        {
            curWeight = 0;
            if (cards[i] != minCard)
                continue;

            printf("{");
            for (int j = 0; j < G->E; j++)
            {
                if (backEdges[i][j].wt != 0)
                {
                    curWeight += backEdges[i][j].wt;
                    printf(" (%s, %s, wt: %d)", STsearchByIndex(G->tab, backEdges[i][j].v), STsearchByIndex(G->tab, backEdges[i][j].w), backEdges[i][j].wt);
                }
            }

            // mentre stampo gli insiemi cerco l'insieme di peso massimo
            if (curWeight > maxWeight)
            {
                maxWeight = curWeight;
                idMaxWeight = i;
            }
            printf(" }\n");
        }

        printf("Insieme di archi da rimuovere a peso massimo:\n {");
        for (int i = 0; i < cards[idMaxWeight]; i++)
        {
            edges[i] = backEdges[idMaxWeight][i];
            printf(" (%s, %s, wt: %d)", STsearchByIndex(G->tab, backEdges[idMaxWeight][i].v), STsearchByIndex(G->tab, backEdges[idMaxWeight][i].w), backEdges[idMaxWeight][i].wt);
        }
        printf(" }\n");
        *cardinality = cards[idMaxWeight];
    }

    for (int i = 0; i < G->V; i++)
    {
        free(backEdges[i]);
    }
    free(backEdges);
    free(cards);
}

void GRAPHRemoveEdges(Graph G, Edge *edges, int N)
{
    for (int i = 0; i < N; i++)
        GRAPHremoveE(G, edges[i].v, edges[i].w);
}

static int GRAPHisSource(Graph G, int id)
{
    // un nodo è sorgente se nessun arco punta a tale nodo
    for (int v = 0; v < G->V; v++)
    {
        for (link t = G->ladj[v]; t != G->z; t = t->next)
        {
            if (t->v == id)
            {
                // ho trovato un arco che punta al nodo
                return 0;
            }
        }
    }

    return 1;
}

void sortTopologicalR(Graph G, int w, int *time,
                      int *pre, int *post, int *orderedVertex, int *cnt)
{
    pre[w] = (*time)++;
    for (link t = G->ladj[w]; t != G->z; t = t->next)
        if (pre[t->v] == -1)
            sortTopologicalR(G, t->v, time, pre, post, orderedVertex, cnt);
    post[w] = (*time)++;
    orderedVertex[(*cnt)++] = w;
}

void sortTopological(Graph G, int start, int *orderedVertex)
{
    int time = 0, cnt = 0;
    int *pre = (int *)malloc(G->V * sizeof(int));
    int *post = (int *)malloc(G->V * sizeof(int));
        for (int j = 0; j < G->V; j++)
        {
            pre[j] = -1;
            post[j] = -1;
        }
    sortTopologicalR(G, start, &time, pre, post, orderedVertex, &cnt);
    free(post);
    free(pre);
}

void GRAPHmaxPathFromSource(Graph G)
{
    link t;

    int *distances = (int *)malloc(G->V * sizeof(int));
    int *st = (int *)malloc(G->V * sizeof(int));
    int *topSorted = (int *)malloc(G->V * sizeof(int));

    for (int i = 0; i < G->V; i++)
    {
        if (GRAPHisSource(G, i))
        {
            // ordinamento topologico dei vertici a partire dalla sorgente i
            sortTopological(G, i, topSorted);
            for (int j = 0; j < G->V; j++)
            {
                distances[j] = INT_MIN;
                st[j] = -1;
            }
            distances[i] = 0;
            st[i] = i;

            for (int j = G->V-1; j >=0; j--)
            {
                int k = topSorted[j];
                for (t = G->ladj[k]; t != G->z; t = t->next)
                {
                    // aggiorno le distanze se ho trovato un cammino più lungo
                    if (distances[t->v] < distances[k] + t->wt)
                    {
                        st[t->v] = k;
                        distances[t->v] = distances[k] + t->wt;
                    }
                }
            }

            // stampo per ogni vertice il cammino massimo
            for (int j = 0; j < G->V; j++)
            {
                int k = j;
                if (j != i)
                {
                    printf("Cammino massimo dalla sorgente %s al nodo %s:\n", STsearchByIndex(G->tab, i), STsearchByIndex(G->tab, j));
                    printf("%s", STsearchByIndex(G->tab, k));
                    while (k != i)
                    {
                        printf(" <- %s", STsearchByIndex(G->tab, st[k]));
                        k = st[k];
                    }
                    printf("\nPeso del cammino: %d\n", distances[j]);
                }
            }
        }
    }

    free(distances);
    free(topSorted);
    free(st);
}