bary_functions.c File Reference

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

Include dependency graph for bary_functions.c:

Go to the source code of this file.

Defines
#define	STATIC
Functions
STATIC int	compare_bary (const GNODE *a, const GNODE *b)
STATIC void	resort_up_down_layer (int level)
STATIC void	resort_down_up_layer (int level)
void	apply_horder (int i)
STATIC void	mark_all_nodes (GNODE node, int i)
STATIC void	phase1_down (void)
STATIC void	phase1_up (void)
STATIC int	cycle_sort_array (int siz)
STATIC void	tree_horizontal_order (void)
STATIC void	unmerge_connected_parts (void)
void	copy_layers (DEPTH *l1, DEPTH *l2)
STATIC void	save_level (int i)
STATIC void	restore_level (int i)
STATIC void	init_barycentering (void)
void	barycentering (void)
Variables
int	mark_all_nodes_merger
STATIC int	have_alternative
STATIC int	phase1_allowed

---

Define Documentation

#define STATIC

Definition at line 3 of file bary_functions.c. Referenced by array_to_level(), calc_all_layers_crossings(), checkcrossing(), compare_pos(), cycle_sort_array(), finish_lower(), finish_upper(), graph_crossings(), gs_ide1518(), init_barycentering(), layer_crossing(), level_to_array(), mark_all_nodes(), phase1_down(), phase1_up(), phase2_down(), phase2_up(), resort_down_layer(), resort_down_up_layer(), resort_up_down_layer(), resort_up_layer(), restore_level(), save_level(), tree_horizontal_order(), and unmerge_connected_parts().

---

Function Documentation

void apply_horder (  int  i  )

Definition at line 49 of file bary_functions.c. References compare_bary(), GNLIST, GNODE, sort_array, and tmp_layer. Referenced by phase2_down(), phase2_up(), resort_down_layer(), and resort_up_layer(). { 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); } }

void barycentering (  void   )

Definition at line 383 of file bary_functions.c. Referenced by main(). { 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; } }

STATIC int compare_bary (  const GNODE *  a, const GNODE *  b )

Definition at line 7 of file bary_functions.c. References GNODE. { 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); }

void copy_layers (  DEPTH *  l1, DEPTH *  l2 )  [static]

Definition at line 326 of file bary_functions.c. References DEPTH, GNLIST, maxdepth, and tmpnodelist_alloc(). Referenced by barycentering(), tree_horizontal_order(), and unmerge_connected_parts(). { 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 int cycle_sort_array (  int  siz  )

Definition at line 126 of file bary_functions.c. References GNODE, sort_array, and STATIC. Referenced by phase2_down(), and phase2_up(). { 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); }

STATIC void init_barycentering (  void   )

Definition at line 378 of file bary_functions.c. References have_alternative, phase1_allowed, and STATIC. Referenced by main(). { have_alternative = 0; phase1_allowed = 1; }

STATIC void mark_all_nodes (  GNODE  node, int  i )

Definition at line 80 of file bary_functions.c. References ADJEDGE, GNODE, max_horder_num, and STATIC. Referenced by unmerge_connected_parts(). { 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   )

Definition at line 102 of file bary_functions.c. References gs_wait_message(), maxdepth, resort_down_layer(), and STATIC. Referenced by barycentering(). { int i; gs_wait_message ('b'); for (i = 0; i <= maxdepth; i++) (void) resort_down_layer (i); }

STATIC void phase1_up (  void   )

Definition at line 109 of file bary_functions.c. References gs_wait_message(), maxdepth, resort_up_layer(), and STATIC. Referenced by barycentering(). { int i; gs_wait_message ('b'); for (i = maxdepth; i >= 0; i--) (void) resort_up_layer (i); }

STATIC void resort_down_up_layer (  int  level  )

Definition at line 28 of file bary_functions.c. References maxdepth, resort_down_layer(), resort_up_layer(), and STATIC. Referenced by phase2_up(). { 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; } } }

STATIC void resort_up_down_layer (  int  level  )

Definition at line 19 of file bary_functions.c. References maxdepth, resort_down_layer(), resort_up_layer(), and STATIC. Referenced by phase2_down(). { 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 restore_level (  int  i  )

Definition at line 367 of file bary_functions.c. References GNLIST, save_array, STATIC, and tmp_layer. Referenced by resort_down_layer(), and resort_up_layer(). { int j; GNLIST hn; ; j = 0; hn = ((tmp_layer[i]).succlist); while (hn) { ((hn)->node) = save_array[j++]; hn = ((hn)->next); } }

STATIC void save_level (  int  i  )

Definition at line 358 of file bary_functions.c. References GNLIST, save_array, STATIC, and tmp_layer. Referenced by resort_down_layer(), and resort_up_layer(). { int j; GNLIST hn; ; j = 0; hn = ((tmp_layer[i]).succlist); while (hn) { save_array[j++] = ((hn)->node); hn = ((hn)->next); } }

STATIC void tree_horizontal_order (  void   )

Definition at line 182 of file bary_functions.c. References ADJEDGE, array_to_level(), compare_bary(), copy_layers(), GEDGE, GNLIST, GNODE, adjedge::kante, layer, level_to_array(), max_eprio, maxdepth, gnlist::next, adjedge::next, gnlist::node, predbary(), sort_array, STATIC, gnode::succ, tmp_layer, and gedge::weights. { 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   )

Definition at line 279 of file bary_functions.c. References array_to_level(), compare_bary(), copy_layers(), GNLIST, GNODE, gs_wait_message(), layer, mark_all_nodes(), maxdepth, sort_array, STATIC, and tmp_layer. { 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); }

---

Variable Documentation

STATIC int have_alternative

Definition at line 376 of file bary_functions.c. Referenced by barycentering(), and init_barycentering().

int mark_all_nodes_merger

Definition at line 323 of file bary_functions.c.

STATIC int phase1_allowed

Definition at line 377 of file bary_functions.c. Referenced by barycentering(), and init_barycentering().

---