Crossings Minimization  1.0
crossings.c File Reference

Implementation of functions that are used to count and update crossings locally. More...

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

Go to the source code of this file.

Data Structures

struct  inter_layer_struct
 

Typedefs

typedef struct inter_layer_structInterLayerptr
 

Functions

static int count_down_edges (int layer_number)
 
static InterLayerptr makeInterLayer (int upper_layer)
 
void initCrossings (void)
 
int numberOfCrossings (void)
 
int maxEdgeCrossings (void)
 
int numberOfCrossingsLayer (int layer)
 
int numberOfCrossingsNode (Nodeptr node)
 
int numberOfCrossingsEdge (Edgeptr edge)
 
void updateAllCrossings (void)
 
void updateCrossingsForLayer (int layer)
 
void updatePositionsForLayer (int layer)
 
static void initialize_crossings (int upper_layer)
 
void updateCrossingsBetweenLayers (int upper_layer)
 
int maxCrossingsLayer (void)
 
Nodeptr maxCrossingsNode (void)
 
Edgeptr maxCrossingsEdge (void)
 
Edgeptr maxCrossingsEdgeStatic (void)
 
static void print_down_crossings_nodes (int i)
 
static void print_down_crossings_edges (int i)
 
void print_up_crossings_nodes (int i)
 
void print_crossings_between_layers (int i)
 
void printCrossings (void)
 

Variables

static InterLayerptrbetween_layers
 

Detailed Description

Implementation of functions that are used to count and update crossings locally.

Implementation of functions that keep track of and update the number of crossings for each node, each layer, and for the whole graph.

Author
Matt Stallmann
Date
2009/05/15
Id
crossing_utilities.c 56 2014-03-13 21:12:01Z mfms

The algorithm used to count crossings between adjacent layers is the O(|E|+|C|) algorithm from "Simple and efficient bilayer cross counting", W. Barth, M. Juenger, P. Mutzel, in JGAA, 2004.

Author
Matt Stallmann
Date
2008/12/23
Id
crossings.c 101 2014-10-22 16:32:05Z mfms

Definition in file crossings.c.

Typedef Documentation

◆ InterLayerptr

Information about edges between layers i - 1 and i; the entry for 0 is not used.

Function Documentation

◆ count_down_edges()

static int count_down_edges ( int  layer_number)
static

◆ initCrossings()

void initCrossings ( void  )

Initializes all crossing counts and allocates data structures used for counting crossings. Assumes that the graph has been read from the two input files and all basic data properly initialized -

See also
readgraph()

Definition at line 80 of file crossings.c.

References makeInterLayer(), and number_of_layers.

Referenced by main(), and printCrossings().

Here is the call graph for this function:

◆ initialize_crossings()

static void initialize_crossings ( int  upper_layer)
static

Sets all node crossings relevant to the edges between layers upper_layer and upper_layer - 1 to 0

Definition at line 169 of file crossings.c.

References edge_struct::crossings, node_struct::down_crossings, node_struct::down_degree, node_struct::down_edges, layers, layer_struct::nodes, layer_struct::number_of_nodes, and node_struct::up_crossings.

Referenced by updateCrossingsBetweenLayers().

◆ makeInterLayer()

static InterLayerptr makeInterLayer ( int  upper_layer)
static

Definition at line 64 of file crossings.c.

References count_down_edges(), inter_layer_struct::edges, and inter_layer_struct::number_of_edges.

Referenced by initCrossings().

Here is the call graph for this function:

◆ maxCrossingsEdge()

Edgeptr maxCrossingsEdge ( void  )
Returns
A pointer to an unfixed edge with the most crossings, or NULL if all edges are fixed.

Definition at line 262 of file crossings.c.

References edge_struct::crossings, genrand_permute(), isFixedEdge(), master_edge_list, inter_layer_struct::number_of_edges, and randomize_order.

Referenced by maximumCrossingsEdge(), maximumCrossingsEdgeWithSifting(), and printCrossings().

Here is the call graph for this function:

◆ maxCrossingsEdgeStatic()

Edgeptr maxCrossingsEdgeStatic ( void  )
Returns
an edge with the maximum number of crossings; does not change any state information; this is used only when computing bottleneck crossings
Todo:
eventually this will go away when a lot of the content here is moved to channel.[ch] and the maximum bottleneck and total crossings can be maintained on a per channel basis

Definition at line 287 of file crossings.c.

References edge_struct::crossings, master_edge_list, and inter_layer_struct::number_of_edges.

Referenced by maxEdgeCrossings().

◆ maxCrossingsLayer()

int maxCrossingsLayer ( void  )
Returns
The number of an unfixed layer whose incident edges have the largest number of total crossings, or -1 if all layers are fixed.

Definition at line 220 of file crossings.c.

References genrand_permute(), isFixedLayer(), number_of_layers, numberOfCrossingsLayer(), and randomize_order.

Referenced by modifiedBarycenter(), and printCrossings().

Here is the call graph for this function:

◆ maxCrossingsNode()

Nodeptr maxCrossingsNode ( void  )
Returns
A pointer to an unfixed node whose incident edges have the most crossings, or NULL if all nodes are fixed. The layer and position of the node are stored with it. When there are ties, bias is in favor of a node not on the same layer as the most recent node chosen; this is to avoid a lot of repeated sifting on the same layer.

Definition at line 242 of file crossings.c.

References genrand_permute(), isFixedNode(), master_node_list, node_struct::name, number_of_nodes, numberOfCrossingsNode(), and randomize_order.

Referenced by maximumCrossingsNode(), and printCrossings().

Here is the call graph for this function:

◆ maxEdgeCrossings()

int maxEdgeCrossings ( void  )
Returns
the maximum number of crossings for any edge

Definition at line 104 of file crossings.c.

References edge_struct::crossings, and maxCrossingsEdgeStatic().

Referenced by capture_beginning_stats(), capture_preprocessing_stats(), end_of_iteration(), trace_printer(), and update_best_all().

Here is the call graph for this function:

◆ numberOfCrossings()

int numberOfCrossings ( void  )

◆ numberOfCrossingsEdge()

int numberOfCrossingsEdge ( Edgeptr  edge)
Returns
the number of crossings for the given edge

Definition at line 133 of file crossings.c.

References edge_struct::crossings.

Referenced by printCrossings().

◆ numberOfCrossingsLayer()

int numberOfCrossingsLayer ( int  layer)
Returns
the number of crossings for the given layer

Definition at line 112 of file crossings.c.

References inter_layer_struct::number_of_crossings, and number_of_layers.

Referenced by maxCrossingsLayer(), and printCrossings().

◆ numberOfCrossingsNode()

int numberOfCrossingsNode ( Nodeptr  node)
Returns
the number of crossings for the given node

Definition at line 125 of file crossings.c.

References node_struct::down_crossings, and node_struct::up_crossings.

Referenced by edge_sift_iteration(), maxCrossingsNode(), and printCrossings().

◆ print_crossings_between_layers()

void print_crossings_between_layers ( int  i)

Prints information for crossings between layers i-1 and i

Definition at line 353 of file crossings.c.

References inter_layer_struct::number_of_crossings, print_down_crossings_nodes(), and print_up_crossings_nodes().

Referenced by printCrossings().

Here is the call graph for this function:

◆ print_down_crossings_edges()

static void print_down_crossings_edges ( int  i)
static

◆ print_down_crossings_nodes()

static void print_down_crossings_nodes ( int  i)
static

Prints down crossings for the nodes on layer i

Definition at line 303 of file crossings.c.

References node_struct::down_crossings, node_struct::layer, layers, node_struct::name, layer_struct::nodes, layer_struct::number_of_nodes, and node_struct::position.

Referenced by print_crossings_between_layers().

◆ print_up_crossings_nodes()

void print_up_crossings_nodes ( int  i)

Prints up crossings for the nodes on layer i

Definition at line 338 of file crossings.c.

References node_struct::layer, layers, node_struct::name, layer_struct::nodes, layer_struct::number_of_nodes, node_struct::position, and node_struct::up_crossings.

Referenced by print_crossings_between_layers().

◆ printCrossings()

◆ updateAllCrossings()

void updateAllCrossings ( void  )

Updates all crossings based on current ordering of nodes on each layer. The position pointers for all nodes are made consistent as well, using updateAllPositions() in the sorting module

Definition at line 138 of file crossings.c.

References number_of_layers, updateAllPositions(), and updateCrossingsBetweenLayers().

Referenced by main(), printCrossings(), restore_order(), total_stretch_sift_iteration(), and trace_printer().

Here is the call graph for this function:

◆ updateCrossingsBetweenLayers()

void updateCrossingsBetweenLayers ( int  upper_layer)

Updates crossings between two adjacent layers. Also updates the relevant crossing fields of the two layers.

Parameters
upper_layerthe higher of the two layers; crossings between layers upper_layer - 1 and upper_layer are counted

Definition at line 199 of file crossings.c.

References add_edges_to_array(), count_inversions_down(), node_struct::down_degree, node_struct::down_edges, inter_layer_struct::edges, initialize_crossings(), layers, layer_struct::nodes, inter_layer_struct::number_of_crossings, inter_layer_struct::number_of_edges, layer_struct::number_of_nodes, and sortByDownNodePosition().

Referenced by updateAllCrossings(), and updateCrossingsForLayer().

Here is the call graph for this function:

◆ updateCrossingsForLayer()

void updateCrossingsForLayer ( int  layer)

Updates crossings after the given layer has been permuted. The position pointers for all nodes on the layer are made consistent as well, using updateNodePositions() in the sorting module

Definition at line 147 of file crossings.c.

References number_of_layers, updateCrossingsBetweenLayers(), and updateNodePositions().

Referenced by barycenterDownSweep(), barycenterUpSweep(), evenOddBarycenter(), medianDownSweep(), medianUpSweep(), modifiedBarycenter(), rotatingBarycenter(), sift(), sift_node_for_edge_crossings(), slab_bary_iteration(), staticBarycenter(), and upDownBarycenter().

Here is the call graph for this function:

◆ updatePositionsForLayer()

void updatePositionsForLayer ( int  layer)

Variable Documentation

◆ between_layers

InterLayerptr* between_layers
static

between_layers[i] is information about edges between layers i - 1 and i; the entry for i = 0 is not used

Definition at line 48 of file crossings.c.