Crossings Minimization  1.0
median.c File Reference

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"
Include dependency graph for median.c:

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)
 

Detailed Description

implements various functions related to median heuristics

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

Definition in file median.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 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().

◆ 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.

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().

◆ lower_median()

static double lower_median ( Nodeptr  node)
static
Returns
the median position of the nodes adjacent to 'node' on the layer below 'node'

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().

Here is the call graph for this function:

◆ medianDownSweep()

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().

Here is the call graph for this function:

◆ medianUpSweep()

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.

Returns
true if max iterations was reached in the process

Definition at line 187 of file median.c.

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

Referenced by median().

Here is the call graph for this function:

◆ medianWeights()

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().

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 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().

Here is the call graph for this function:

◆ two_layer_node_weight()

static void two_layer_node_weight ( Nodeptr  node)
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().

Here is the call graph for this function:

◆ upper_median()

static double upper_median ( Nodeptr  node)
static
Returns
the median position of the nodes adjacent to 'node' on the layer above 'node'

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().

Here is the call graph for this function: