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
//
// Created by Stephane on 10/03/2020.
//
#ifndef SRC_DECOMPOSE_H
#define SRC_DECOMPOSE_H
#include <stdio.h>
#include "graph.h"
#include "separator.h"
#include "sets.h"
#include "tree.h"
#define SEPARE_AND_EXPLORE 0
#define GREEDY_ALGORITHM 1
#define SIZE_SMALL_TREE 3
extern int *bestTree;
extern int bestHeight;
extern Separator separator;
extern Node * theNodes;
extern int time_limit;
void updateBestDecomposition(Node root, Graph g);
void testDecompose(Graph g, int nbRuns, int algo);
Node decompose(int *S, int n, int pos[], int depth, Graph g, int hmax, int connected);
Node greedyDecompose(Heap conHeap, int depth, Graph g, int hmax, int connected);
Node makeListWithUnconnectedVertices(Heap heap, Graph g, Node *last);
Node makeSmallTree(int *S, int n, Graph g);
Node decomposeConnectedComponents(int *iComp, int nbComp, int *S, int n, int pos[], int depth, Graph g, int hmax);
Node greedyDecomposeComponents(int iComp[], int nbComp, Heap conHeap, int depth, Graph g, int hmax);
int isSmallerNeighborsInB(int a, int b);
void allocNodes(Graph g);
void allocSets(Graph g, int max);
void reAllocSets(int size, Graph g);
void allocComponents(Graph g, int max);
void reAllocComponents(Graph g, int size);
void PACEOutput(FILE *file, int height, int fathers[], Graph g);
void saveToTable(int T[], Graph g);
Node buildTreeFromTable(int T[], Graph g);
int verifyDecomposition(Node tree, Graph g);
void printStatsOnCriticalNodes(Node root, int *nbCriticalNodes);
#endif //SRC_DECOMPOSE_H