Crossings Minimization
1.0

implements various functions related to median heuristics More...
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "defs.h"
#include "min_crossings.h"
#include "median.h"
#include "graph.h"
#include "sorting.h"
#include "crossings.h"
#include "graph_io.h"
#include "heuristics.h"
Go to the source code of this file.
Functions  
static double  upper_median (Nodeptr node) 
static double  lower_median (Nodeptr node) 
static void  node_weight (Nodeptr node, Orientation orientation) 
static void  two_layer_node_weight (Nodeptr node) 
static void  adjust_weights_left (int layer) 
static void  adjust_weights_avg (int layer) 
void  medianWeights (int layer, Orientation orientation) 
bool  medianUpSweep (int starting_layer) 
bool  medianDownSweep (int starting_layer) 
implements various functions related to median heuristics
Definition in file median.c.

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 115 of file median.c.
References layers, node_struct::name, layer_struct::nodes, layer_struct::number_of_nodes, number_of_nodes, and node_struct::weight.
Referenced by medianWeights().

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.
Definition at line 90 of file median.c.
References layers, node_struct::name, layer_struct::nodes, layer_struct::number_of_nodes, and node_struct::weight.
Referenced by medianWeights().

static 
Definition at line 40 of file median.c.
References node_struct::down_degree, node_struct::down_edges, edge_struct::down_node, node_struct::position, and sortByDownNodePosition().
Referenced by node_weight(), and two_layer_node_weight().
bool medianDownSweep  (  int  starting_layer  ) 
Repeats median heuristic moving downward from the starting layer to the bottom layer, layer 0. Orientation of each heuristic application is upward.
Definition at line 206 of file median.c.
References end_of_iteration(), layerSort(), medianWeights(), tracePrint(), updateCrossingsForLayer(), and UPWARD.
Referenced by median().
bool medianUpSweep  (  int  starting_layer  ) 
Repeats median heuristic moving upward from the starting layer to the uppermost layer. Orientation of each heuristic application is downward.
Definition at line 187 of file median.c.
References DOWNWARD, end_of_iteration(), layerSort(), medianWeights(), number_of_layers, tracePrint(), and updateCrossingsForLayer().
Referenced by median().
void medianWeights  (  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 155 of file median.c.
References adjust_weights, adjust_weights_avg(), adjust_weights_left(), AVG, BOTH, layers, LEFT, node_weight(), layer_struct::nodes, layer_struct::number_of_nodes, and two_layer_node_weight().
Referenced by medianDownSweep(), and medianUpSweep().

static 
Computes the weight of a node based on the median position of its neighbors according to the given orientation.
Definition at line 54 of file median.c.
References BOTH, DOWNWARD, lower_median(), node_struct::name, upper_median(), UPWARD, and node_struct::weight.
Referenced by medianWeights().

static 
computes weight based on two neighboring layers as 1/2 * (upper_median + lower_median)
Definition at line 77 of file median.c.
References lower_median(), upper_median(), and node_struct::weight.
Referenced by medianWeights().

static 
Definition at line 26 of file median.c.
References node_struct::position, sortByUpNodePosition(), node_struct::up_degree, node_struct::up_edges, and edge_struct::up_node.
Referenced by node_weight(), and two_layer_node_weight().