Programs generated by 'make':

 - min_crossings: implements all the heuristics; has lots of options that
 control which preprocessor/heuristic is run, stopping criteria, etc.
 - create_random_dag: creates a connected dag; command-line arguments
 specify the number of nodes, edges, and layers, and the skew factor
 A script for creating a uniform dag is in the scripts directory: it's
 called createDag
 - add_edges: adds a given number of randomly chosen edges to a layered
 dag 


Copyright (C) 2009, 2011 Matthias Stallmann, Saurabh Gupta.
Contact: matt_stallmann AT ncsu DOT edu

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License (gnu-public-license.txt) along with this program.

If not, write to the
 Free Software Foundation, Inc.,
 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

Heuristics

Descriptions of the heuristics implemented as part of this project.

Each heuristic consists of a preprocessing phase (specified using the -p option) and an iterative phase (specified using -h).

Possible preprocessors are

dfs: Do a depth-first search of the graph and sort each layer by preorder number. The start node is a node on the lowest level. Adjacent vertices on the next higher layer are explored before those on the next lower layer. See dfs.
bfs: same as dfs, but a breadth-first search is done (not implemented)
mds: (middle degree sort) Identify the node w with highest degree, put it in the middle of its layer and sort the rest so that larger degree vertices are closer to the middle. Then do an upward and a downward sweep of barycenter (see below).

Possible main (iterative) heuristics are as follows. In each case the actions that take place during a single pass are described. Passes are repeated until there is no improvement in number of crossings (default) or a fixed number has occurred (specified by a command-line option).

bary: The barycenter heuristic defined in the literature – each layer is sorted using the average position of the adjacent vertices on the layer above/below it (average position sorting). In a single pass, barycenter does an upsweep, sorting layers 1 to k-1 based on the layer above each, and a downsweep, sorting layers k down to 2 based on the layer below each.
mod_bary: Choose the layer L whose edges contribute the most crossings. Use an average position sort with respect to the layer above and the layer below L (simulatiously). Then sort layers L-1 and L+1 with respect to L. Mark L and repeat until all layers have been marked. The order in which layers are considered is dynamic, i.e., may change as the result of the sorting of a previous layer.
- sifting: Use the sifting heuristic described in Matuszewski et al., Using Sifting for k-layer Straightline Crossing Minimization. To sift a node w, find its optimal position, i.e., keeping all other nodes on w's layer the same determine the position among them that minimizes crossings. Nodes are sorted by decreasing degree and sifted accordingly (other node sequences were proposed but are not implemented here).
- mcn: (maximum crossings node) This is a variation on sifting where the next node to be sifted is the one that has the maximum number of crossings. This information is updated dynamically and nodes are sifted until all have been "marked".
- mce: (maximum crossings edge) Another variation on sifting – here, the heuristic picks an edge e = vw that has the maximum number of crossings. Both v and w are sifted, but the objective is to minimize the number of crossings for e. The chosen position in each case is a local rather than global minimum. There are three options for ending a pass.
1. nodes: (default) mark a node when it's an endpoint of a chosen edge; stop when all nodes are marked
2. early: mark a node when it's the endpoint of a chosen edge; stop as soon as the next edge under consideration has both endpoints marked.
3. edges: mark an edge when it is chosen; stop when all edges are marked

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

a two pass version of barycenter (or any other heuristic) in which the first pass minimizes crossings among of preferred edges only and the second pass minimizes crossings of the remaining edges, keeping the endpoints of preferred edges fixed
a version of mce in which only the preferred edges are sifted

The set of preferred edges can be specified in a file using a -f option. Format for this file can be simple: a single integer giving the number of edges followed by pairs of vertex names, one per line, giving the actual edges. Alternatively, they could be marked in the dot file.