O Conceito do Layout de Gráfico

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ício
    O algoritmo de layout é totalmente refeito ("a partir do início") sempre que o gráfico é alterado.
  • Layout incremental
    Quando 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.