Algoritmo de Sugiyama-

GRAFOS
Artigo: “Methods for visual understanding of
hierarchical system structures”
K. Sugiyama, S. Tagawa, M. Toda. Methods for visual undestanding of
hierarchical
system
structures. IEEE Trans. Syst. Man Cybern., Grafos
pp. 109-125,
MARCO
ANTONIO GARCIA
DE CARVALHO
e Aplicações
Março
de
2010
1981.
Motivation
This paper is intended to present methods to generate a visually understandable drawing
of a hierarchy automatically by a computer.
computer.
MARCO ANTONIO GARCIA DE CARVALHO
Março de 2010
Grafos e Aplicações
Motivation
The rows and columns of a graph
matrix
representation
can
be
permuted, allowing different views
of the data set.
(# of rows)! x (# of columns) !
The user has a chance to detect
patterns in the new presentation and
to gain insight into the data.
E. Makinen, H. Siirtola. Reordering the reoderable matrix as an algorithmic
problem.
In:GARCIA
Proc.DEOf
the First International Conference on Theory Grafos
and e Aplicações
MARCO ANTONIO
CARVALHO
Março de 2010
Application of Diagrams, pp. 453-467, 2000.
Schematic diagrams
MARCO ANTONIO GARCIA DE CARVALHO
Março de 2010
Grafos e Aplicações
(P1) Definition of a Hierarchy: A hierarchy is defined by terms of graph theory.
(P2) Identification of Readability Elements: In the case of hierarchies, the former, regular
layout of vertices, is identfied as the following readability element:
Element A: “Hierarchical” layout of vertices;
Element B: “Less-Crossings” of lines (edges);
Element C: “Straightness” of lines;
Element D: “Close” layout of vertices connected to each other.
Element E: “Balanced” layout of lines coming into or going from a vertex.
(P3) Specification of Basic Rules of Drawing: In order to draw a hierarchy, we should
determine a layout of vertices and how to draw edges. We specify the basic rules regarding
these aspects as follows:
Rule a) Vertices are placed on horizontal lines in each level of the hierarchy
without overlapping;
Rule b) Each edge is drawn with a straight line.
MARCO ANTONIO GARCIA DE CARVALHO
Março de 2010
Grafos e Aplicações
(P4) Formulation as a Multstage Multiobjective Problem: The whole algorithm
developed includes four step.
Step I: A “proper” hierarchy is formed from a given set of directed pairwise relations
among elements of a system.
Step II: The number of crossings of edges in the proper hierarchy is reduced by
permuting orders of vertices in each level.
Step III: Horizontal positions of vertices are determined. The orders of the vertices in
Step II is given as constraints to preserve the reduced number of crossings.
Step IV: A picture of the hierarchy is automatically drawn.
(P5) Theorical and Heuristcs Aproaches: We have focus on heuristhic methods.
Therefore, we developed to Step II a method called Barycentric (BC) and to Step III we
have been developed the priority (PR) layout method where the computing cost is
MARCO ANTONIO GARCIA DE CARVALHO
Grafos e Aplicações
significatly
Março
de 2010 lower.
Basic definitions
MARCO ANTONIO GARCIA DE CARVALHO
Março de 2010
Grafos e Aplicações
Basic definitions
MARCO ANTONIO GARCIA DE CARVALHO
Março de 2010
Grafos e Aplicações
Numerical example
Original graph
Matrix realization
Barycentric Method
We consider a heuristic method for the reordering of the row order σ1 to reduce the
number of crossings under the fixed column order σ2 in M(σ1, σ2).
The essential idea of this method is to reorder σ1 according to the row barycenters
calculated by (9)
We can reduce the number of crossings by repeating the barycentric ordering of rows
and column in turn.
MARCO ANTONIO GARCIA DE CARVALHO
Março de 2010
Grafos e Aplicações