graph.c

/*
 *  graph.c
 *  graphes
 *
 *  Created by Stphane on 19/02/18.
 *  Copyright 2018 __MyCompanyName__. All rights reserved.
 *
 */

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
//#include <tcl.h>

#include "lists.h"
#include "decompose.h"
#include "graph.h"
#include "heap.h"
#include "main.h"
#include "sets.h"
#include "utils.h"


int maxMemory = 8000;


Graph newGraph(int n, int m, LIST *adj, int *nadj) {
    Graph g;

    g = malloc(sizeof(struct graph));

    g->n = n;
    g->m = m;
    if (adj == NULL) {
        g->adj = calloc(n, sizeof(LIST));
        g->nadj = calloc(n, sizeof(int));
    }
    else {
        g->adj = adj;
        g->nadj = nadj;
        g->lists = malloc(g->n*sizeof(int *));
        g->slists = malloc(g->n*sizeof(int *));
        for (int i = 0; i < n; i ++) {
            g->lists[i] = malloc((g->nadj[i]+1)*sizeof(int));
            g->lists[i][g->nadj[i]] = NONE;
            g->slists[i] = malloc((g->nadj[i]+1)*sizeof(int));
            g->slists[i][g->nadj[i]] = NONE;
            g->nadj[i] = 0;
        }
        for (int i = 0; i < n; i ++) {
            LIST p = adj[i];
            while (p != NULL) {
                g->lists[i][g->nadj[i]] = g->slists[i][g->nadj[i]] = p->val;
                g->nadj[i] ++;
                p = p->suiv;
            }

        }
    }

    g->neighbors = malloc(g->n*sizeof(SET));

    if ((algo == GREEDY_ALGORITHM) || ((g->n/64)*(g->n/128)/1024 > maxMemory)) { // n=260000 --> mem=8000
        for (int i = 0; i < n; i ++) g->neighbors[i] = NULL;
        return g;
    }

    for (int i = 0; i < n; i ++) {

        SET neighbors = allocSet(g->n);
        if (adj != NULL) {
            int *p = g->lists[i];
            while (*p != NONE) {
                ADDe(*p, neighbors);
                p ++;
            }
        }
        g->neighbors[i] = neighbors;
    }

#ifdef NOTDEF
    g->nodes = malloc(n*sizeof(NODE_FIBO));
    assert(g->nodes != NULL);
    for (int i = 0; i < n; i ++) {
        g->nodes[i] = newHeapNode(i, 0, NULL, NULL, NULL, NULL, 0, 1, NULL);
    }
#endif

    return g;
}



// Determine if u and v are neighbors.
int areNeighbours(int u, int v, Graph g) {

    if (g->neighbors[v] != NULL)
        return IN(u, g->neighbors[v]);

    if (g->nadj[u] <= g->nadj[v]) {
        for (int *p = g->lists[u]; *p != NONE; p++) {
            if (*p == v) return 1;
        }
        return 0;
    }

    for (int *p = g->lists[v]; *p != NONE; p++) {
        if (*p == u) return 1;
    }
    return 0;
}


void printGraph(Graph g) {
    for (int i = 0; i < g->n; i ++) {
        for (LIST p = g->adj[i]; p != NULL; p = p->suiv)
            printf("%d -- %d\n", i, p->val);
    }
}


// Count the number of vertices of list[] which are in the heap F (used to count the number of neighbors in the heap).
int nbVerticeInHeap(int list[], int n, Heap F, Graph g) {
    int nb = 0;
    for (int *p = list; p < list+n; p ++) {
        if (F->ind[*p] != NONE)
            nb ++;
    }
    return nb;
}

int nbNeighborsInHeap(int u, Heap F, Graph g) {
    LIST p = g->adj[u];
    int nb = 0;
    while (p != NULL) {
        if (F->ind[p->val] != NONE)
            nb ++;
        p = p->suiv;
    }
    return nb;
}


int nbNeighborsInList(int u, SET V, int *S, int n, Graph g) {
    LIST p = g->adj[u];
    int nbN = 0;

    while (p != NULL) {
        if (isInSet(p->val, V, S, n)) {
            nbN ++;
        }
        p = p->suiv;
    }
    return nbN;
}

int hasNoNeighborInSet(int vertex, SET V, Graph g) {
    for (int *p = g->lists[vertex]; *p != NONE; p ++)
        if (IN(*p, V)) return 0;
    return 1;
}

int hasNeighborsInSubtree(int vertex, SET V, Graph g) {
    int nb = 0;
    for (int *p = g->lists[vertex]; *p != NONE; p ++)
        if (IN(*p, V)) nb ++;
    return nb;
}


int haveSameNeighbors(int u, int v, Graph g) {
    int *q;
    for (int *p = g->lists[u]; *p != NONE; p ++) {
        for (q = g->lists[v]; *q != NONE; q++)
            if (*p == *q) break;
        if (*q == NONE) return 0;
    }
    return 1;
}



//
// Connections in current set
//

Heap conHeap = NULL; // contains the vertices ordered by their number of neighbors in the cluster
int *nbN4Con; // for each vertex the number of its neighbors in the cluster
int nbE4Con, nbMax4Con, maxNbN4Con;
int nbUnconnectedVertices;

int hasMoreConnections(int a, int b) {
    return (nbN4Con[a] > nbN4Con[b]);
}

void allocConnectionsHeap(Graph g) {
    conHeap = allocHeap(g->n, hasMoreConnections);
    nbN4Con = malloc(g->n * sizeof(int));
}

//
// Update the max value in the heap and its number of occurrences
//

void exploreCountMax(int i, int T[], int n) {
    if (nbN4Con[T[i]] == maxNbN4Con) {
        nbMax4Con ++;
        if (2*i+1 < n) {
            exploreCountMax(2*i+1, T, n);
            if (2*i+2 < n)
                exploreCountMax(2*i+2, T, n);
        }
    }
}

void updateNbMaxConInHeap(Heap heap) {

    if (heap->n == 0) { nbMax4Con = 0; return; }

    maxNbN4Con = nbN4Con[heap->val[0]];
    nbMax4Con = 0;
    exploreCountMax(0, heap->val, heap->n);
}



// Rebuilt the heap. Suppose that there is no unconnected components here (called after decomposeConnectedComponents)
// returns 1 if the heap is a clique
int rebuildConHeap(Heap heap) {
    nbE4Con = 0;
    nbUnconnectedVertices = 0; // Comes from decomposeConnectedComponents normally with no unconnected vertices
    maxNbN4Con = -1;
    int minNbN4Con = conHeap->n + 1;
    for (int i = 0; i < conHeap->n; i ++) {
        conHeap->ind[conHeap->val[i]] = i;
        nbE4Con += nbN4Con[conHeap->val[i]];
        if (nbN4Con[conHeap->val[i]] == 0) nbUnconnectedVertices ++;
        if (nbN4Con[conHeap->val[i]] < minNbN4Con) minNbN4Con = nbN4Con[conHeap->val[i]];
        if (nbN4Con[conHeap->val[i]] > maxNbN4Con) { maxNbN4Con = nbN4Con[conHeap->val[i]]; nbMax4Con = 1; }
        else if (nbN4Con[conHeap->val[i]] == maxNbN4Con) nbMax4Con ++;
    }
    makeHeap(conHeap);
    if (minNbN4Con == heap->n - 1) return 1;
    return 0;
    //heapVerif(conHeap, nbN4Con);
}

// The initial construction of the heap: there can be unconnected components !
void initConHeap(Graph g) {

    //conHeap = allocHeap(g->n, hasMoreConnections);
    //nbN4Con = malloc(g->n * sizeof(int));

    nbE4Con = 0;
    nbMax4Con = 0;
    maxNbN4Con = -1;
    nbUnconnectedVertices = 0;
    conHeap->n = 0;

    for (int i = 0; i < g->n; i++) {
        heapJustAdd(i, conHeap);
        nbN4Con[i] = g->nadj[i];
        nbE4Con += nbN4Con[i];
        if (nbN4Con[i] > maxNbN4Con) { maxNbN4Con = nbN4Con[i]; nbMax4Con = 1; }
        else if (nbN4Con[i] == maxNbN4Con) nbMax4Con ++;
        if (nbN4Con[i] == 0) nbUnconnectedVertices ++;
    }

    shakeList(conHeap->val, conHeap->ind, conHeap->n, g->n / 2);

    makeHeap(conHeap);
}


int countNbUnconnectedInHeap(Heap F) {
    int nb = 0;
    for (int i = 0; i < F->n; i ++)
        if (nbN4Con[F->val[i]] == 0) nb ++;
    return nb;
}



// Here other vertices may have index not NONE but they can not be in u component and then they are not neighbors
int updateHeapNbNAfterRemoval(int u, Heap heap, Graph g) {

    int nbRemovedEdges = 0;

    //assert(nbUnconnectedVertices == countNbUnconnectedInHeap(heap));
    for (int *pp = g->lists[u]; *pp != NONE; pp ++) {

        nbN4Con[*pp] --;

        if (heap->ind[*pp] != NONE) {

            // if ( nbOccs(*pp, heap->val, heap->n) != 1) printf("%d OUYE\n", *pp);

            nbRemovedEdges ++;

            if (nbN4Con[*pp]+1 == maxNbN4Con) nbMax4Con --;

            if (nbN4Con[*pp] == 0) { // put unconnected vertice at the end of the heap (can leave current branch)
                int pos = heap->ind[*pp];
                if (0 && (nbUnconnectedVertices+1 != countNbUnconnectedInHeap(heap))) { printf("nbunconnected is not good : %d / %d\n", countNbUnconnectedInHeap(heap), nbUnconnectedVertices+1);exit(0); }
                heapSwap(pos, heap->n - 1 - nbUnconnectedVertices, heap);
                // update the heap
                if ((pos > 0) && (nbN4Con[heap->val[pos]] > nbN4Con[*pp]+1))
                    heapBubbleUp(pos, heap);
                else if (nbN4Con[heap->val[pos]] < nbN4Con[*pp]+1)
                    heapBubbleDown(heap, pos);
                nbUnconnectedVertices++;
            }
            else {
                heapBubbleDown(heap, heap->ind[*pp]);
            }
        }
    }
    //assert(nbUnconnectedVertices == countNbUnconnectedInHeap(heap));
    return nbRemovedEdges;
}


// returns the position of a vertex of S[] with many neighbors in S[] (depending of mode).
int vertexWithManyConnections(Heap heap, int mode) {

    assert(heap->n != 0);

    if (heap->n == 1) return heap->val[0];

    if (mode == MAX_CONNECTED_WEIGHTED_AT_RANDOM) {// Unsupported: nbE4Con is not up to date
        nbE4Con = 0;
        for (int i = 0; i < heap->n; i ++)
            nbE4Con += nbN4Con[heap->val[i]];
        return chooseWeightedRandom(nbN4Con, heap->val, heap->n, nbE4Con);
    }

     if (mode == MAX_CONNECTED_BEST_AT_RANDOM)
         return heap->val[rand()%nbMax4Con]; // perhaps not a vertex with the max number of neighbors

    return heap->val[0];
}



//
// UNUSED
//

SET set4Con; // the set of vertices that are considered to evaluate connectivity

void updateNeighbors4Con(int u, Graph g) {
    LIST p = g->adj[u];
    while (p != NULL) {
        if (IN(p->val, set4Con) && (conHeap->ind[p->val] != NONE)) {
            nbN4Con[p->val]++;
            heapDecreaseKey(p->val, conHeap);
        }
        p = p->suiv;
    }
}


int vertexMaxConnectivity(int *S, int n, SET V, Graph g) {
    set4Con = V;

    if (conHeap == NULL) {
        conHeap = allocHeap(g->n, hasMoreConnections);
        nbN4Con = malloc(g->n * sizeof(int));
    }

    int best = S[0];
    float eval = connectivity(S[0], S, n, g);

    for (int i = 1; i < n; i ++) {
        float e = connectivity(S[i], S, n, g);
        if (e > eval) {
            eval = e;
            best = S[i];
        }
    }
    return best;
}


// Evaluates the degree of connectivity of a vertice.
// The heap contains the vertices ordered by the number of neighbors in the cluster built from u
float connectivity(int u, int S[], int n, Graph g) {

    int nbVertices = 1, nbEdges = 0;
    float density = 0;

    resetHeap(conHeap);
    for (int i = 0; i < n; i ++)  { heapJustAdd(S[i], conHeap); nbN4Con[i] = 0; }

    heapRemove(u, conHeap);
    updateNeighbors4Con(u, g);

    while (conHeap->n > 0) {
        nbVertices ++;
        nbEdges += nbN4Con[conHeap->val[0]];
        //printf("%d %d density=%.1f\n", nbVertices, nbEdges, density);
        if ((float) nbEdges/nbVertices < density)
            break;
        density = (float) nbEdges/nbVertices;
        int v = heapExtractMin(conHeap);
        updateNeighbors4Con(v, g);
    }
    if (0) printf("cluster %d : %d/%d %d edges density=%.1f\n", u, nbVertices, n, nbEdges, density);
    return density;
}