|
Size: 2051
Comment:
|
← Revision 14 as of 2011-02-02 17:34:40 ⇥
Size: 2813
Comment: Mi ha cancellato la pagina!
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 5: | Line 5: |
| == 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. |
|
| Line 7: | Line 18: |
| * '''Input''': layers/1, width/2, in_layer/2, edge/2 | * '''Input''': {{{layers/1, width/2, in_layer/2, edge/2}}} |
| Line 9: | Line 20: |
| * '''Output''': position/2 == Problem Description == The standard approach for drawing hierarchical network diagrams is a three phase approach in which (a) nodes in the graph are assigned levels producing a k-level graph; (b) nodes are assigned an order so as to minimize edge crossings in the k-level graph; and (c) the edge routes and node positions are computed. There has been considerable research into step (b) which is ccalled 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. |
* '''Output''': {{{position/2}}} |
| Line 18: | Line 24: |
| 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 | 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 |
| Line 20: | Line 26: |
| layers(2). width(0, 2). in_layer(0,n1). in_layer(0,n2). width(1, 1). in_layer(1,n3). | {{{layers(2). width(0, 2). in_layer(0,n1). in_layer(0,n2). width(1, 1). in_layer(1,n3).}}} |
| Line 26: | Line 32: |
| edge(n1,n3). edge(n2,n3). | {{{edge(n1,n3). edge(n2,n3).}}} |
| Line 30: | Line 36: |
| 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. | 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. == 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).}}} == Problem Peculiarities == '''Type''': Optimization '''Competition''': Model & Solve only 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. |
Crossing minimization in layered graphs
Contents
Problem Description
The standard approach for drawing hierarchical network diagrams is a three phase approach in which
nodes in the graph are assigned levels producing a k-level graph;
nodes are assigned an order so as to minimize edge crossings in the k-level graph; and
- 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.
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.
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).
Problem Peculiarities
Type: Optimization Competition: Model & Solve only
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.
Author(s)
- Author: Peter Stuckey
- Affiliation: University of Melbourne, Australia
- Author: Graeme Gange
- Affiliation: University of Melbourne, Australia