Seminar 08
講師: 顏嗣鈞
主題: Algorithmic Issues in
Graph Drawing
日期: 11/11/2003
作者: 林翰儂
學號: 89703008
心得:
這次的主題是說明Graph Drawing(以下簡稱GD)演算法的探討與簡介.一開始教授對我們說明了GD的目的為何?GD可以對於我們不論在學界或業界有著什麼樣的幫助?
GD的主要應用之一是為了要畫出讓人能容易理解的動作流程,目前我們最常接觸到的應用就是在制定工作流程表或是物件之間繼承,衍生,包含…等等的關係.如果只是單單的利用文字表格與敘述一一列出,其實對於不了解內部運作的人有相當大的困擾,例如客戶,老闆,老師以及不參與計畫的同伴這些你需要去向他們解釋自己到底在做什麼,進度到多少了的人.
以下圖為例
這是一個系統發展的流程,我們可以看得到下面一排的processes有loop的特徵,如果可以利用GD的技巧可以很容易的就看的出來這件事情想表達的意義.
所以接下來我們要了解如何才能畫出一個好圖?還有哪些方法可以畫圖來表達不同的重點?也就是這次議題的重點.以樹狀圖為例要讓人能輕易的理解整個圖要表達的意義,除了圖的link之間不要有重疊的發生也要兼顧平衡的概念(near symmetry),之後講師說了一個The Sugiyama Method是一種把link交錯減到最低的一種方法,不過在複雜度上還是NP-problem.其實要畫出圖其實並不困難,但是在簡化圖形的最佳化的演算法目前還是有相當高的複雜度.
最後我想探討一下比較感興趣的floor-planning演算法.他是說可以將樹狀的關係畫成像是馬賽克地板的樣子,如下
比如說node 1與node 2,3,6,7,12有關聯,就把方塊1和方塊2,3,6,7,12畫成鄰近的關係.在查詢資料我之前一直以為我們要先做出地板的樣式(像是T型L型的地板,如地板3,5)才能對應樹狀關係圖拼貼.但是其實方法剛好相反.
做法就是先將root(node 1)畫出再找出誰是它的child nodes以及child nodes之間的link關係,將其放到對應的方塊1下方,以此類推可以得到下圖(先由上方的樹狀圖的粗線為準畫出下圖)
再把node兩兩對照畫出下列之圖形
最後再把圖f的鋸齒狀邊緣填滿
就可以得到地板狀的圖了.如果想知道詳細的演算法請見註解.
這次的議題相當有趣且實用,我們可以從這裡了解到一般我們看似簡單又直覺的圖,其實仍然要靠著嚴謹的演算法與規則才能得到證實,複雜的敘述可以利用簡單的圖形解釋.雖然有些講師提過的概念由於時間上的限制並沒有比較詳細的解釋,不過仍然可以由他所提過的幾個名詞在網路上找到大概的解釋.我個人十分希望往後能有類似的議題可以繼續探討這個領域的問題.
