separator.c

//
// Created by Stephane on 10/03/2020.
//

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


#include "components.h"
#include "graph.h"
#include "main.h"
#include "separator.h"
#include "utils.h"
#include "heap.h"



// Options separation
int chooseSeedNeighborMaxDegree = 0;

int separatorJustMemorizeReceptorSize = 1;
int separatorJustMemoSizeMin = 10000;

int verifyTheSeparator = 0;


int useMinPartitions = 2; // 0: maintain heap, 1-2: just put min elements at the beginning.
// 1: maintain mins   2: calculate mins only when necessary



//
// Datas structures
//

int *nbNeighborsInB;
int *nbNeighborsInA;
int nbEdgesInA, nbEdgesInB;

int *dateABDisconnected; // Current date for AB Diconnected vertices of C (date=number of current separe call)
int *nbNeighborsABDisconnected; // For AB Disconnected vertices : Number of neighbors in C which are AB disconnected

int *priorities;

int *verticesToThrow;

// Copies to memorize nb neighbors and not recalculate at each separation run
int * nbNInDestCopy; // To build the best separator
int * nbNInABCopy; // To memorize the number of neighbors in A an B of C vertices for best separator
int * nbNeighborsInS;
int nbEACopy, nbEdgesInS;
int minDegree, nbMinD; // minimal degree of vertices of S, initialised in initializeNbNeighbors()
int maxDegree, nbMaxD;


int nbCallsSepare = 0;

int nbCallsSearchSeparator = 0;

Separator sep = NULL;
Separator bestSep = NULL;
double bestEval;
int bestIsUninitialized;


int sizeMin;
int sizeMax;


// Connected components
int *component;


//
// Warning: the preliminary call to initializeNbNeighbors() place first in the lists of neighbors
// those that are in the current set S[]. It is then unnecessary to verify each time that the vertex
// belongs to the current set.

#ifdef STATS_SEPARATION
clock_t *timesSep = NULL;
int *nbSearches;
int *sumSizes;
#endif

int searchSeparator(int *S, int n, SET V, Graph g, Separator theSeparator, int nTries, int nFlushes, int depth) {

#ifdef STATS_SEPARATION
    if (timesSep == NULL) {
        timesSep = calloc(10000, sizeof(clock_t));
        nbSearches = calloc(10000, sizeof(int));
        sumSizes = calloc(10000, sizeof(int));
    }
#endif

    if (sep == NULL) sep = newSeparator(g->n, g);
    if (bestSep == NULL) bestSep = newSeparator(g->n, g);

    nbCallsSearchSeparator ++;

    theSeparator->C->n = g->n+1;
    bestEval = -1.0;
    bestIsUninitialized = 1;

    sizeMin = n * ratioMin / 100;
    if (sizeMin == 0) sizeMin = 1;

    sizeMax = n * ratioMax / 100;

    if ((g->n > 300000) && (depth < 6)) nbRunsSeparation = 1; // avoids WA ?

    //saveNbNeighbors(S, n);

    if (modeEvalAtRandom) {
        if (rand()%2 == 1) modeEvalSeparator = EVAL_CARD;
        else modeEvalSeparator = rand() % 4;
    }

    if (0) {
        // test for heur_105: much better when equal to 0
        perForceChoiceNotInC = 0;
        perChooseInCAtRandom = 0;
    }

    clock_t start = clock();

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

        randomizePriorities(S, n, g);

        initSeparator(V, S, n, g, sep);

        separe(S, n, V, g, sep, nFlushes, modeEvalSeparator);

        if ((stopSearch) || ((clock()-start)/CLOCKS_PER_SEC > maxTimeSeparation/(depth+1))) break;
    }

    if (0 && depth < 3) printf("depth=%d  tSep=%.1fs  total=%.1fs\n", depth,
                          (float) (clock()-start)/CLOCKS_PER_SEC,
                          (float) (clock()-startTime)/CLOCKS_PER_SEC);

#ifdef STATS_SEPARATION
    timesSep[depth] += clock()-start;
    nbSearches[depth] ++;
    sumSizes[depth] += n;
#endif

    if (bestIsUninitialized)
        exit(0);

    if (bestEval > 0)
        copySeparator(bestSep, theSeparator);
    else
        copySeparator(sep, theSeparator);

    //if (verifyTheSeparator && (! verifySeparator(S, n, theSeparator))) exit(0);

    return 1;
}




int chooseFirstVertex(int *S, int n, Graph g) {
    if (1) {
        // Test choose as first vertex one with small degree with a neighbor with max degree
        int t = rand() % nbMaxD;
        for (int *p = S;; p++)
            if (nbNeighborsInS[*p] == maxDegree)
                if (t-- == 0) {
                    int *q = g->lists[*p];
                    int vmin = *q;
                    int min = nbNeighborsInS[*q];
                    q ++;
                    while (q < g->lists[*p]+nbNeighborsInS[*p]) {
                        if (nbNeighborsInS[*q] < min) {
                            min = nbNeighborsInS[*q];
                            vmin = *q;
                        }
                        q ++;
                    }
                    return vmin;
                }
        return NONE;
    }
    else {
        int t = rand() % nbMinD;
        for (int *p = S;; p++)
            if (nbNeighborsInS[*p] == minDegree)
                if (t-- == 0) return *p;
        return NONE;
    }

    if (n <= 10) return S[rand()%n];
    int dmin, vmin;
    vmin = S[rand()%n];
    dmin = nbNeighborsInS[vmin];
    for (int i = 0; i < 5; i ++) {