#acl EditorsGroup:read,write,delete,revert,admin CarmineDodaro:read,write All:read = Crossing minimization in layered graphs = == Problem Description == The standard approach for drawing hierarchical network diagrams is a three phase approach in which 1. nodes in the graph are assigned levels producing a {{{k}}}-level graph; 1. nodes are assigned an order so as to minimize edge crossings in the {{{k}}}-level graph; and 1. the edge routes and node positions are computed. There has been considerable research into step 2 which is called {{{k}}}-level crossing minimization. Unfortunately this step is NP-hard for even two layers ({{{k = 2}}}) where the ordering on one layer is given. Thus, research has focussed on developing heuristics to solve it. In practice the approach is to iterate through the levels, re-ordering the nodes on each level using heuristic techniques such as the barycentric method. Recently it was shown that modern optimization technology can tackle the complete {{{k}}}-level crossing minimization problem at least for small to medium sized graphs, generating optimal crossings. A crossing in a graph occurs if there are: 1. nodes N1, N2 on layer i, and 1. nodes N3, N4 on layer j, (j <> i), and 1. edges e1 = (N1,N3), e2 = (N2,N4), and 1. the position of N1 is antecedent of the position of N2, and 1. the position of N4 is antecedent of the position of N3. == Predicates == * '''Input''': {{{layers/1, width/2, in_layer/2, edge/2}}} * '''Output''': {{{position/2}}} == Input format == The predicates {{{layers/1}}} and {{{in_layer/2}}} give the partitioning of nodes into layers. For convenience, {{{width/2}}} gives the number of nodes in a layer. For example {{{ layers(2). width(0, 2). in_layer(0,n1). in_layer(0,n2). width(1, 1). in_layer(1,n3). }}} defines two layers, layer 0 containing nodes {n1, n2} and layer 1 containing {n3}. The predicate edge/2 defines edges between nodes. For example {{{ edge(n1,n3). edge(n2,n3). }}} == Output format == A solution to the problem is an assignment of each node to a position in its layer, which minimizes the number of crossings in the graph. This is given by the position/2 predicate, where {{{position(n,3)}}} assigns node 'n' to the third position in its layer. Positions at a layer L are numbered from 1 until the width of L. == Example(s) == Input: {{{ layers(2). width(0, 2). in_layer(0,n1). in_layer(0,n2). width(1, 1). in_layer(1,n3). edge(n1,n3). edge(n2,n3). }}} Possible output: {{{ position(n1,1). position(n2,2). position(n3,1). }}} Additional sample instances: [[https://www.mat.unical.it/aspcomp2013/files/samples/crossing_minimization-sample.zip|download]] == Problem Peculiarities == '''Type''': Optimization '''Competition''': Both This problem is considered quite hard in practice, and is usually approached using ad-hoc heuristics. The instance family is based on graphs taken from the graphviz website and randomly generated layered graphs of known optimal value. The outcomes of this benchmark will give a clear idea of the gap-width of declarative technologies in this respect. == Notes and updates == == Author(s) == * Author: Carmine Dodaro * Affiliation: University of Calabria, Italy * Original Authors: Peter Stuckey, Graeme Gange * Affiliation: University of Melbourne, Australia