Crossings Minimization  1.0
barycenter.c File Reference

implements various functions related to barycenter heuristics More...

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "defs.h"
#include "min_crossings.h"
#include "barycenter.h"
#include "graph.h"
#include "sorting.h"
#include "crossings.h"
#include "graph_io.h"
#include "heuristics.h"
Include dependency graph for barycenter.c:

Go to the source code of this file.

Functions

static void node_weight (Nodeptr node, Orientation orientation)
 
static void balanced_node_weight (Nodeptr node)
 
static void adjust_weights_left (int layer)
 
static void adjust_weights_avg (int layer)
 
void barycenterWeights (int layer, Orientation orientation)
 
bool barycenterUpSweep (int starting_layer)
 
bool barycenterDownSweep (int starting_layer)
 

Detailed Description

implements various functions related to barycenter heuristics

Author
Matthias Stallmann
Date
2008/12/29
Id
barycenter.c 96 2014-09-09 16:37:16Z mfms

Definition in file barycenter.c.

Function Documentation

◆ adjust_weights_avg()

static void adjust_weights_avg ( int  layer)
static

Some nodes may have weight -1 because they have no edges in the desired direction. This function gives them a weight that is the average of that of the two neighbors on the layer - or just the weight of one of the neighbors if the other is absent or also has weight -1.

Definition at line 146 of file barycenter.c.

References layers, node_struct::name, layer_struct::nodes, layer_struct::number_of_nodes, number_of_processors, and node_struct::weight.

Referenced by barycenterWeights().

◆ adjust_weights_left()

static void adjust_weights_left ( int  layer)
static

Some nodes may have weight -1 because they have no edges in the desired direction. This function gives them a weight identical to that of their left neighbor on the layer, or 0 if all nodes to the left have weight -1. Note: If the node to the left has weight -1 originally, its weight will have been changed by the time the node is processed.

Todo:
adjust_weights_left() and adjust_weights_avg() have identical counterparts in median.c

Definition at line 121 of file barycenter.c.

References layers, node_struct::name, layer_struct::nodes, layer_struct::number_of_nodes, and node_struct::weight.

Referenced by barycenterWeights().

◆ balanced_node_weight()

static void balanced_node_weight ( Nodeptr  node)
static

computes weight based on two neighboring layers, but does it as 1/2 * (upper_average + lower_average) instead of sum_of_positions / total_degree

Definition at line 72 of file barycenter.c.

References node_struct::down_degree, node_struct::down_edges, edge_struct::down_node, node_struct::id, node_struct::position, node_struct::up_degree, node_struct::up_edges, edge_struct::up_node, and node_struct::weight.

Referenced by barycenterWeights().

◆ barycenterDownSweep()

bool barycenterDownSweep ( int  starting_layer)

Repeats barycenter heuristic moving downward from the starting layer to the bottom layer, layer 0. Orientation of each heuristic application is upward.

Definition at line 260 of file barycenter.c.

References barycenterWeights(), end_of_iteration(), layerSort(), tracePrint(), updateCrossingsForLayer(), and UPWARD.

Referenced by barycenter(), modifiedBarycenter(), and printCrossings().

Here is the call graph for this function:

◆ barycenterUpSweep()

bool barycenterUpSweep ( int  starting_layer)

Repeats barycenter heuristic moving upward from the starting layer to the uppermost layer. Orientation of each heuristic application is downward.

Returns
true if max iterations was reached in the process

Definition at line 239 of file barycenter.c.

References barycenterWeights(), DOWNWARD, end_of_iteration(), layerSort(), number_of_layers, tracePrint(), and updateCrossingsForLayer().

Referenced by barycenter(), modifiedBarycenter(), and printCrossings().

Here is the call graph for this function:

◆ barycenterWeights()

void barycenterWeights ( int  layer,
Orientation  orientation 
)

Assigns weights to nodes on the given layer based on positions of their edges above, below, or both, as specified by the orientation.

Definition at line 206 of file barycenter.c.

References adjust_weights, adjust_weights_avg(), adjust_weights_left(), AVG, balanced_node_weight(), balanced_weight, BOTH, layers, LEFT, node_weight(), layer_struct::nodes, and layer_struct::number_of_nodes.

Referenced by barycenterDownSweep(), barycenterUpSweep(), evenOddBarycenter(), modifiedBarycenter(), rotatingBarycenter(), slab_bary_iteration(), staticBarycenter(), and upDownBarycenter().

Here is the call graph for this function:

◆ node_weight()

static void node_weight ( Nodeptr  node,
Orientation  orientation 
)
static

Computes the weight of a node based on the average position of its neighbors according to the given orientation. If the node has no neighbors in the direction specified by the orientation, its neighbors in the other direction are taken into account. Isolated nodes have 0 weight.

Definition at line 29 of file barycenter.c.

References adjust_weights, node_struct::down_degree, node_struct::down_edges, edge_struct::down_node, DOWNWARD, node_struct::id, NONE, node_struct::position, node_struct::up_degree, node_struct::up_edges, edge_struct::up_node, UPWARD, and node_struct::weight.

Referenced by barycenterWeights().