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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//
// Created by Stephane on 10/03/2020.
//
#ifndef SRC_TREE_H
#define SRC_TREE_H
#include "graph.h"
#include "sets.h"
typedef struct node * Node;
struct node {
int vertex;
Node fbs; // first child
Node lbs; // last child
Node next;
Node prev;
Node father;
//int size;
int height;
int nbhmax; // the number of children with max height
SET nodes;
int depth;
int date; // for swaps, to mark nodes of the critical branch at this moment
};
extern Node bottomNode;
Node newNode(int vertex, Graph g);
void resetNode(Node p);
int initializeHeight(Node p);
void updateHeights(Node root);
void updateDepths(Node p, int depth);
void updateDepthsAndHeights(Node p, int depth, int verbose);
void updateDepthsInCriticalBranch(Node p, int depth, Node end);
void sortNeighborsInBranch(Node p, Graph g);
int nbNeighborsAbove(Node p, Graph g);
Node leftmostDeepestNode(Node root);
Node criticalAncestor(Node p, int date);
void updateNbDeeperNeighbors(int nbDeeperN[], Graph g);
int makeStatsCriticalNodes(Node node, int nbCritical[]);
void updateDecHeightOnBranch(Node p, int height);
void updateIncHeightOnBranch(Node p, int height);
int decHeightNodeUpdate(Node node, int height);
int incHeightNodeUpdate(Node node, int height);
void forceUpdateDecHeightOnBranch(Node p, int height);
void addChild(Node p, Node father);
int removeChild(Node p, Node father);
void justRemoveChild(Node node);
void addSibling(Node p, Node sibling);
void connectSiblings(Node u, Node v);
void connect3Siblings(Node u, Node v, Node w);
Node makeSingleBranch(int S[], int n, int nbNInAB[], Graph g);
Node makeSingleBranchWithDisconnectedVertices(int *S, int n, int nbDV, Graph g);
int pullUp(Node p);
void searchForksSwaps(Node root, Graph g, int maxdepth);
int exploreAndSearchForks(Node node, int depth, Graph g);
int searchFork(Node u, Graph g);
Node swapFork(Node u, Node fork, Graph g);
void makeAllSetsOfNodes(Node node, Graph g);
void exploreAndBuildSetOfNodes(Node p, SET V);
void buildSetOfNodes(Node p, Graph g);
void updateSetOfNodes(Node p, Graph g);
void freeSetsOfNodes(Node nodes[], int nb);
int independent(int v, Node tree, Graph g);
int verifyTree(Node root, int depth);
void printTree(Node node);
int sizeForest(Node node);
int sizeTree(Node node);
int treeContains(int e, Node p);
int treeContainsNeighbors(int v, Node tree, Graph g);
#endif //SRC_TREE_H