Crossings Minimization
1.0
|
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"
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) |
implements various functions related to barycenter heuristics
Definition in file barycenter.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 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().
|
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 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().
|
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().
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().
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.
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().
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().
|
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().