separator.h

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

#ifndef SRC_SEPARATOR_H
#define SRC_SEPARATOR_H

#include "graph.h"
#include "heap.h"
#include "sets.h"


#define EVAL_0 0
#define EVAL_TREE_HEIGHT_COMPLETE_GRAPH 1
#define EVAL_CARD 2
#define EVAL_SQRT_CARD 3

#define EVAL_MINIMIZE_C 4
#define EVAL_MAX_SOURCE_DENSITY 5

#define EVAL_MIN_A_B 6

#define EVAL_MAX_CDENS_MIN_AB_SIZES 7
#define EVAL_MAX_C_DENSITY 8
#define EVAL_MAX_AB_SIZES_MIN_AB_EDGES 9

#define EVAL_LEVEL_DENSITY 11
#define EVAL_ESSAI 33


#define FLUSH_A_B 0
#define FLUSH_B_A 1



typedef struct separator * Separator;

struct separator {
    Heap A;
    Heap B;
    Heap C;
    int nbABDV; // nb vertices in C that are disconnected from A, B and from themselves
    Graph graph;
};



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

extern int * nbNInABCopy;

extern int *priorities;

extern int nbCallsSepare;


double evalSep(int nA, int nB, int nC, int mA, int mB, int mode, int direction);

int searchSeparator(int *S, int n, SET V, Graph g, Separator theSeparator, int nTries, int nFlushes, int depth);
int separe(int *S, int n, SET V, Graph g, Separator s, int nbFlushs, int mode);
void flushBtoA(Heap A, Heap B, Heap C, SET V, int S[], int n, int mode, int seed, Graph g);
void flushAtoB(Heap A, Heap B, Heap C, SET V, int S[], int n, int mode, Graph g);

void builtBestSeparator(Heap dest, Heap src, Heap C, int nbNdest[], int nbNsrc[], int size, Graph g);

void removeNeighborsFromA(int e, Heap A, Heap B, Heap C, SET V, int *S, int n, Graph g);
void removeNeighborsFromB(int e, Heap A, Heap B, Heap C, SET V, int *S, int n, Graph g);

int isSmallerNeighborsInB(int a, int b);
int isSmallerNeighborsInA(int a, int b);
int compareCVerticesFlushBtoA(int a, int b);
int compareCVerticesFlushAtoB(int a, int b);

void pourCintoA(Heap A, int nbNFrom[], int nbNTo[], int *nbEdges, Heap C, Graph g, int justAdd);

void allocSeparation(Graph g);
void copySeparator(Separator from, Separator to);


void improveSeparation(Separator s, Graph g, int nSteps);
int searchMoveAC(Separator s, Graph g, int movesCB[], int *the);
int searchMoveBC(Separator s, Graph g, int movesCA[], int *the);
void makeMove(int v, Heap source, Heap dest);

Separator newSeparator(int size, Graph g);
int initializeNbNeighbors(SET V, int S[], int n, int pos[], Graph g);
void recoverNbNeighbors(int S[], int n);
void initSeparator(SET V, int *S, int n, Graph g, Separator s);
void printSeparator(Separator s);
int verifySeparator(int *S, int n, Separator s);

void decreaseNbNeighborsInB(int u, Heap B, Heap C, SET V, int S[], int n, Graph g);
void decreaseNbNeighborsInA(int u, Heap A, Heap C, SET V, int S[], int n, Graph g);
void increaseNbNeighborsInA(int u, Heap C, SET V, int S[], int n, Graph g);
void increaseNbNeighborsInB(int u, Heap C, SET V, int S[], int n, Graph g);

void initializePriorities(Graph g);
void randomizePriorities(int S[], int n, Graph g);


#endif //SRC_SEPARATOR_H