High-level implementations of various heuristics. More...

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include <math.h>
#include "min_crossings.h"
#include "heuristics.h"
#include "graph.h"
#include "barycenter.h"
#include "median.h"
#include "dfs.h"
#include "crossings.h"
#include "channel.h"
#include "sorting.h"
#include "graph_io.h"
#include "sifting.h"
#include "stats.h"
#include "priority_edges.h"
#include "swap.h"
#include "timing.h"
#include "random.h"

Include dependency graph for heuristics.c:

Go to the source code of this file.

Macros
#define	TRACE_FREQ_THRESHOLD 2

#define	MAX_FAILS 1

Functions
void	createOrdFileName (char output_file_name, const char appendix)

void	createDotFileName (char output_file_name, const char appendix)

static void	trace_printer (int layer, const char *message)

void	tracePrint (int layer, const char *message)

static bool	no_improvement (void)

static void	print_last_iteration_message (void)

bool	end_of_iteration (void)

static void	print_standard_termination_message ()

static bool	terminate ()

bool	isFixedNode (Nodeptr node)

bool	isFixedEdge (Edgeptr edge)

bool	isFixedLayer (int layer)

void	fixNode (Nodeptr node)

void	fixEdge (Edgeptr edge)

void	fixLayer (int layer)

bool	allNodesFixed (void)

void	clearFixedNodes (void)

void	clearFixedEdges (void)

void	clearFixedLayers (void)

int	totalDegree (int layer)

int	maxDegreeLayer (void)

Nodeptr	maxDegreeNode (void)

void	median (void)

void	barycenter (void)

void	modifiedBarycenter (void)

void	staticBarycenter (void)

void	evenOddBarycenter (void)

void	upDownBarycenter (void)

static bool	slab_bary_iteration (int offset, int slab_size, Orientation sort_direction)

void	slabBarycenter (void)

void	rotatingBarycenter (void)

static bool	sift_iteration (Nodeptr node)

static bool	edge_sift_iteration (Edgeptr edge)

static bool	total_stretch_sift_iteration (Nodeptr node)

void	maximumCrossingsNode (void)

void	maximumCrossingsEdgeWithSifting (void)

static bool	end_mce_pass (Edgeptr edge)

void	maximumCrossingsEdge (void)

void	maximumStretchEdge (void)

static bool	sift_decreasing (const Nodeptr *node_array, int num_nodes, int initial_crossings)

static bool	sift_increasing (const Nodeptr *node_array, int num_nodes, int initial_crossings)

void	sifting (void)

void	breadthFirstSearch (void)

void	depthFirstSearch (void)

static void	weight_first_to_middle (int layer)

void	middleDegreeSort (void)

static void	swap_nodes (Nodeptr *node_array, int i, int j)

static int	swapping_iteration (int crossings, int odd_even)

void	swapping (void)

Variables
int	iteration = 0

int	post_processing_iteration = 0

int	min_crossings = INT_MAX

int	post_processing_crossings = INT_MAX

int	min_edge_crossings = INT_MAX

int	min_crossings_iteration = -1

int	min_edge_crossings_iteration = -1

static char	buffer [MAX_NAME_LENGTH]

Detailed Description

High-level implementations of various heuristics.

Author: Matthias Stallmann

Date: 2008/12/29

Id: heuristics.c 140 2016-02-15 16:13:56Z mfms

Definition in file heuristics.c.

Macro Definition Documentation

◆ MAX_FAILS

#define MAX_FAILS 1

Definition at line 941 of file heuristics.c.

Referenced by sifting().

◆ TRACE_FREQ_THRESHOLD

#define TRACE_FREQ_THRESHOLD 2

Todo:: The incrementing of 'iteration' is far from transparent; it takes place in end_of_iteration(), which is called from a number of different places, most in other modules; perhaps this is okay, but the comments should at least indicate what's going on. Furthermore, the stopping criteria are buried in lots of different places and the functions that are invoked have other side effects.

if trace_freq is <= TRACE_FREQ_THRESHOLD, then a message is printed at the end of each pass; end of pass messages don't appear otherwise.

Definition at line 45 of file heuristics.c.

Referenced by tracePrint().

Function Documentation

◆ allNodesFixed()

bool allNodesFixed ( void )

Definition at line 300 of file heuristics.c.

References isFixedNode(), layers, layer_struct::nodes, number_of_layers, and layer_struct::number_of_nodes.

Referenced by end_mce_pass(), maximumCrossingsEdgeWithSifting(), and maximumStretchEdge().

Here is the call graph for this function:

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

void clearFixedEdges ( void )

Definition at line 329 of file heuristics.c.

References node_struct::down_degree, node_struct::down_edges, edge_struct::fixed, layers, layer_struct::nodes, number_of_layers, and layer_struct::number_of_nodes.

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

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

void clearFixedNodes ( void )

Definition at line 315 of file heuristics.c.

References node_struct::fixed, layers, layer_struct::nodes, number_of_layers, and layer_struct::number_of_nodes.

Referenced by createFanoutList(), maximumCrossingsEdge(), maximumCrossingsEdgeWithSifting(), maximumCrossingsNode(), maximumStretchEdge(), and printCrossings().

◆ 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_name	a buffer for the file name to be created, assumed to be big enough
appendix	a 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_name	a buffer for the file name to be created, assumed to be big enough
appendix	a 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:

◆ edge_sift_iteration()

static bool edge_sift_iteration ( Edgeptr edge )

static

Handles sifting of both endpoints of an edge and all related bookkeeping

Returns: true if max iterations reached

Todo:: Consider sifting only one endpoint even if both are not fixed and leaving the edge unfixed in that case.

Definition at line 743 of file heuristics.c.

References buffer, edge_struct::down_node, EDGES, end_of_iteration(), fixNode(), heuristic, isFixedNode(), node_struct::layer, mce_option, node_struct::name, numberOfCrossingsNode(), ONE_NODE, node_struct::position, sift_node_for_edge_crossings(), tracePrint(), and edge_struct::up_node.

Referenced by maximumCrossingsEdge().

Here is the call graph for this function:

◆ end_mce_pass()

static bool end_mce_pass ( Edgeptr edge )

static

Returns: true if the pass should end based on command-line option mce_option; note: if the option is EDGES, maxCrossingsEdge() will return NULL and this will not happen unless all the nodes have been fixed as well, in most cases more than once.

Definition at line 862 of file heuristics.c.

References allNodesFixed(), edge_struct::down_node, EARLY, isFixedNode(), mce_option, NODES, and edge_struct::up_node.

Referenced by maximumCrossingsEdge().

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 )

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 )

Definition at line 298 of file heuristics.c.

References edge_struct::fixed.

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

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

void fixNode ( Nodeptr node )

Definition at line 297 of file heuristics.c.

References node_struct::fixed.

Referenced by edge_sift_iteration(), maximumCrossingsEdgeWithSifting(), maximumStretchEdge(), printCrossings(), sift_iteration(), and total_stretch_sift_iteration().

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

bool isFixedNode ( Nodeptr node )

Definition at line 294 of file heuristics.c.

References node_struct::fixed.

Referenced by allNodesFixed(), edge_sift_iteration(), end_mce_pass(), maxCrossingsNode(), maximumCrossingsEdgeWithSifting(), and maximumStretchEdge().

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

◆ maxDegreeNode()

Nodeptr maxDegreeNode ( void )

Definition at line 386 of file heuristics.c.

References DEGREE, layers, layer_struct::nodes, number_of_layers, and layer_struct::number_of_nodes.

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

Definition at line 443 of file heuristics.c.

References barycenterDownSweep(), barycenterUpSweep(), barycenterWeights(), BOTH, clearFixedLayers(), end_of_iteration(), fixLayer(), layerSort(), maxCrossingsLayer(), terminate(), tracePrint(), and updateCrossingsForLayer().

Referenced by runHeuristic().

Here is the call graph for this function:

◆ no_improvement()

static bool no_improvement ( void )

static

Returns: true if none of the crossing measures of interest have improved since the last call to this function

Side effect: all measures are updated

Definition at line 142 of file heuristics.c.

References bottleneck_stretch, favored_edge_crossings, has_improved_double(), has_improved_int(), max_edge_crossings, total_crossings, and total_stretch.

Referenced by print_last_iteration_message(), and terminate().

Here is the call graph for this function:

◆ print_last_iteration_message()

static void print_last_iteration_message ( void )

static

Prints a message if number of crossings (of various types) are still improving but max iterations have been reached.

Todo:: more information in the "still improving" message

Definition at line 167 of file heuristics.c.

References graph_name, iteration, max_iterations, no_improvement(), and RUNTIME.

Referenced by end_of_iteration().

Here is the call graph for this function:

◆ print_standard_termination_message()

static void print_standard_termination_message ( )

static

Prints a message to indicate the point at which standard termination would have occurred if the option is to keep going. This is called at the end of a pass. It will not be called if max iterations has been reached.

message already printed?

Definition at line 248 of file heuristics.c.

References crossing_stats_int::best, graph_name, iteration, max_edge_crossings, and total_crossings.

Referenced by terminate().

◆ rotatingBarycenter()

void rotatingBarycenter ( void )

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:

◆ sift_decreasing()

static bool sift_decreasing	(	const Nodeptr *	node_array,
		int	num_nodes,
		int	initial_crossings
	)

static

Sifts node in decreasing order as determined by the input array

Returns: false if the sift was unsuccessful, i.e., it did not improve upon initial_crossings or if the maximum number of iterations was reached

Note: here the key is improvement upon the number of crossings at the beginning of this sifting pass, not necessarily the number of crossings overall.

Definition at line 952 of file heuristics.c.

References buffer, end_of_iteration(), iteration, max_iterations, numberOfCrossings(), sift(), and tracePrint().

Referenced by sifting().

Here is the call graph for this function:

◆ sift_increasing()

static bool sift_increasing	(	const Nodeptr *	node_array,
		int	num_nodes,
		int	initial_crossings
	)

static

Sifts node in increasing order as determined by the input array

Returns: false if the sift was unsuccessful, i.e., it did not improve upon initial_crossings or if the maximum number of iterations was reached

Note: here the key is improvement upon the number of crossings at the beginning of this sifting pass, not necessarily the number of crossings overall.

Definition at line 989 of file heuristics.c.

References buffer, end_of_iteration(), iteration, max_iterations, numberOfCrossings(), sift(), and tracePrint().

Referenced by sifting().

Here is the call graph for this function:

◆ sift_iteration()

static bool sift_iteration ( Nodeptr node )

static

Handles sifting of a node and all related bookkeeping

Returns: true if max_iterations reached

Definition at line 725 of file heuristics.c.

References buffer, end_of_iteration(), fixNode(), heuristic, node_struct::layer, node_struct::name, sift(), and tracePrint().

Referenced by maximumCrossingsEdgeWithSifting(), and maximumCrossingsNode().

Here is the call graph for this function:

◆ sifting()

void sifting ( void )

Definition at line 1006 of file heuristics.c.

References end_of_iteration(), genrand_permute(), iteration, master_node_list, MAX_FAILS, max_iterations, number_of_nodes, numberOfCrossings(), randomize_order, sift_decreasing(), sift_increasing(), sortByDegree(), standard_termination, terminate(), and tracePrint().

Referenced by runHeuristic().

Here is the call graph for this function:

◆ slab_bary_iteration()

static bool slab_bary_iteration	(	int	offset,
		int	slab_size,
		Orientation	sort_direction
	)

static

Does the parallel part of each iteration of the slabBarycenter algorithm below.

Parameters

offset how far above the bottom of the slab each layer to be sorted is

Returns: true if this iteration is to be the last one

Definition at line 612 of file heuristics.c.

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

Referenced by slabBarycenter().

Here is the call graph for this function:

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

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 )

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:

◆ swap_nodes()

static void swap_nodes	(	Nodeptr *	node_array,
		int	i,
		int	j
	)

static

Definition at line 1139 of file heuristics.c.

References node_struct::position.

Referenced by swapping_iteration().

◆ swapping()

void swapping ( void )

!!! 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:

◆ swapping_iteration()

static int swapping_iteration	(	int	crossings,
		int	odd_even
	)

static

Does an iteration where either all swaps between nodes i, i+1 on layers L, L+1 are considered where i, L are either even or odd

Parameters

crossings	the number of crossings before this iteration
odd_even	is 1 if odd values of i and L are considered, even otherwise

Returns: the number of crossings after this iteration

Definition at line 1156 of file heuristics.c.

References layers, node_crossings(), layer_struct::nodes, number_of_layers, layer_struct::number_of_nodes, swap_nodes(), and tracePrint().

Referenced by swapping().

Here is the call graph for this function:

◆ terminate()

static bool terminate ( )

static

Returns: True if termination is based on "convergence" rather than the number of iterations and the heuristic exhibits no improvement in any of the crossing counts.

Prints a message about failure to improve even if stopping criterion is number of iterations.

Definition at line 277 of file heuristics.c.

References iteration, max_iterations, no_improvement(), print_standard_termination_message(), and standard_termination.

Referenced by barycenter(), evenOddBarycenter(), maximumCrossingsEdge(), maximumCrossingsEdgeWithSifting(), maximumCrossingsNode(), maximumStretchEdge(), median(), modifiedBarycenter(), rotatingBarycenter(), sifting(), slabBarycenter(), staticBarycenter(), and upDownBarycenter().

Here is the call graph for this function:

◆ total_stretch_sift_iteration()

static bool total_stretch_sift_iteration ( Nodeptr node )

static

Definition at line 793 of file heuristics.c.

References buffer, end_of_iteration(), fixNode(), heuristic, node_struct::layer, node_struct::name, node_struct::position, sift_node_for_total_stretch(), tracePrint(), and updateAllCrossings().

Referenced by maximumStretchEdge().

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

◆ trace_printer()

static void trace_printer	(	int	layer,
		const char *	message
	)

static

Does the actual printing for tracePrint

Todo:: Use trace_freq == -1 to indicate that printing should only be done if there has been improvement since last time; can use INT_MAX as default instead of -1.

The logic would be something like:

update crossings
trace_freq == -1 then _ update_best (stats.c) _ return if ! has_improved (stats.c)

Definition at line 105 of file heuristics.c.

References crossing_stats_int::best, crossing_stats_double::best, iteration, max_edge_crossings, maxEdgeCrossings(), numberOfCrossings(), RUNTIME, total_crossings, total_stretch, totalStretch(), and updateAllCrossings().

Referenced by tracePrint().

Here is the call graph for this function:

◆ tracePrint()

void tracePrint	(	int	layer,
		const char *	message
	)

Prints information about current number of iterations, crossings, etc.,

Parameters

message	a message identifying the context of the printout.
layer	the layer that was just sorted

Definition at line 122 of file heuristics.c.

References iteration, trace_freq, TRACE_FREQ_THRESHOLD, and trace_printer().

Referenced by barycenter(), barycenterDownSweep(), barycenterUpSweep(), edge_sift_iteration(), evenOddBarycenter(), maximumCrossingsEdge(), maximumCrossingsEdgeWithSifting(), maximumCrossingsNode(), maximumStretchEdge(), median(), medianDownSweep(), medianUpSweep(), modifiedBarycenter(), rotatingBarycenter(), sift_decreasing(), sift_increasing(), sift_iteration(), sifting(), slab_bary_iteration(), slabBarycenter(), staticBarycenter(), swapping(), swapping_iteration(), total_stretch_sift_iteration(), and upDownBarycenter().

Here is the call graph for this function:

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

◆ weight_first_to_middle()

static void weight_first_to_middle ( int layer )

static

Assigns weights so that, in a subsequent layer sort, the last node on the layer is moved to the middle position, the next to last on one side, the third from last on the other, etc.

Definition at line 1083 of file heuristics.c.

References layers, layer_struct::nodes, layer_struct::number_of_nodes, and node_struct::weight.

Referenced by middleDegreeSort().

Variable Documentation

◆ buffer

char buffer[MAX_NAME_LENGTH]

static

buffer for formatting all tracePrint strings

Definition at line 59 of file heuristics.c.

Referenced by edge_sift_iteration(), main(), maximumCrossingsEdge(), maximumCrossingsEdgeWithSifting(), maximumStretchEdge(), rotatingBarycenter(), sift_decreasing(), sift_increasing(), sift_iteration(), slab_bary_iteration(), slabBarycenter(), total_stretch_sift_iteration(), and upDownBarycenter().

◆ iteration

int iteration = 0

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

◆ min_crossings

int min_crossings = INT_MAX

Definition at line 50 of file heuristics.c.

◆ min_crossings_iteration

int min_crossings_iteration = -1

Definition at line 53 of file heuristics.c.

◆ min_edge_crossings

int min_edge_crossings = INT_MAX

Definition at line 52 of file heuristics.c.

◆ min_edge_crossings_iteration

int min_edge_crossings_iteration = -1

Definition at line 54 of file heuristics.c.

◆ post_processing_crossings

int post_processing_crossings = INT_MAX

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 = 0

The current iteration during post processing

Definition at line 48 of file heuristics.c.

Referenced by capture_post_processing_stats(), and swapping().

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ MAX_FAILS

◆ TRACE_FREQ_THRESHOLD

Function Documentation

◆ allNodesFixed()

◆ barycenter()

◆ breadthFirstSearch()

◆ clearFixedEdges()

◆ clearFixedLayers()

◆ clearFixedNodes()

◆ createDotFileName()

◆ createOrdFileName()

◆ depthFirstSearch()

◆ edge_sift_iteration()

◆ end_mce_pass()

◆ end_of_iteration()

◆ evenOddBarycenter()

◆ fixEdge()

◆ fixLayer()

◆ fixNode()

◆ isFixedEdge()

◆ isFixedLayer()

◆ isFixedNode()

◆ maxDegreeLayer()

◆ maxDegreeNode()

◆ maximumCrossingsEdge()

◆ maximumCrossingsEdgeWithSifting()

◆ maximumCrossingsNode()

◆ maximumStretchEdge()

◆ median()

◆ middleDegreeSort()

◆ modifiedBarycenter()

◆ no_improvement()

◆ print_last_iteration_message()

◆ print_standard_termination_message()

◆ rotatingBarycenter()

◆ sift_decreasing()

◆ sift_increasing()

◆ sift_iteration()

◆ sifting()

◆ slab_bary_iteration()

◆ slabBarycenter()

◆ staticBarycenter()

◆ swap_nodes()

◆ swapping()

◆ swapping_iteration()

◆ terminate()

◆ total_stretch_sift_iteration()

◆ totalDegree()

◆ trace_printer()

◆ tracePrint()

◆ upDownBarycenter()

◆ weight_first_to_middle()

Variable Documentation

◆ buffer

◆ iteration

◆ min_crossings

◆ min_crossings_iteration

◆ min_edge_crossings

◆ min_edge_crossings_iteration

◆ post_processing_crossings

◆ post_processing_iteration