Crossings Minimization  1.0
heuristics.h File Reference

Interface for functions implementing all of the heuristics Those labeled parallel are designed specifically for parallel implementation and their iterations are defined by "synchronization points". More...

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

Go to the source code of this file.

Functions

void createOrdFileName (char *output_file_name, const char *appendix)
 
void createDotFileName (char *output_file_name, const char *appendix)
 
void tracePrint (int layer, const char *message)
 
bool end_of_iteration (void)
 
bool isFixedNode (Nodeptr node)
 
bool isFixedEdge (Edgeptr edge)
 
bool isFixedLayer (int layer)
 
void fixNode (Nodeptr node)
 
void fixEdge (Edgeptr edge)
 
void fixLayer (int layer)
 
void clearFixedNodes (void)
 
void clearFixedEdges (void)
 
void clearFixedLayers (void)
 
int totalDegree (int layer)
 
int maxDegreeLayer ()
 
void median (void)
 
void barycenter (void)
 
void modifiedBarycenter (void)
 
void staticBarycenter (void)
 
void evenOddBarycenter (void)
 
void rotatingBarycenter (void)
 
void upDownBarycenter (void)
 
void slabBarycenter (void)
 
void maximumCrossingsNode (void)
 
void maximumCrossingsEdge (void)
 
void maximumCrossingsEdgeWithSifting (void)
 
void maximumStretchEdge (void)
 
void sifting (void)
 
void breadthFirstSearch (void)
 
void depthFirstSearch (void)
 
void middleDegreeSort (void)
 
void swapping (void)
 

Variables

int iteration
 
int post_processing_crossings
 
int post_processing_iteration
 

Detailed Description

Interface for functions implementing all of the heuristics Those labeled parallel are designed specifically for parallel implementation and their iterations are defined by "synchronization points".

Author
Matthias Stallmann
Date
2008/12/29
Id
heuristics.h 110 2015-06-12 12:26:27Z mfms

Definition in file heuristics.h.

Function Documentation

◆ barycenter()

void barycenter ( void  )

implements the barycenter heuristic

Definition at line 428 of file heuristics.c.

References barycenterDownSweep(), barycenterUpSweep(), number_of_layers, terminate(), and tracePrint().

Referenced by runHeuristic().

Here is the call graph for this function:

◆ breadthFirstSearch()

void breadthFirstSearch ( void  )

Definition at line 1065 of file heuristics.c.

Referenced by runPreprocessor().

◆ clearFixedEdges()

◆ clearFixedLayers()

void clearFixedLayers ( void  )

Definition at line 348 of file heuristics.c.

References layer_struct::fixed, layers, and number_of_layers.

Referenced by modifiedBarycenter(), and printCrossings().

◆ clearFixedNodes()

◆ createDotFileName()

void createDotFileName ( char *  output_file_name,
const char *  appendix 
)

Creates a dot file name using the graph name and the appendix

Parameters
output_file_namea buffer for the file name to be created, assumed to be big enough
appendixa string that is attached just before the .dot extension

Definition at line 83 of file heuristics.c.

References graph_name.

Referenced by createFavoredEdgeInfo().

◆ createOrdFileName()

void createOrdFileName ( char *  output_file_name,
const char *  appendix 
)

Creates an ord file name from the graph name, preprocessor and heuristic.

Parameters
output_file_namea buffer for the file name to be created, assumed to be big enough
appendixa string that is attached just before the .ord extension

Definition at line 64 of file heuristics.c.

References heuristic, output_base_name, and preprocessor.

Referenced by end_of_iteration(), and main().

◆ depthFirstSearch()

void depthFirstSearch ( void  )

Definition at line 1070 of file heuristics.c.

References assignDfsWeights(), layerSort(), and number_of_layers.

Referenced by runPreprocessor().

Here is the call graph for this function:

◆ end_of_iteration()

bool end_of_iteration ( void  )

Does things that are appropriate at the end of an iteration, such as checking whether the ordering needs to be captured and the min crossings/edge crossings need to be updated. Also increments the iteration counter

Returns
true if max_iterations has been reached

Definition at line 183 of file heuristics.c.

References crossing_stats_int::best, crossing_stats_int::best_heuristic_iteration, capture_iteration, createOrdFileName(), iteration, max_edge_crossings, max_iterations, MAX_NAME_LENGTH, max_runtime, maxEdgeCrossings(), numberOfCrossings(), output_file_name, print_last_iteration_message(), RUNTIME, total_crossings, update_best_all(), and writeOrd().

Referenced by barycenterDownSweep(), barycenterUpSweep(), edge_sift_iteration(), evenOddBarycenter(), main(), medianDownSweep(), medianUpSweep(), modifiedBarycenter(), rotatingBarycenter(), sift_decreasing(), sift_increasing(), sift_iteration(), sifting(), slab_bary_iteration(), staticBarycenter(), total_stretch_sift_iteration(), and upDownBarycenter().

Here is the call graph for this function:

◆ evenOddBarycenter()

void evenOddBarycenter ( void  )

Alternates barycenter iterations between even and odd layers, computing weights for both adjoining layers each time. (parallel)

Should really be called oddEvenBarycenter, and is referred to as alt_bary in the user interface. Alternates between sorting odd and even numbered layers based on both neighboring layers. Weight assignment is affected by the 'balanced_weight' parameter, set with the -b command-line option.

Definition at line 523 of file heuristics.c.

References barycenterWeights(), BOTH, end_of_iteration(), layerSort(), number_of_layers, number_of_processors, terminate(), tracePrint(), and updateCrossingsForLayer().

Referenced by runHeuristic().

Here is the call graph for this function:

◆ fixEdge()

void fixEdge ( Edgeptr  edge)

◆ fixLayer()

void fixLayer ( int  layer)

Definition at line 299 of file heuristics.c.

References layer_struct::fixed, and layers.

Referenced by modifiedBarycenter(), and printCrossings().

◆ fixNode()

◆ isFixedEdge()

bool isFixedEdge ( Edgeptr  edge)

Definition at line 295 of file heuristics.c.

References edge_struct::fixed.

Referenced by maxCrossingsEdge(), and maxStretchEdge().

◆ isFixedLayer()

bool isFixedLayer ( int  layer)

Definition at line 296 of file heuristics.c.

References layer_struct::fixed, and layers.

Referenced by maxCrossingsLayer().

◆ isFixedNode()

◆ maxDegreeLayer()

int maxDegreeLayer ( )
Returns
the layer with maximum total degree

Definition at line 369 of file heuristics.c.

References number_of_layers, and totalDegree().

Here is the call graph for this function:

◆ maximumCrossingsEdge()

void maximumCrossingsEdge ( void  )

mce as described in M. Stallmann, JEA 2012.

Todo:
what follows is now incorporated into maximumCrossingsEdgeWithSifting(); eventually the two could be merged

Definition at line 875 of file heuristics.c.

References buffer, clearFixedEdges(), clearFixedNodes(), edge_struct::down_node, edge_sift_iteration(), end_mce_pass(), fixEdge(), node_struct::layer, maxCrossingsEdge(), node_struct::name, terminate(), tracePrint(), and edge_struct::up_node.

Referenced by runHeuristic().

Here is the call graph for this function:

◆ maximumCrossingsEdgeWithSifting()

void maximumCrossingsEdgeWithSifting ( void  )

A variation of the mce heuristic in which the two endpoints of the edge with maximum crossings are sifted so as to minimize the total number of crossings rather than the more complicated objective of mce that is described in M. Stallmann, JEA 2012.

Definition at line 828 of file heuristics.c.

References allNodesFixed(), buffer, clearFixedEdges(), clearFixedNodes(), edge_struct::down_node, fixEdge(), fixNode(), isFixedNode(), node_struct::layer, maxCrossingsEdge(), node_struct::name, sift_iteration(), terminate(), tracePrint(), and edge_struct::up_node.

Referenced by runHeuristic().

Here is the call graph for this function:

◆ maximumCrossingsNode()

void maximumCrossingsNode ( void  )

Definition at line 805 of file heuristics.c.

References clearFixedNodes(), maxCrossingsNode(), sift_iteration(), terminate(), and tracePrint().

Referenced by runHeuristic().

Here is the call graph for this function:

◆ maximumStretchEdge()

void maximumStretchEdge ( void  )

similar to mce, except that, in each iteration, the edge with maximum stretch is chosen and the endpoints are moved to positions that minimize the total stretch of their incident edges

Todo:
one could also base the movement on minimizing the maximum stretch of any edge, similar to mce

Definition at line 912 of file heuristics.c.

References allNodesFixed(), buffer, clearFixedEdges(), clearFixedNodes(), edge_struct::down_node, fixEdge(), fixNode(), isFixedNode(), node_struct::layer, maxStretchEdge(), node_struct::name, terminate(), total_stretch_sift_iteration(), tracePrint(), and edge_struct::up_node.

Referenced by runHeuristic().

Here is the call graph for this function:

◆ median()

void median ( void  )

implements the median heuristic

Definition at line 413 of file heuristics.c.

References medianDownSweep(), medianUpSweep(), number_of_layers, terminate(), and tracePrint().

Referenced by runHeuristic().

Here is the call graph for this function:

◆ middleDegreeSort()

void middleDegreeSort ( void  )

Definition at line 1098 of file heuristics.c.

References layerQuicksort(), layers, number_of_layers, number_of_nodes, sortByDegree(), and weight_first_to_middle().

Referenced by runPreprocessor().

Here is the call graph for this function:

◆ modifiedBarycenter()

void modifiedBarycenter ( void  )

◆ rotatingBarycenter()

void rotatingBarycenter ( void  )

Alternates between odd and even numbered layers, but instead of alternating at every iteration and using both neighboring layers to assign weights, this version uses the downward layer (starting with odd layers) for a number of iterations corresponding to the number of layers, and then the upward layer for an equal number of iterations. (parallel) Alternates between even numbered and odd numbered layers. Unlike alt_bary, which bases sorting on both neighboring layers simultaneously, this version rotates between doing upward, downward, and both. (parallel)

Alternates between even numbered and odd numbered layers. Unlike alt_bary, which bases sorting on both neighboring layers simultaneously, this version rotates between doing upward, downward, and both.

Definition at line 686 of file heuristics.c.

References barycenterWeights(), BOTH, buffer, DOWNWARD, end_of_iteration(), layerSort(), LINE_LENGTH, number_of_layers, number_of_processors, terminate(), tracePrint(), updateCrossingsForLayer(), and UPWARD.

Referenced by runHeuristic().

Here is the call graph for this function:

◆ sifting()

◆ slabBarycenter()

void slabBarycenter ( void  )

Each processor does a full-blown barycenter algorithm. Starts are staggered at distance max(layers/processors,2) and each sweep wraps around to make the best use of of each processor. Startting layer shifts by 1 at each iteration.

Todo:
rename this as shiftBarycenter, which would be more in keeping with its behavior.

Each processor does a full-blown barycenter algorithm. Starts are staggered at distance max(layers/processors,2) and each sweep wraps around to make the best use of of each processor. Startting layer shifts by 1 at each iteration.

Definition at line 649 of file heuristics.c.

References buffer, DOWNWARD, LINE_LENGTH, number_of_layers, number_of_processors, slab_bary_iteration(), terminate(), tracePrint(), and UPWARD.

Referenced by runHeuristic().

Here is the call graph for this function:

◆ staticBarycenter()

void staticBarycenter ( void  )

Computes weights on each layer independently and alternates sweep directions (parallel)

Todo:
For the following variations of barycenter, staticBarycenter() and evenOddBarycenter(), which are intended to be parallelized, it would be useful to have a global variable 'number_of_processors' to govern when the end of an iteration takes place. The current code assumes that the number of processors is unlimited, but synchronization and capture of current minimum takes place only at synchronization points, i.e., calls to end_of_iteration().

The mechanism would count local_iterations and do something like:
if ( local_iterations % number_of_processors == 0 ) end_of_iteration();
local_iterations would be updated in the body of each for loop that is intended to be parallelized (and effects a change) and the above code woul occur at the end of such a loop

Definition at line 492 of file heuristics.c.

References barycenterWeights(), BOTH, end_of_iteration(), layerSort(), number_of_layers, number_of_processors, terminate(), tracePrint(), and updateCrossingsForLayer().

Referenced by runHeuristic().

Here is the call graph for this function:

◆ swapping()

void swapping ( void  )

Swaps neighboring nodes when this improves the total number of crossings until no improvement is possible. (embarrasingly parallel)

!!! attempted to update this so that it would fix the Pareto frontier, but a swapping iteration does not actually recompute total crossings !!!

Definition at line 1195 of file heuristics.c.

References best_crossings_order, numberOfCrossings(), post_processing_crossings, post_processing_iteration, save_order(), swapping_iteration(), tracePrint(), and update_best_all().

Referenced by main().

Here is the call graph for this function:

◆ totalDegree()

int totalDegree ( int  layer)
Returns
the total degree of nodes on the given layer

Definition at line 357 of file heuristics.c.

References node_struct::down_degree, layers, layer_struct::nodes, layer_struct::number_of_nodes, and node_struct::up_degree.

Referenced by maxDegreeLayer().

◆ tracePrint()

void tracePrint ( int  layer,
const char *  message 
)

◆ upDownBarycenter()

void upDownBarycenter ( void  )

Alternates between odd and even numbered layers, but instead of alternating at every iteration and using both neighboring layers to assign weights, this version uses the downward layer (starting with odd layers) for a number of iterations corresponding to the number of layers, and then the upward layer for an equal number of iterations.

Definition at line 570 of file heuristics.c.

References barycenterWeights(), buffer, DOWNWARD, end_of_iteration(), layerSort(), LINE_LENGTH, number_of_layers, number_of_processors, terminate(), tracePrint(), updateCrossingsForLayer(), and UPWARD.

Referenced by runHeuristic().

Here is the call graph for this function:

Variable Documentation

◆ iteration

int iteration

The current iteration, or, the number of iterations up to this point.

Definition at line 47 of file heuristics.c.

Referenced by end_of_iteration(), maxEdgeStretch(), print_last_iteration_message(), print_standard_termination_message(), sift_decreasing(), sift_increasing(), sifting(), terminate(), totalStretch(), trace_printer(), and tracePrint().

◆ post_processing_crossings

int post_processing_crossings

The minimum total number of crossings during post processing

Definition at line 51 of file heuristics.c.

Referenced by swapping().

◆ post_processing_iteration

int post_processing_iteration

The current iteration during post processing

Definition at line 48 of file heuristics.c.

Referenced by capture_post_processing_stats(), and swapping().