Crossings Minimization  1.0
Todo List
Global add_edge (Nodeptr upper_node, Nodeptr lower_node)
Avoid duplication with the same function in create_random_tree and add_edges
Global adjust_weights_left (int layer)
adjust_weights_left() and adjust_weights_avg() have identical counterparts in median.c
Global balanced_weight
not clear which value of this option works best; stay tuned ...
Global base_name (char *buffer)
there must be a better way to do this, but basename() by itself does not work.
File channel.h
eventually channels should replace the interlayer structures in crossings.c since can they serve more general purposes; note that the current discipline in crossings.[ch] is that, when an iteration sorts a layer, the crossings for the adjoining channels are updated, including the max crossings node and edge; here, we do this with stretch and leave the crossings updates alone for now.
Global countIsolatedNodes ()
Should eliminate the isolated nodes altogether; on each layer -
Global createFavoredEdgeInfo (char *file_name_buffer, char *graph_name_buffer, char *comment_buffer)
put more information into the graph name and/or comments; also, most graph names have characters such as - and + in them; these must be converted to _'s
page Crossing Minimization
Version that allows user to specify a set of preferred edges who crossings should be minimimized at the expense of others to a certain degree. Typically, this would be used to highlight predecessors/successors of a node. Variations on existing heuristics:
File dot_and_ord_to_sgf.c
comments from the original dot file are not preserved and should be added by an external script for now.
Global edge_sift_iteration (Edgeptr edge)
Consider sifting only one endpoint even if both are not fixed and leaving the edge unfixed in that case.
Global init_statistics (int size)
allow for unlimited capacity
Global initDot (FILE *in)
eventually will want to pick up the first comment
Global main (int argc, char *argv[])
Need functions to deallocate everything (in the appropriate modules)
Global master_node_list
this and master_edge_list could really be useful for heuristics such as mcn and mce.
Global maxCrossingsEdgeStatic (void)
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
Global maximumCrossingsEdge (void)
what follows is now incorporated into maximumCrossingsEdgeWithSifting(); eventually the two could be merged
Global maximumStretchEdge (void)
one could also base the movement on minimizing the maximum stretch of any edge, similar to mce
Global print_graph_statistics (FILE *output_stream)
minimize maximum crossings on any layer
Global print_last_iteration_message (void)
more information in the "still improving" message
Global printUsage (void)
sort these alphabetically and make them more meaningful and/or use long options
Global runHeuristic (void)
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
Global sifting_style
The introduction of mce_s as a separate heuristic makes this enum superfluous for now, but maybe it should be revived for the sake of symmetry and completeness – so that the sifting heuristic can be used with bottleneck minimization
Global sifting_style
The introduction of mce_s as a separate heuristic makes this enum superfluous for now, but maybe it should be revived for the sake of symmetry and completeness – so that the sifting heuristic can be used with bottleneck minimization
Global slabBarycenter (void)
rename this as shiftBarycenter, which would be more in keeping with its behavior.
Global staticBarycenter (void)
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().
File stats.c
To keep things simple, total stretch is rounded to an integer value
Global swap_nodes (int layer, int i, int j)
this might be useful elsewhere
Global TRACE_FREQ_THRESHOLD
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.
Global trace_printer (int layer, const char *message)
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.
Global writeOrd (const char *ord_file)
ord file should have information about heuristic that created it, etc., embedded in it. Use of the file/graph name can be problematic if we want to check what happens when one heuristic follows another for a whole class using a script. There needs to be some way to differentiate among these files.