Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//
// 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);
int isABetterSeparator(Separator best, Separator s);
void copySeparator(Separator from, Separator to);
void selectABDisconnectedVertices(Separator sep, SET V, int *S, int n, int date, Graph g);
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 removeFromB(int v, Separator s);
//void removeFromC(int v, Separator s);
//void addInC(int v, 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);