bary_functions.c

Go to the documentation of this file.

#include "bary.h"
#include <stdlib.h>
#define STATIC 


STATIC int compare_bary 
(const GNODE * a, const GNODE * b)
{ 
    if ((((*a)->bary) == 0.0) || (((*b)->bary) == 0.0)) return (0); 
    if (((*a)->bary) > ((*b)->bary)) return (1); 
    if (((*a)->bary) < ((*b)->bary)) return (-1); 
    return (0);
}



//resort_up_down_layer and resort_down_up_layer could be merged if we know what operation to perform first :
//add in a direction parameter, and if the direction is up, go up, else go down. 
STATIC void resort_up_down_layer (int level)
{ int change; int i; change = 1;
 if (level > 0) { for (i = level - 1; i >= 0; i--) {// INDEX2
     change = resort_up_layer (i); // branch up
     if (!change) break; } }
 if (level <= maxdepth) { for (i = level; i <= maxdepth; i++) {// INDEX1
     change = resort_down_layer (i); // branch down
     if (!change) break; } }}

STATIC void resort_down_up_layer (int level)
{ int change; int i; change = 1;
 if (level <= maxdepth) { for (i = level; i <= maxdepth; i++) { // INDEX1
     change = resort_down_layer (i); // branch down
     if (!change) break; } }
 if (level > 0) { for (i = level - 1; i >= 0; i--) {// INDEX2
     change = resort_up_layer (i); // brach up
     if (!change) break; } }
}


/*
  SORT THE SUCCLIST by the nhorder field

  get the succ list from a node in the layer
  for each item :
       fill the sort array
       set the bary field from the nhorder field
  sort the array by bary
  put the array back into the succ list, but in a sorted order
 */
void apply_horder (int i)
{ 
    GNLIST hn; 
    int j;
    hn = ((tmp_layer[i]).succlist); 
    j = 0; 

    while (hn)     { 
        if (((((hn)->node))->nhorder) >= 0) 
        { 
            sort_array[j++] = ((hn)->node); 
            ((((hn)->node))->bary) = ((((hn)->node))->nhorder); 
        } 
        hn = ((hn)->next); 
    } 
    if (j) qsort (sort_array, j, sizeof (GNODE), (int (*)(const void *, const void *)) compare_bary); 
    hn = ((tmp_layer[i]).succlist); 
    j = 0; 

    while (hn) { 
        if (((((hn)->node))->nhorder) >= 0) 
            ((hn)->node) = sort_array[j++]; 
        hn = ((hn)->next); 
    }
}



//recursive function
//calculates bary for horder functions

STATIC void mark_all_nodes (GNODE node, int i)
{
    ADJEDGE e;
    if (((node)->bary)) return; 
    if (((node)->nhorder) >= 0)
        ((node)->bary) = (float) i *(float) (max_horder_num + 1) + (float) ((node)->nhorder); 
    else 
        ((node)->bary) = (float) i *(float) (max_horder_num + 1); 
    e = ((node)->succ); 
    while (e) { 
        mark_all_nodes ((((((e)->kante))->end)), i); 
        e = ((e)->next); 
    } 

    e = ((node)->pred); 
    while (e) { 
        mark_all_nodes ((((((e)->kante))->start)), i); 
        e = ((e)->next); 
    }

}

STATIC void phase1_down (void){ 
    int i;
    gs_wait_message ('b'); 
    for (i = 0; i <= maxdepth; i++) 
        (void) resort_down_layer (i);
}

STATIC void phase1_up (void){ 
    int i;
    gs_wait_message ('b'); 
    for (i = maxdepth; i >= 0; i--)
        (void) resort_up_layer (i);
}




// cycle/rotates the array!
// this has got to be slow!
// siz > j
// sort_array

// j goes from 0 to the size of the layer
// 
STATIC int cycle_sort_array (int siz)
{ 
    int j, k; 
    int original_sit; 
    int start_region; 
    GNODE h; 
    original_sit = 1; // is there no change?
    start_region = -1;  // is there a run
    for (j = 0; j < siz - 1; j++) { 

        // is there a run in the array?
        if (((sort_array[j])->bary) == ((sort_array[j + 1])->bary)) { 

            // set the start region to be the beginning of the run
            if (start_region == -1) 
                start_region = j; 
        } 
        else if (start_region != -1) // there is a run already?
        { 
            // void runsort(j,start_region,original_sit) 
            h = sort_array[j]; 

            //k=j .down.to..> start region
            for (k = j; k > start_region; k--) 
                sort_array[k] = sort_array[k - 1]; 

            sort_array[start_region] = h; // the beginning of the start region
        
            // set the flag
            start_region = -1; 
            original_sit = 0; 

        } 
    } 

    if (start_region != -1) 
    { 
        // void runsort(j,start_region,original_sit) 
        h = sort_array[j]; 
        for (k = j; k > start_region; k--) 
            sort_array[k] = sort_array[k - 1]; 
        sort_array[start_region] = h; 
        original_sit = 0; 
    } 

    return (!original_sit);
}



// uses a set of temp variables :
// 1. weights per edge
// 2. marking
// these variables can be stored in a vector and disposed of easier than with a list
// uses list traversals, these can also be represented with an array.
// todo : create an iterator abstraction so that the representation can be abstracted.
STATIC void tree_horizontal_order (void)
{ 
    GNLIST li; 
    int i, prio; 
    GNODE node; 
    ADJEDGE a; 
    GEDGE e; 
    double maxbary;

    //  init each layer, following the succ list , setting the weights to 0
    for (i = 0; i <= maxdepth + 1; i++){  
        // for each successor in the list 1
        li = ((tmp_layer[i]).succlist);  // for each layer
        while (li){ 
            a = li->node->succ;
            while (a){ a->kante->weights=0;a = a->next; }  // follow the next in the succ list of the node
            li = li->next; 
        } // follow the next in the succ list of the layer
    }

// for each depth, and in the order of priority,
// visit each node in the graph
// get each edge, and the end of the edge,
// mark the node if not marked, and the set the weight edge to 1

    for (i = 0; i <= maxdepth + 1; i++) { 
        for (prio = max_eprio; prio >= 0; prio--) {  // for each prio
        // for each successor in the list 2
            li = ((tmp_layer[i]).succlist);  // start to follow the succ list
            while (li) { 
                a = ((((li)->node))->succ); // follow the node succ list
                while (a) { 
                    e = ((a)->kante); 
                    if (((e)->priority) == prio) { // check the priority
                        node = (((((a)->kante))->end));  // get the end node
                        if (!((node)->markiert)) { 
                            ((node)->markiert) = 1;  // mark the node
                            ((e)->weights) = 1; // set the weights to 1
                        } 
                    } 
                    a = ((a)->next); 
                } 
                li = ((li)->next); 
            }
        }
    }
 
    // second passs
    for (i = 1; i <= maxdepth + 1; i++) { 
        level_to_array (i, 'd');  // convers the level to an array
        maxbary = 0.1; 

        // for each successor in the list 3
        li = ((tmp_layer[i]).succlist); 
        while (li) { 
            node = ((li)->node); 
            ((node)->bary) = predbary (node);  // calc the predbary
            if (((node)->bary) > maxbary) maxbary = ((node)->bary); // calc the maxbary 
            li = ((li)->next); 
        }

        maxbary = maxbary + 1.0; 

        // for each successor in the list 4
        li = ((tmp_layer[i - 1]).succlist); 
        while (li) { 
            a = ((((li)->node))->succ); 
            while (a) { 
                e = ((a)->kante); 
                if (((e)->weights)) { // marked by this algorithm
                    node = (((((a)->kante))->end)); 
                    ((node)->bary) = (double) (((((li)->node))->position)) + ((node)->bary) / maxbary;  // scale the bary down by the max and the position
                } 
                a = ((a)->next); 
            } 
            li = ((li)->next); 
        } 
        
        
        if (((layer[i]).anz)) 
            qsort (sort_array, ((layer[i]).anz), sizeof (GNODE), (int (*)(const void *, const void *)) compare_bary); 
    } 
    array_to_level (i); 
    
    // set the marking to 0
    for (i = 0; i <= maxdepth + 1; i++) 
    { 
        li = ((tmp_layer[i]).succlist); 
        while (li) { 
            ((((li)->node))->markiert) = 0; li = ((li)->next); 
        } 
    } 

    // copy the layers from tmp to main
    copy_layers (layer, tmp_layer);
}

STATIC void unmerge_connected_parts (void){ 
    GNLIST li; 
    int i, j; 
    int part_is_missing; 
    GNODE node; int act_graph;


    // set bary to 0
    for (i = 0; i <= maxdepth + 1; i++) { 
        li = ((tmp_layer[i]).succlist); 
        while (li) { 
            ((((li)->node))->bary) = 0; li = ((li)->next); 
        } 
    } 
    act_graph = 1; 
    part_is_missing = 1; 
    while (part_is_missing) { 
        gs_wait_message ('u'); part_is_missing = 0; node = (GNODE) 0; act_graph++; 
        for (i = 0; i <= maxdepth + 1; i++) { 
            li = ((layer[i]).succlist); 
            while (li) { 
                if (((((li)->node))->bary) == 0) { 
                    node = ((li)->node); break; 
                } 
                li = ((li)->next); 
            } 
            if (node) break; 
        } 
        if (node) { 
            part_is_missing = 1; mark_all_nodes (node, act_graph); 
        } 
    } 
    for (i = 0; i <= maxdepth + 1; i++) { 
        li = ((tmp_layer[i]).succlist); j = 0; 
        while (li) { 
            sort_array[j++] = ((li)->node); li = ((li)->next); 
        } 
        
        if (((layer[i]).anz)) qsort (sort_array, ((layer[i]).anz), sizeof (GNODE), (int (*)(const void *, const void *)) compare_bary); 
        array_to_level (i); 
    } 
    copy_layers (layer, tmp_layer);
}

int mark_all_nodes_merger;


static void copy_layers (DEPTH * l1, DEPTH * l2)
{ 
    int i; 
    GNLIST h1, h2; 
    for (i = 0; i <= maxdepth + 1; i++) 
    { 
        ((l1[i]).cross) = ((l2[i]).cross); 
        h1 = ((l1[i]).succlist); 
        h2 = ((l2[i]).succlist); 
        if (((l1[i]).anz) == ((l2[i]).anz)) 
        { 
            while (h2) { 
                ((h1)->node) = ((h2)->node); 
                h1 = ((h1)->next); 
                h2 = ((h2)->next); 
            } 
        } 
        else 
        { 
            while (h2) { 
                ((h1)->node) = ((h2)->node); 
                h2 = ((h2)->next); 
                if (h2 && !((h1)->next)) 
                    ((h1)->next) = tmpnodelist_alloc (); 
                h1 = ((h1)->next); 
            } 
            ((l1[i]).anz) = ((l2[i]).anz); 
        } 
    }
}


STATIC void save_level (int i){ 
    int j; GNLIST hn; ; j = 0; 
    hn = ((tmp_layer[i]).succlist); 
    while (hn) { 
        save_array[j++] = ((hn)->node); 
        hn = ((hn)->next); 
    } 
}

STATIC void restore_level (int i){
    int j; GNLIST hn; ; j = 0; 
    hn = ((tmp_layer[i]).succlist); 
    while (hn) { 
        ((hn)->node) = save_array[j++]; 
        hn = ((hn)->next); 
    }
}

STATIC int have_alternative;
STATIC int phase1_allowed; 
STATIC void  init_barycentering (void){ 
    have_alternative = 0; 
    phase1_allowed = 1;
}

void barycentering (void)
{
    int alt; 
    int cross; 
    int changed; 
    int tmp_startlevel, alt_startlevel; 
    tmp_startlevel = alt_startlevel = 0; 
    changed = 1; 
    while (phase1_allowed && changed) 
    { 
        nr_bary_iterations++; 
        if (nr_bary_iterations >= max_baryiterations) 
        { 
            gs_wait_message ('t'); 
            break; 
        } 
        if (G_timelimit > 0) if (test_timelimit (60))  
        { 
            gs_wait_message ('t'); 
            break; 
        } 
        changed = 0; 
        phase1_down (); 
        cross = graph_crossings (); 
        alt = 0; 
        if ((cross < nr_crossings) || (nr_bary_iterations < min_baryiterations))  
        { 
            changed = 1; 
            copy_layers (layer, tmp_layer); 
            nr_crossings = cross; 
            alt_startlevel = tmp_startlevel;        
        } 
        else if (have_alternative)  
        { 
            copy_layers (tmp_layer, layer); 
            phase1_down (); 
            cross = graph_crossings (); 
            if (cross < nr_crossings)  
            { 
                changed = 1; 
                copy_layers (layer, tmp_layer); 
                nr_crossings = cross; 
                alt_startlevel = tmp_startlevel; 
            } 
            else if (cross > nr_crossings)  
            { 
                copy_layers (tmp_layer, layer); 
                tmp_startlevel = alt_startlevel; 
            } 
            else 
                alt = 1; 
        } else if (cross == nr_crossings) 
            alt = 1; 
        else  
        {          
            copy_layers (tmp_layer, layer); 
            tmp_startlevel = alt_startlevel; 
        } 
        have_alternative = alt; 
        phase1_up (); 
        cross = graph_crossings (); 
        alt = 0; 
        if ((cross < nr_crossings) || (nr_bary_iterations < min_baryiterations))  
        {          
            changed = 1;     
            copy_layers (layer, tmp_layer); 
            nr_crossings = cross; 
            alt_startlevel = tmp_startlevel; 
        } 
        else if (have_alternative)  
        { 
            copy_layers (tmp_layer, layer); 
            phase1_up (); 
            cross = graph_crossings (); 
            if (cross < nr_crossings)  
            { 
                changed = 1;                
                copy_layers (layer, tmp_layer); 
                nr_crossings = cross; 
                alt_startlevel = tmp_startlevel; 
            } 
            else if (cross > nr_crossings)  
            { 
                copy_layers (tmp_layer, layer); 
                tmp_startlevel = alt_startlevel;                
            } 
            else 
                alt = 1; 
        } else if (cross == nr_crossings) 
            alt = 1; 
        else  
        {           
            copy_layers (tmp_layer, layer); 
            tmp_startlevel = alt_startlevel; 
        } 
        have_alternative = alt; 

        if (nr_crossings == 0) 
            return; 
 
    } 
    if (nr_crossings == 0) 
        return; 
 
    if (skip_baryphase2) 
        return; 
 
    phase1_allowed = 0; 
    tmp_startlevel = alt_startlevel = 0; 
    changed = 1; 
    while (changed)  
    { 
        nr_bary_iterations++; 
        if (nr_bary_iterations >= max_baryiterations)  
        { 
            gs_wait_message ('t'); 
            break; 
        } 
        if (G_timelimit > 0) if (test_timelimit (60))  
        { 
            gs_wait_message ('t'); 
            break; 
        } 
        changed = 0; 
        phase2_startlevel = tmp_startlevel; 
        phase2_down (); 
        tmp_startlevel = phase2_startlevel; 
        
        if (tmp_startlevel > maxdepth) tmp_startlevel = 0; 
        cross = graph_crossings (); 
        alt = 0; 
        
        if (cross < nr_crossings)  
        { 
            changed = 1; 
            copy_layers (layer, tmp_layer); 
            nr_crossings = cross; 
            alt_startlevel = tmp_startlevel; 
        } 
        else if (have_alternative)  
        { 
            copy_layers (tmp_layer, layer); 
            phase2_startlevel = tmp_startlevel = alt_startlevel; 
            phase2_down (); 
            tmp_startlevel = phase2_startlevel; 
            if (tmp_startlevel > maxdepth) tmp_startlevel = 0; 
            cross = graph_crossings (); 
            if (cross < nr_crossings)  
            { 
                changed = 1; 
                copy_layers (layer, tmp_layer); 
                nr_crossings = cross; 
                alt_startlevel = tmp_startlevel; 
            } 
            else if (cross > nr_crossings)  
            { 
                copy_layers (tmp_layer, layer); 
                tmp_startlevel = alt_startlevel; 
            } 
            else alt = 1; 
        } else if (cross == nr_crossings) alt = 1; 
        else  
        {          
            copy_layers (tmp_layer, layer);         
            tmp_startlevel = alt_startlevel; 
        } 
        have_alternative = alt; 
        
        if (nr_crossings == 0) 
            return;     
    } 

    tmp_startlevel = alt_startlevel = maxdepth + 1; 
    changed = 1; 
    while (changed)  
    { 
        nr_bary_iterations++; 
        if (nr_bary_iterations >= max_baryiterations)  
        { 
            gs_wait_message ('t'); 
            break; 
        } if (G_timelimit > 0) if (test_timelimit (60))  
        { 
            gs_wait_message ('t'); 
            break; 
        } changed = 0; 
        phase2_startlevel = tmp_startlevel; 
        phase2_up (); 
        tmp_startlevel = phase2_startlevel; 
        if (tmp_startlevel < 0) tmp_startlevel = maxdepth; 
        cross = graph_crossings (); 
        alt = 0; 
        if (cross < nr_crossings)  
        { 
            changed = 1; 
            copy_layers (layer, tmp_layer); 
            nr_crossings = cross; 
            alt_startlevel = tmp_startlevel; 
        } else if (have_alternative)    { 

            copy_layers (tmp_layer, layer); 
            phase2_startlevel = tmp_startlevel = alt_startlevel; 
            phase2_up (); 
            tmp_startlevel = phase2_startlevel; 
            if (tmp_startlevel < 0) tmp_startlevel = maxdepth; 
            cross = graph_crossings (); 
            if (cross < nr_crossings)  
            { 
                changed = 1; 
                copy_layers (layer, tmp_layer); 
                nr_crossings = cross; 
                alt_startlevel = tmp_startlevel; 
            } 
            else if (cross > nr_crossings)  
            { 
                copy_layers (tmp_layer, layer); 
                tmp_startlevel = alt_startlevel; 
            } 
            else 
                alt = 1; 
        } else if (cross == nr_crossings) alt = 1; 
        else  
        { 
            copy_layers (tmp_layer, layer); 
            tmp_startlevel = alt_startlevel; 
        } 
        have_alternative = alt; 
        if (nr_crossings == 0) 
            return; 
    }
}

---