//
// 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