基因演算法於繪製有向分層布置圖之應用

Layered Layouts of Directed Graphs Using a Genetic Algorithm

林奕廷(Yi-Ting Lin)

指導教授 ： 顏嗣鈞

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2009年)

https://doi.org/10.6342/NTU.2009.01477

摘要

有向圖之圖形製圖在生活中有相當多的應用，本研究主要針對「分層布置圖」作探討。分層布置圖概略來說，是將點分布在不同的「層」上，且盡可能使所有的邊均往下指的一種製圖結構。透過這種圖，希望可讓使用者能更輕易的了解各點之間的層次關係。
分層布置圖的繪製主要以Sugiyama於1981年所提出的演算法為最傳統、經典的方式。其演算法主要將此問題分為四個步驟：迴圈去除、點層級的配置、邊交叉去除、點水平位置微調。這四個步驟，分別針對單一個美學項目作佳佳化的處理，其中有三步為NP-困難問題。因此，也有許多研究在各個步驟上。
然而，這四個步驟所處理的問題，並非相互獨立的，甚至是相互矛盾的。四個問題同時要為最佳解便無法定義，意即無法同時取得最佳解。在這種情況下，這些美學指標彼此之間的取捨變成了一個重要的課題。但在傳統方法中，四個問題為相互獨立解決，這些問題之間的比重便無法取捨，造成結果不符合人眼美學準則的情況。
在調整各項準則比重的觀點下，我們提出了一基因演算法，將傳統方法前三個步驟的問題一同考慮，希望做出更符合人眼美學準則的結果。

關鍵字

分層布置圖 ； 圖形製圖 ； 基因演算法 ； 有向圖

並列摘要

Drawings of directed graphs have many applications on many different media in our daily lives. This thesis focuses on layered layouts of directed graphs. In brief, a layered layout is a topology in which nodes are distributed over several layers and all edges are directed downward as much as possible. In this layout, people could easily understand the layered relation between nodes.
The classical technique of drawing layered layouts was proposed by Sugiyama in 1981. This technique involves four steps: cycle removal, layer assignment, crossing reduction, and x-coordinate assignment. Optimization issues associated with the first three steps under this framework are NP-hard. As a result, heuristic approximation algorithms have been proposed in the literature for the first three steps of Sugiyama’s algorithm.
It is important to note that the four problems which are solved by the four steps are not independent, in the sense that in respective aesthetic criteria may contradict each other. For this reason, it is impossible to define what the optimum of all aesthetic criteria is. In other words, it is impossible to achieve an optimal solution for all aesthetic criteria at the same time. Hence, the choice for each criterion becomes a very important problem. On the other hand, even if each step could get the optimal solution, these optimal solutions not necessarily correspond to the optimal solution of the entire layered layout problem.
To overcome the problem we mentioned above, we propose a genetic algorithm to model the first three steps of the Sugiyama’s algorithm, in hope of simultaneously considering these three aesthetic criteria. Moreover, the designed genetic algorithm allows us to adjust the weight ratio of each criterion in order to satisfy human aesthetic viewpoints.
According to the result of our experiment, our genetic algorithm could effectively adjust the ratio between edge crossing number and total edge length. This algorithm could make layered layout more satisfy human aesthetic viewpoint.

並列關鍵字

layered layout ； hierarchical graphs ； multi-level graphs ； graph drawing ； directed graphs ； genetic algorithm

參考文獻

1. H. Nagamochi and N. Yamada, "Counting edge crossings in a 2-layered drawing". Information Processing Letters, 2004. 91: pp. 221-225.

2. K. Sugiyama, S. Tagawa, and M. Toda, "Methods for visual understanding of hierarchical system structures". IEEE Transitions on Systems, Man, and Cybernetics, 1981. 11(2): pp. 109-125.

3. P. Eades and N. Wormland, "Edge crossings in drawings of bipartite graphs", in Algorithmica. 1994, Springer New York. pp. 379-403.

4. P. Kuntz, B. Pinaud, and R. Lehn, "Minimizing crossings in hierarchical digraphs with a hybridized genetic algorithm". Journal of Heuristics, 2006. 12(1-2): pp. 23-36.

8. E. Mäkinen and M. Sieranta, "Genetic algorithms for drawing bipartite graphs", in International J. Computer Mathematics. 1994. pp. 157-166.