tree.c

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

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#include "decompose.h"
#include "graph.h"
#include "tree.h"
#include "sets.h"
#include "utils.h"




Node newNode(int vertex, Graph g) {
    Node v = malloc(sizeof(struct node));
    v->vertex = vertex;
    v->height = 0;
    v->nbhmax = 0;
    v->next = v->prev = v->fbs = v->lbs = NULL;
    v->father = NULL;
    v->nodes = NULL; //allocSet(g->n);
    v->depth = 0;
    v->date = 0;
    return v;
}


void resetNode(Node p) {
    p->fbs = p->lbs = p->next = p->prev = p->father = NULL;
    p->height = 1;
    p->nbhmax = 0;
    //VideSet(p->nodes);
}


// Calculate the height for this node, returns true if height has been modified
int initializeHeight(Node p) {
    int h = p->height;
    p->height = 1;
    Node q = p->fbs;
    p->nbhmax = 0;
    while (q != NULL) {
        if (p->height < q->height+1) { p->height = q->height+1; p->nbhmax = 1; }
        else if (p->height == q->height+1) p->nbhmax ++;
        q = q->next;
    }
    return (p->height != h);
}


// Update heights and number of children with max height for all the nodes
void updateHeights(Node root) {
    Node q = root->fbs;
    while (q != NULL) {
        updateHeights(q);
        q = q->next;
    }
    initializeHeight(root);
}

// Update depths
void updateDepths(Node p, int depth) {
    p->depth = depth;
    Node q = p->fbs;
    while (q != NULL) {
        updateDepths(q, depth + 1);
        q = q->next;
    }
}

// prepare improvement: set depths and heights and free nodes sets for all nodes of the subtree
void updateDepthsAndHeights(Node p, int depth, int verbose) {
    int height = 1;

    if (verbose && (p->depth != depth)) printf("depth node %d : %d -> %d\n", p->vertex, p->depth, depth);
    p->depth = depth;

    Node q = p->fbs;
    while (q != NULL) {
        updateDepthsAndHeights(q, depth + 1, verbose);
        if (q->height+1 > height) height = q->height+1;
        q = q->next;
    }

    if (verbose && (p->height != height)) printf("height node %d : %d -> %d\n", p->vertex, p->height, height);
    p->height = height;

}


void updateDepthsInCriticalBranch(Node p, int depth, Node end) {
    while (1) {
        p->depth = depth;
        if (p == end)
            break;
        p = p->fbs;
        depth ++;
    }
}


void sortNeighborsInBranch(Node p, Graph g) {
    while (p != NULL) {
        int *list = g->lists[p->vertex];
        Introsort(list, list, list+g->nadj[p->vertex]-1);
        p = p->father;
    }
}



int nbNeighborsAbove(Node node, Graph g) {
    int *N = g->slists[node->vertex];
    int nN = g->nadj[node->vertex];
    int nb = 0;

    Node p = node->father;
    while (p != NULL) {
        if (isInSet(p->vertex, NULL, N, nN))
            nb ++;
        p = p->father;
    }
    return nb;
}

// Returns the leftmost deepest node
Node leftmostDeepestNode(Node root) {
    Node p = root;
    while (1) {
        Node q = p->fbs;
        while (q != NULL) {
            if (q->height+1 == p->height)
                break;
            q = q->next;
        }
        if (q == NULL) return p;
        p = q;
    }
}


// the first ancestor whose father is marked with date (that is which is a node of the critical branch)
Node criticalAncestor(Node p, int date) {
    while (p != NULL) {
        if (p->father->date == date) break;
        p = p->father;
    }
    return p;
}


void updateNbDeeperNeighbors(int nbDeeperN[], Graph g) {
    for (int i = 0; i < g->n; i ++) {
        nbDeeperN[i] = 0;
        for (int *p = g->lists[i]; *p != NONE; p ++)
            if (theNodes[*p]->depth > theNodes[i]->depth)
                nbDeeperN[i] ++;
    }
}



// Count at each level the number of critical nodes
void exploreMakeStats(Node node, int depth, int nbCritical[], int *max) {
    Node q = node->fbs;
    while (q != NULL) {
        if (q->height+1 == node->height)
            exploreMakeStats(q, depth+1, nbCritical, max);
        q = q->next;
    }
    nbCritical[depth] ++;
    if (*max < depth) *max = depth;
}

int makeStatsCriticalNodes(Node node, int nbCritical[]) {
    int max = 0;
    for (int i = 0; i < node->height; i ++)
        nbCritical[i] = 0;
    exploreMakeStats(node, 0, nbCritical, &max);
    return max;
}



// update height after insertion of a new child or increase of the height of a child
int incHeightNodeUpdate(Node node, int height) { // node gets height among its children
    if (node->height < height+1) {
        node->height = height+1;
        node->nbhmax = 1;
        return 1;
    }
    if (node->height == height+1) node->nbhmax ++;
    return 0;
}

// update height after removal of a child or decrease of the height of a child
int decHeightNodeUpdate(Node node, int height) { // node looses height among its children
    if (node->height == height+1) {
        if (node->nbhmax-- == 1)
            if (initializeHeight(node))
                return 1;
    }
    return 0;
}



// p looses a child of height height (removal or height decrease).
// Update p and propagate above if necessary.
void updateDecHeightOnBranch(Node p, int height) {
    while (p != NULL) {
        if ( ! decHeightNodeUpdate(p, height))
            break;
        p = p->father;
        height ++;
    }
}

void forceUpdateDecHeightOnBranch(Node p, int height) {
    while (p != NULL) {
        decHeightNodeUpdate(p, height);
        p = p->father;
        height ++;
    }
}


// New child or child height increase
void updateIncHeightOnBranch(Node p, int height) {
    while (p != NULL) {
        if ( ! incHeightNodeUpdate(p, height))
            break;
        p = p->father;
        height ++;
    }
}


// insert node at last position in the list of children
void addChild(Node p, Node father) {

    p->next = NULL;
    p->father = father;

    if (father->fbs == NULL) {
        father->fbs = father->lbs = p;
        p->prev = NULL;
    }
    else {
        father->lbs->next = p;
        p->prev = father->lbs;
        father->lbs = p;
    }
    // updateIncHeightOnBranch(father, p->height); abandoned, it is better to update only once
    incHeightNodeUpdate(father, p->height);
}



void addChildOLD(Node p, Node father) {
    p->next = father->fbs;
    if (father->fbs != NULL) father->fbs->prev = p;
    p->prev = NULL;
    father->fbs = p;
    p->father = father;
    // updateIncHeightOnBranch(father, p->height); abandoned, it is better to update only once
    incHeightNodeUpdate(father, p->height);
}


int removeChild(Node p, Node father) {
    if (father->fbs == p) {
        father->fbs = p->next;
        if (p->next != NULL) p->next->prev = NULL;
        else father->lbs = NULL;
    }
    else {
        p->prev->next = p->next;
        if (p->next != NULL) p->next->prev = p->prev;
        else father->lbs = p->prev;
    }
    //updateDecHeightOnBranch(father, p->height); abandoned, it is better to update only once
    return decHeightNodeUpdate(father, p->height);
}

// Suppose father exists !!
void justRemoveChild(Node node) {
    Node father = node->father;
    if (node == father->fbs)
        father->fbs = node->next;
    else {
        Node p = father->fbs;
        while (p->next != node)
            p = p->next;
        p->next = node->next;
    }
}


void addSibling(Node p, Node sibling) {
    assert(sibling != NULL);
    Node next = sibling->next;

    p->next = next;
    if (next != NULL) next->prev = p;
    sibling->next = p;
    p->prev = sibling;

    p->father = sibling->father;
    if (p->father != NULL)
        incHeightNodeUpdate(p->father, p->height);
}

void connectSiblings(Node u, Node v) {
    u->next = v;
    v->next = NULL;
    u->prev = NULL;
    v->prev = u;
}

void connect3Siblings(Node u, Node v, Node w) {
    u->next = v;
    v->next = w;
    w->next = NULL;
    u->prev = NULL;
    v->prev = u;
    w->prev = v;
}


Node bottomNode;

Node makeSingleBranch(int S[], int n, int nbNInAB[], Graph g) {
    // put at bottom those which have the fewer neighbors in A and B

    if (1 && nbNInAB != NULL)
        QSort1(S, nbNInAB, 0, n-1);

    if (n == 0)
        return NULL;

    Node node, father;

    bottomNode = node = theNodes[S[0]];
    resetNode(bottomNode);

    for (int i = 1; i < n; i ++) {
        father = theNodes[S[i]];
        resetNode(father);
        addChild(node, father);
        node = father;
    }

    return node;
}

// Make a single branch with nodes S[nbDV],...,S[n-1] with independent children S[0],...,S[nbDV-1]
Node makeSingleBranchWithDisconnectedVertices(int *S, int n, int nbDV, Graph g) {

    if (n == 0)
        return NULL;

    Node node, father;

    if (n == nbDV) nbDV --;

    bottomNode = node = theNodes[S[nbDV]];
    resetNode(bottomNode);

    for (int i = 0; i < nbDV; i ++) {
        Node child = theNodes[S[i]];
        resetNode(child);
        addChild(child, node);
    }

    for (int i = nbDV+1; i < n; i ++) {
        father = theNodes[S[i]];
        resetNode(father);
        addChild(node, father);
        node = father;
    }

    return node;
}




//
// Modifications
//


void printChildren(Node node) {
    Node p = node->fbs;
    printf("(%d) :: ", node->vertex);
    while (p != NULL) {
        printf("%d(%d),", p->vertex, p->father->vertex);
        p = p->next;
    }
    printf("\n");
}



// pull up the node p. Then p becomes a child of its grandfather
int pullUp(Node p) {
    Node father = p->father;
    assert(father != NULL);
    Node gfather = father->father;
    assert(gfather != NULL);
    int hbefore = gfather->height;
    int trace = 0;

    if (trace) { printf("\npull up %d:h=%d father=%d gfather=%d \n", p->vertex, p->height, father->vertex, gfather->vertex);printTree(gfather); }

    int prevHeight = father->height;
    if (removeChild(p, father))
        decHeightNodeUpdate(gfather, prevHeight); // indeed gfather height is perhaps not good here

    if (trace) { printf("pull up :: after remove %d :: father=%d gfather=%d\n", p->vertex, father->vertex, gfather->vertex);printTree(gfather);}

    addChild(p, gfather);

    if (trace) { printf("pull up :: after addChild ::  father=%d gfather=%d \n", father->vertex, gfather->vertex);printTree(gfather); }
    //printf(" --->  %d:h=%d father=%d gfather=%d\n", p->vertex, p->height, father->vertex, gfather->vertex);

    return (gfather->height != hbefore);
}



//
// Forks: from a node u, the longest branch such that each node has a uniq child dependent with u
//
// Goal: the fork is not a critical node, but there are critical nodes on the path.
// Then, pushing down the source node as a child of the fork has as effect to pull up all subtrees
// connected on the path, in particular those that were critical.
Node theFork; // the fork
int forkIsCritical; // if the fork is a critical node, that is some leaves are at the maximal depth
Node theFirstSon; // the first dependent son in the branch
Node *dependentChildren = NULL; // The children of the fork that are dependent with the source node
int delta = 0; // Depth difference between nodes under the fork and the other nodes of the subtree
// If delta=1 the swap has no effect on the height of the subtree. If delta>1 the height decreases of 1.
int maxDepthForkSwaps = 33; // under this depth abandon
Node theRoot;
int searchSomeSwapsAtRandom = 1;

void searchForksSwaps(Node root, Graph g, int maxdepth) {
    theRoot = root;
    maxDepthForkSwaps = maxdepth;
    //while (exploreAndSearchForks(root, 0, g))
    exploreAndSearchForks(root, 0, g);
    {
        if (!verifyTree(root, 0)) {printf("swap fork error 00: node u\n"); exit(0); }
    }
}

// NOTE:: it is not necessary to search the fork, it is sufficient to swap whenever delta > 1

int exploreAndSearchForks(Node node, int depth, Graph g) {
    int len;

    if (dependentChildren == NULL) dependentChildren = malloc(g->n* sizeof(Node));

    if (node->fbs == NULL) return 0;

    if (node->father != NULL) {
        //printf("[%d] search fork for %d h=%d :\n", depth, node->vertex, node->height);
        len = searchFork(node, g);
        if ( (delta > 1) || ((delta == 1) && (rand()%2)) ) {
            printf("[%d] fork swap h_u=%d h_fork=%d len=%d* delta=%d\n", depth, node->height, theFork->height, len, delta);
            swapFork(node, theFork, g);
            return 1;
        }
        //else printf("[%d] %d l=%d\n", depth, node->vertex, len);
    }

    if (depth > maxDepthForkSwaps)
        return 0;

    Node p = node->fbs;
    while (p != NULL) {
        if (p->height == node->height-1) {  // ignore non critical nodes
            exploreAndSearchForks(p, depth + 1, g);
            //if ( ! exploreAndSearchForks(p, depth + 1, g)) return 0;
        }
        p = p->next;
    }
    return 1;
}

// Search the fork. delta is the difference of maximal depth considering just the nodes of
// the fork or all the nodes of the subtree u
int searchFork(Node u, Graph g) {
    int len = 0, nbdep;
    Node the;
    int trace = 0;

    theFork = u;
    forkIsCritical = 1; // u is a critical node
    theFirstSon = NULL;
    delta = 0;

    while (1) {
        Node q = theFork->fbs;
        nbdep = 0;

        while (q != NULL) {
            if ( ! independent(u->vertex, q, g)) {
                dependentChildren[nbdep] = q;
                nbdep++;
                the = q;
                if (q->height+1 < theFork->height) forkIsCritical = 0;
            }
            q = q->next;
        }
        dependentChildren[nbdep] = NULL;

        if (nbdep == 0) return -len;

        if (nbdep > 1) return len;

        if (trace) printf("the=%d h_the=%d\n", the->vertex, the->height);

        // A uniq dependent child, its height is the->height, delta is the difference
        // between its height and the height of its father +1. If 0 this means that the is a
        // critical node.
        delta += (theFork->height-1-the->height);
        if (theFirstSon == NULL) theFirstSon = the;
        theFork = the;
        len ++;
    }
    return 0;
}



// Push down the source node as a child of the fork. Children of the fork that are dependent with the
// source node are pushed down as children of the source. Suppose that u is not fork and not root.
int nbSwaps = 0;

Node swapFork(Node u, Node fork, Graph g) {
    assert(u != fork);
    assert(u->father != NULL); // this particular case should be considered a part (u must have a uniq son)
    Node father = u->father;
    int heightFather = father->height;

    nbSwaps ++;

    // remove u from father children
    removeChild(u, father);

//    updateHeights(father);
//    printf("father height 1 : %d --> %d\n", heightFather, father->height);

    // pull up u children (even theFirstSon)
    Node q = u->fbs;
    while (q != NULL) {
        Node next = q->next;
        removeChild(q, u);
        addChild(q, father);
        q = next;
    }
    // here u has no child

//    updateHeights(father);
//    printf("father height 2 : %d \n", father->height);
    int forkHeight = fork->height;

    // transfer fork children that are dependent with u, as new children of u
    //resetNode(u);
    //u->fbs = NULL; //p->lbs = p->next = p->prev = p->father = NULL;
    //u->height = 1;
    //u->nbhmax = 0;

    if (1) for (Node *pp = dependentChildren; *pp != NULL; pp++) {
        removeChild(*pp, fork);
        addChild(*pp, u);
    }

    if (0) {
        q = fork->fbs;
        resetNode(u);
        while (q != NULL) {
            Node next = q->next;
            if (!independent(u->vertex, q, g)) {
                removeChild(q, fork);
                addChild(q, u);
            }
            q = next;
        }
    }


    //updateHeights(father);
    //printf("father height 3 : %d \n", father->height);

    // Add u as a child of fork
    addChild(u, fork);

    //updateHeights(father);
    //printf("father height 4 : %d \n", father->height);

    Node root;
    while (u != NULL) {
        root = u;
        initializeHeight(u);
        u = u->father;
    }
    if (!verifyTree(root, 0)) {printf("swap fork error 1: node u\n"); exit(0); }

    //printf("father height :: %d --> %d\n", heightFather, father->height);

    if (heightFather < father->height) {
        printTree(father);
        exit(0);
    }

    if (0) {
        // Update...
        printf("updating: \n");
        printf("   u:%d  h=%d\n", u->vertex, u->height);
        printf("   fork:%d  h=%d\n", fork->vertex, fork->height);
        printf("   father:%d  h=%d\n", father->vertex, father->height);
        if (father->father != NULL)
            printf("   father->father:%d  h=%d\n", father->father->vertex, father->father->height);

        initializeHeight(u);
        initializeHeight(fork);
        if (fork->height != forkHeight) {
            updateIncHeightOnBranch(fork->father, fork->height);
        }
        if (!verifyTree(u, 0)) printf("swap fork verify 1: node u\n");

        initializeHeight(father);
        if (father->height < heightFather)
            updateDecHeightOnBranch(father->father, heightFather);

        printf("   u:%d  h=%d\n", u->vertex, u->height);
        printf("   fork:%d  h=%d\n", fork->vertex, fork->height);
        printf("   father:%d  h=%d\n", father->vertex, father->height);
        if (father->father != NULL)
            printf("   father->father:%d  h=%d\n", father->father->vertex, father->father->height);

        if (!verifyTree(u->father, 0)) printf("swap fork verify 2: u->father\n");
        if (!verifyTree(father, 0)) printf("swap fork verify 3: root\n");
        if ((father->father != NULL) && (!verifyTree(father->father, 0))) printf("swap fork verify 4: root->father\n");
    }

    return father;
}



//
// Independent subtrees: computation
//

int indpdNbCalls = 0;

SET nodesInSubtrees = NULL;

void makeNodesInSubtrees(Node node) {
    Node p = node->fbs;
    while (p != NULL) {
        makeNodesInSubtrees(p);
        p = p->next;
    }
    ADDe(node->vertex, nodesInSubtrees);
}


int independent(int v, Node tree, Graph g) {

    indpdNbCalls++;

    if (nodesInSubtrees == NULL) nodesInSubtrees = allocSet(g->n);

    clearSet(nodesInSubtrees);
    makeNodesInSubtrees(tree);

    LIST p = g->adj[v];
    while (p != NULL) {
        if (IN(p->val, nodesInSubtrees))
            return 0;
        p = p->suiv;
    }
    return 1;
}


//
// Sets of nodes (for swap in critical branches)
//


void makeAllSetsOfNodes(Node node, Graph g) {
    Node q = node->fbs;
    while (q != NULL) {
        makeAllSetsOfNodes(q, g);
        q = q->next;
    }
    if (node->nodes == NULL) node->nodes = allocSet(g->n);
    else clearSet(node->nodes);
    q = node->fbs;
    while (q != NULL) {
        addSet(q->nodes, node->nodes);
        q = q->next;
    }
}


// Construct sets of nodes for a given node, and for its children, suppose children sets do not exist
void exploreAndBuildSetOfNodes(Node p, SET V) {
    ADDe(p->vertex, V);
    Node q = p->fbs;
    while (q != NULL) {
        exploreAndBuildSetOfNodes(q, V);
        q = q->next;
    }
}

void buildSetOfNodes(Node p, Graph g) {

    if (p->nodes != NULL) return;

    p->nodes = allocSet(g->n);

    SET V = p->nodes;

    //clearSet(V);
    ADDe(p->vertex, V);

    Node q = p->fbs;
    while (q != NULL) {
        if (q->nodes == NULL) {
            q->nodes = allocSet(g->n);
            exploreAndBuildSetOfNodes(q, q->nodes);
        }
        addSet(q->nodes, V);
        q = q->next;
    }
}

void updateSetOfNodes(Node p, Graph g) {

    if (p->nodes == NULL) p->nodes = allocSet(g->n);

    SET V = p->nodes;

    clearSet(V);
    ADDe(p->vertex, V);

    Node q = p->fbs;
    while (q != NULL) {
        assert (q->nodes != NULL);
        addSet(q->nodes, V);
        q = q->next;
    }
}



void freeSetsOfNodes(Node nodes[], int nb) {

    for (int i = 0; i < nb; i ++) {
        free(nodes[i]->nodes);
        nodes[i]->nodes = NULL;
    }
}



//
// Verifications
//


int verifyNode(Node root) {

    if (root == NULL)
        return NONE;

    int height = 1;
    Node p = root->fbs;

    while (p != NULL) {
        if (p->height+1 > height)
            height = p->height+1;
        p = p->next;
    }

    if (root->height != height)
        return height;
    return NONE;
}

// Verify heights in nodes
int verifyTree(Node root, int depth) {
    int height;

    if (root == NULL)
        return 1;

    Node p = root->fbs;
    int vertex;
    if (p != NULL)
        vertex = p->vertex;

    while (p != NULL) {
        if ( ! verifyTree(p, depth+1))
            return 0;
        p = p->next;
        if ((p != NULL) && (p->vertex == vertex)) {
            printf("children list loops !!\n");
            exit(0);
        }
    }

    height = verifyNode(root);
    if (height != NONE) {
        printf("bad height node %d at depth %d : height is %d should be %d\n", root->vertex, depth, root->height, height);
        return 0;
    }

    return 1;
}


void exploreAndPrint(Node node, int depth) {
    for (int i = 0; i < depth; i ++) printf(" -");
    printf("[%d:%dx%d]\n", node->vertex, node->height, node->nbhmax);
    Node p = node->fbs;
    if (p == NULL)
        return;
    //printf("(");
    while (p != NULL) {
        exploreAndPrint(p, depth+1);
        p = p->next;
        if (p != NULL) printf(",");
    }
    //printf(")");
}

void printTree(Node node) {
    exploreAndPrint(node, 0);
    printf("\n");
}


int sizeForest(Node node) {
    int nb = 0;
    while (node != NULL) {
        nb += 1+ sizeForest(node->fbs);
        node = node->next;
    }
    return nb;
}


int sizeTree(Node node) {
    if (node == NULL) return 0;
    int nb = 1;
    Node p = node->fbs;
    while (p != NULL) {
        nb += sizeTree(p);
        p = p->next;
    }
    return nb;
}



int treeContains(int e, Node p) {
    if (p == NULL) return 0;
    if (p->vertex == e) return 1;
    for (Node q = p->fbs; q != NULL; q = q->next)
        if (treeContains(e, q))
            return 1;
    return 0;
}

int treeContainsNeighbors(int v, Node tree, Graph g) {
    int nb = 0;
    for (int *p = g->lists[v]; *p != NONE; p ++)
        if (treeContains(*p, tree))
            nb ++;
    return nb;
}