Crossings Minimization  1.0
crossings.h File Reference

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

#include <stdbool.h>
#include "defs.h"
#include "graph.h"
Include dependency graph for crossings.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

void initCrossings (void)
 
int numberOfCrossings (void)
 
int maxEdgeCrossings (void)
 
int numberOfCrossingsLayer (int layer)
 
int numberOfCrossingsNode (Nodeptr node)
 
void updateAllCrossings (void)
 
void updateCrossingsForLayer (int layer)
 
void updateCrossingsBetweenLayers (int upper_layer)
 
int maxCrossingsLayer (void)
 
Nodeptr maxCrossingsNode (void)
 
Edgeptr maxCrossingsEdge (void)
 
Edgeptr maxCrossingsEdgeStatic (void)
 
void printCrossings (void)
 

Detailed Description

Definition 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
2008/12/23
Id
crossings.h 2 2011-06-07 19:50:41Z mfms

Definition in file crossings.h.

Function Documentation

◆ initCrossings()

void initCrossings ( void  )

Initializes all crossing counts and allocates data structures used for counting crossings.

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:

◆ 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
A pointer to an edge with the most crossings; ignores the current status of the edge (fixed or not) and has no impact on the state of any heuristic.
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  )

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

◆ 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 and position fields of nodes for the two layers.

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

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: