Crossings Minimization  1.0
min_crossings.c File Reference

Main program for crossing minimization heuristics. More...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <getopt.h>
#include <limits.h>
#include <assert.h>
#include <libgen.h>
#include <float.h>
#include "stats.h"
#include "defs.h"
#include "heuristics.h"
#include "graph_io.h"
#include "graph.h"
#include "crossings.h"
#include "channel.h"
#include "min_crossings.h"
#include "order.h"
#include "priority_edges.h"
#include "timing.h"
#include "random.h"
Include dependency graph for min_crossings.c:

Go to the source code of this file.

Functions

static void printUsage (void)
 
static char * base_name (char *buffer)
 
static void runPreprocessor (void)
 
static void runHeuristic (void)
 
int main (int argc, char *argv[])
 

Variables

char * heuristic = ""
 
char * preprocessor = ""
 
int max_iterations = INT_MAX
 
double runtime = 0
 
double max_runtime = DBL_MAX
 
double start_time = 0
 
int number_of_processors = 1
 
bool standard_termination = true
 
enum adjust_weights_enum adjust_weights = LEFT
 
enum sift_option_enum sift_option = DEGREE
 
enum mce_option_enum mce_option = NODES
 
enum sifting_style_enum sifting_style = DEFAULT
 
enum pareto_objective_enum pareto_objective = NO_PARETO
 
int capture_iteration = INT_MIN
 
bool favored_edges = false
 
bool randomize_order = false
 
bool balanced_weight = false
 
bool produce_output = false
 
char * output_base_name = NULL
 
bool verbose = false
 
int trace_freq = -1
 
Orderptr best_crossings_order = NULL
 
Orderptr best_edge_crossings_order = NULL
 
Orderptr best_total_stretch_order = NULL
 
Orderptr best_bottleneck_stretch_order = NULL
 
Orderptr best_favored_crossings_order = NULL
 
static char output_file_name [MAX_NAME_LENGTH]
 
static bool do_post_processing = false
 

Detailed Description

Main program for crossing minimization heuristics.

Author
Matt Stallmann
Date
2008/12/29
Id
min_crossings.c 135 2016-01-13 20:27:33Z mfms

Definition in file min_crossings.c.

Function Documentation

◆ base_name()

static char* base_name ( char *  buffer)
static

Truncate the string in buffer so that it ends before the first '.' and copy it into the buffer.

Returns
a pointer to the position of the last '/' so as to remove the directory component of the name in the buffer

Used to emulate the 'basename' command

Todo:
there must be a better way to do this, but basename() by itself does not work.

Definition at line 132 of file min_crossings.c.

Referenced by main().

◆ main()

int main ( int  argc,
char *  argv[] 
)

As of now, the main program does the following seqence of events -

  1. Read the DOT file
  2. Read the ORD file
  3. Display the attributes of the graph
  4. Count the number of crossings.
  5. Apply a preprocess and a heuristic (both optional) on the graph
  6. Optionally apply a post-processor that repeatedly swaps neighboring nodes until there's no more improvement
  7. Count the number of crossings after each phase (and save the ORD files for the minimum number of crossings in each phase)
Todo:
Need functions to deallocate everything (in the appropriate modules)

Definition at line 234 of file min_crossings.c.

References adjust_weights, AVG, balanced_weight, base_name(), BOTTLENECK_STRETCH, BOTTLENECK_TOTAL, buffer, capture_beginning_stats(), capture_heuristic_stats(), capture_iteration, capture_post_processing_stats(), capture_preprocessing_stats(), cleanup_order(), createFanoutList(), createFavoredEdgeInfo(), createOrdFileName(), DEGREE, do_post_processing, EARLY, EDGES, end_of_iteration(), favored_edges, favoredEdges(), getUserSeconds(), heuristic, init_crossing_stats(), init_genrand(), init_order(), initChannels(), initCrossings(), initPriorityEdges(), LAYER, layers, LEFT, MAX, max_iterations, MAX_NAME_LENGTH, max_runtime, mce_option, layer_struct::nodes, NODES, NONE, number_of_layers, layer_struct::number_of_nodes, number_of_processors, numberOfCrossings(), numberOfFavoredEdges(), ONE_NODE, output_base_name, output_file_name, pareto_objective, preprocessor, print_graph_statistics(), print_run_statistics(), printUsage(), produce_output, RANDOM, randomize_order, readGraph(), restore_order(), runHeuristic(), runPreprocessor(), RUNTIME, sift_option, sifting_style, standard_termination, start_time, STRETCH_TOTAL, swapping(), TOTAL, trace_freq, updateAllCrossings(), verbose, writeDot(), and writeOrd().

Here is the call graph for this function:

◆ printUsage()

static void printUsage ( void  )
static

prints usage message

Todo:
sort these alphabetically and make them more meaningful and/or use long options

Definition at line 83 of file min_crossings.c.

Referenced by main(), runHeuristic(), and runPreprocessor().

◆ runHeuristic()

static void runHeuristic ( void  )
static
Todo:
It would be nice to have a way to run two heuristics, one after the other. Not really needed - can always use the output file of one as input to the other

Definition at line 164 of file min_crossings.c.

References adjust_weights, AVG, balanced_weight, barycenter(), evenOddBarycenter(), heuristic, maximumCrossingsEdge(), maximumCrossingsEdgeWithSifting(), maximumCrossingsNode(), maximumStretchEdge(), median(), modifiedBarycenter(), number_of_processors, printUsage(), rotatingBarycenter(), sifting(), slabBarycenter(), staticBarycenter(), and upDownBarycenter().

Referenced by main().

Here is the call graph for this function:

◆ runPreprocessor()

static void runPreprocessor ( void  )
static

Definition at line 140 of file min_crossings.c.

References breadthFirstSearch(), depthFirstSearch(), middleDegreeSort(), preprocessor, and printUsage().

Referenced by main().

Here is the call graph for this function:

Variable Documentation

◆ adjust_weights

enum adjust_weights_enum adjust_weights = LEFT

Definition at line 47 of file min_crossings.c.

Referenced by barycenterWeights(), main(), medianWeights(), node_weight(), and runHeuristic().

◆ balanced_weight

bool balanced_weight = false
Todo:
not clear which value of this option works best; stay tuned ...

Definition at line 58 of file min_crossings.c.

Referenced by barycenterWeights(), main(), and runHeuristic().

◆ best_bottleneck_stretch_order

Orderptr best_bottleneck_stretch_order = NULL

structure to save layer orderings for minimum bottleneck edge stretch so far

Definition at line 69 of file min_crossings.c.

Referenced by update_best_all().

◆ best_crossings_order

Orderptr best_crossings_order = NULL

structure to save layer orderings for minimum crossings so far

Definition at line 66 of file min_crossings.c.

Referenced by swapping(), and update_best_all().

◆ best_edge_crossings_order

Orderptr best_edge_crossings_order = NULL

structure to save layer orderings for minimum edge crossings so far

Definition at line 67 of file min_crossings.c.

Referenced by update_best_all().

◆ best_favored_crossings_order

Orderptr best_favored_crossings_order = NULL

structure to save layer orderings for minimum crossings involving favored edges so far

Definition at line 70 of file min_crossings.c.

Referenced by update_best_all().

◆ best_total_stretch_order

Orderptr best_total_stretch_order = NULL

structure to save layer orderings for minimum total edge stretch so far

Definition at line 68 of file min_crossings.c.

Referenced by update_best_all().

◆ capture_iteration

int capture_iteration = INT_MIN

Save the order at the end of the given iteration in a file called capture-x.ord, where x is the iteration number. If the value is negative, no capture takes place.

Definition at line 52 of file min_crossings.c.

Referenced by end_of_iteration(), main(), and printCrossings().

◆ do_post_processing

bool do_post_processing = false
static

Definition at line 75 of file min_crossings.c.

Referenced by main().

◆ favored_edges

bool favored_edges = false

True if there is a list of favored edges based on predecessors and successors of a central node

Definition at line 53 of file min_crossings.c.

Referenced by main().

◆ heuristic

◆ max_iterations

int max_iterations = INT_MAX

Maximum number of iterations for the main heuristic; this is the number of times a layer is sorted. If neither max_iterations nor max_runtime is specified, standard_termination is used.

Definition at line 41 of file min_crossings.c.

Referenced by end_of_iteration(), main(), print_last_iteration_message(), printCrossings(), sift_decreasing(), sift_increasing(), sifting(), and terminate().

◆ max_runtime

double max_runtime = DBL_MAX

Runtime (in seconds) at which the main heuristic will be terminated; the termination takes place at this runtime or at max_iterations, whichever comes first. If neither max_iterations nor max_runtime is specified, standard_termination is used.

Definition at line 43 of file min_crossings.c.

Referenced by end_of_iteration(), and main().

◆ mce_option

enum mce_option_enum mce_option = NODES

Definition at line 49 of file min_crossings.c.

Referenced by edge_sift_iteration(), end_mce_pass(), and main().

◆ number_of_processors

int number_of_processors = 1

When simulating a heuristic that can be parallelized, there may be a tradeoff between number of processors and solution quality. Fewer processors may lead to fewer crossings because the number of crossings can be checked more often. For example, if there is only one processor, you can check every time a change occurs. If there are more, you have to wait until the next synchronization point.

Definition at line 45 of file min_crossings.c.

Referenced by adjust_weights_avg(), evenOddBarycenter(), main(), rotatingBarycenter(), runHeuristic(), slab_bary_iteration(), slabBarycenter(), staticBarycenter(), and upDownBarycenter().

◆ output_base_name

char* output_base_name = NULL

output file names are of the form output_base_name-x.ord, where x is information about the heuristic used

Definition at line 60 of file min_crossings.c.

Referenced by createOrdFileName(), and main().

◆ output_file_name

char output_file_name[MAX_NAME_LENGTH]
static

buffer to be used for all output file names

Definition at line 73 of file min_crossings.c.

Referenced by end_of_iteration(), and main().

◆ pareto_objective

◆ preprocessor

char* preprocessor = ""

Definition at line 40 of file min_crossings.c.

Referenced by createOrdFileName(), main(), print_run_statistics(), and runPreprocessor().

◆ produce_output

bool produce_output = false

True if ord files representing the minimum number of crossings should be written

Definition at line 59 of file min_crossings.c.

Referenced by main().

◆ randomize_order

bool randomize_order = false

True if the edge list (node list) is to be randomized after each pass of mce (sifting)

Definition at line 54 of file min_crossings.c.

Referenced by main(), maxCrossingsEdge(), maxCrossingsLayer(), maxCrossingsNode(), maxStretchEdge(), and sifting().

◆ runtime

double runtime = 0

Definition at line 42 of file min_crossings.c.

◆ sift_option

enum sift_option_enum sift_option = DEGREE

Definition at line 48 of file min_crossings.c.

Referenced by main().

◆ sifting_style

enum sifting_style_enum sifting_style = DEFAULT

Definition at line 50 of file min_crossings.c.

Referenced by main().

◆ standard_termination

bool standard_termination = true

True if using the standard, "natural" stopping criterion for the iterative heuristic, e.g., no improvement after a sweep for barycenter.

Definition at line 46 of file min_crossings.c.

Referenced by main(), sifting(), and terminate().

◆ start_time

double start_time = 0

Time that the preprocessor (or heuristic if none) started running

Definition at line 44 of file min_crossings.c.

Referenced by main().

◆ trace_freq

int trace_freq = -1

-1 means no tracing, 0 means end of iteration only, trace_freq > 0 means print a trace message every trace_freq iterations.

Definition at line 63 of file min_crossings.c.

Referenced by main(), and tracePrint().

◆ verbose

bool verbose = false

True if verbose information about the graph should be printed

Definition at line 62 of file min_crossings.c.

Referenced by main(), and print_graph_statistics().