Um gráfico é uma estrutura de dados que representa um
conjunto de entidades, nós chamados, conectada por um conjunto de links. Um nó também pode ser referido como um vértice. Um link também pode ser
referido como uma borda ou uma conexão. In practical applications, graphs are frequently
used to model a wide range of things: computer networks, software
program structures, project management diagrams, and so on. Gráficos são modelos
eficientes, porque permitem que aplicativos se beneficiem dos resultados
da pesquisa de teoria de gráfico. Por exemplo, métodos eficientes estão
disponíveis para localizar o caminho mais curto entre dois nós, o caminho
de custo mínimo e outros.
Layout de um Gráfico
O layout de gráfico é usado em interfaces gráficas com o
usuário de aplicativos que precisam exibir modelos de gráfico. Organizar
um gráfico significa desenhar o gráfico para que seja produzida uma
representação legível apropriada. Essentially, it involves determining the location of
the nodes and the shape of the links. For some applications, the location
of the nodes is already be known (for example, based on the geographical
positions of the nodes). Para outros aplicativos, o local não é conhecido (um gráfico
"lógico" puro) ou o local conhecido, se usado, produziria um desenho
ilegível do gráfico. Nestes casos, o local dos nós deve ser calculado.
O que significa um desenho "apropriado" de um gráfico? Em
aplicativos práticos, geralmente é necessário para o desenho do gráfico
observar alguns critérios de qualidade. These criteria
can vary depending on the application field or on a given standard
of representation. Geralmente é difícil dizer no que consiste um bom layout. Each user can have different, subjective criteria for
qualifying a layout as “good”. No entanto, existe um objetivo comum atrás de todos os
critérios e padrões: o desenho deve ser fácil de entender e fornecer uma
navegação fácil por meio da estrutura complexa do gráfico.
O que É um Bom Layout?
Para lidar com as diversas necessidades de diferentes
aplicativos foram desenvolvidas muitas classes de algoritmos de layout de
gráfico. Um algoritmo de layout aborda um ou mais critérios de qualidade,
dependendo do tipo de gráfico e dos recursos do algoritmo, ao organizar um
gráfico.
Os critérios mais comuns são:
- Minimizing the number of link crossings
- Minimização da área total do desenho
- Minimização do número de curvaturas (em desenhos ortogonais)
- Maximização do menor ângulo formado por links incidentes consecutivos
- Maximização da exibição de simetrias
Um um algoritmo de layout pode atender a cada um destes
critérios de qualidade e padrões de representação? If you look at each individual
criteria, some can be met easily, at least for some classes of graphs.
For other classes, it might be difficult to produce a drawing that
meets the criteria. Por exemplo,
minimizar o número de cruzamentos de links é relativamente simples para
árvores (ou seja, gráficos sem ciclos). For
general graphs, minimizing the number of link crossings is a mathematical NP-complete problem (that is, with all known algorithms,
the time required to perform the layout grows fast with the size of
the graph).
If you want to meet several criteria at the same time,
an optimal solution might not exist for each one individually, because
many of the criteria are mutually contradictory. Time-consuming trade-offs
might be necessary. Além disso, não é uma tarefa trivial designar
pesos a cada um dos critérios. Multicriteria optimization is, in most cases,
too complex to implement, and much too time-consuming. For these reasons,
layout algorithms are often based on heuristics and might provide
less than optimal solutions with respect to one or more of the criteria.
Felizmente, em termos práticos, os algoritmos de layout geralmente ainda
fornecem desenhos razoavelmente legíveis.
Métodos para Usar Algoritmos de Layout
Layout algorithms can be employed in various ways in
the various applications in which they are used. As maneiras
mais comuns de usar um algoritmo são:
-
O algoritmo de layout faz tudo sem nenhuma intervenção do usuário, exceto talvez pela opção do algoritmo de layout a ser usado. Às vezes, um conjunto ou regras podem ser codificadas para escolher automaticamente (e dinamicamente) o algoritmo de layout mais apropriado para o tipo específico de gráfico a ser organizado.
-
O usuário do aplicativo é livre para melhorar o resultado do procedimento de layout automático manualmente. In some cases, this user can move and “pin” nodes at wanted locations and perform the layout again. Em outros casos, uma parte do gráfico é automaticamente configurada como "somente leitura" e o usuário pode modificar o restante do layout.
- Layout a partir do inícioO algoritmo de layout é totalmente refeito ("a partir do início") sempre que o gráfico é alterado.
- Layout incrementalQuando o algoritmo de layout é executado uma segunda vez em um gráfico modificado, ele tenta preservar a estabilidade do layout o máximo possível. O layout não é executado novamente a partir do início. O algoritmo de layout também tenta economizar tempo de CPU usando o layout anterior como uma solução inicial. Alguns algoritmos de layout e estilos de layout são incrementais por natureza. For others, incremental layout might be impossible.