# 成發講稿 ## 開始 — 研究方法 【BEGIN】 大家好，我們的主題是圖論演算法學習用之繪圖程式。 【下一頁】 首先介紹什麼是演算法競賽。 舉個例子，「請計算 1 的平方到 10 的平方和是多少？」 這個問題是在數學競賽中會出現的。 然而，在演算法競賽中，類似的問題可能會變成如右： 「輸入一個正整數 N，請輸出 1 的平方到 N 的平方和。N 小於等於十萬。」 【下一頁】 同樣都是運用思維解決問題， 但問題的敘述、題目著重的考點卻有很大的差別。 在演算法競賽中，題目給的是任意的輸入， 並要求參賽者針對問題設計一套解題方法， 使得對於一定範圍內的輸入皆能算出答案。 而參賽者要將該方法利用電腦撰寫成一支程式並上傳。 【下一頁】 我們最初的研究想法便是來自於演算法競賽， 在競賽中，和圖論演算法相關的題目數見不鮮， 尤其以樹或類似樹的圖有關的題目居多。 而練習這些題目時，為了尋找解題靈感，常常需將測試資料手繪出來。 然而，測試資料大都只是描述節點間關係的文字。 例如 2 號點連接到 5 號點，便以「2 5」表示。 然而畫出來之後，不太可能一次就精準到位， 還得進行多次校正、旋轉、重繪，很不方便。 而繪圖工具，便是能夠解決這個問題的工具。 手動拖曳節點、邊之後，就能自動調整、生成一張圖， 對於演算法競賽選手來說，是相當方便的工具。 【下一頁】 除此之外，近年來資訊教育逐漸盛行、發展， 演算法的學習越來越受到重視， 甚至已經被納入新課綱的必修範圍內。 而學習圖論演算法時，常常需以視覺化圖像幫助學習， 教學者設計演算法教材時，也須加上適當的插圖輔助說明。 【下一頁】 因此，若有一項工具，能將圖清楚、完整的呈現， 讓使用者方便操作，甚至可以搭配演算法步驟呈現動畫， 對學習者或教學者來說，這會是一套非常方便的工具。 【下一頁】 現有的繪圖程式有諸多缺點， 像是功能不完整、對使用者不夠友善，或是沒有自動優化繪製結果的功能。 【下一頁】 因此，我們的研究目的，便是想辦法改善這些問題。 首先是優化圖的繪製結果， 利用現有的繪圖演算法，結合一些圖論結構進行優化， 其中以類樹圖的優化為主軸。 接著是進行測試，找出能使繪製結果最清晰的參數組合。 再來也是本次研究的重點目標， 我們打算設計易於操作的使用者介面， 目標用戶鎖定演算法競賽選手，以及演算法的學習者和教學者， 除了功能的優化外，還加入幫助學習演算法、撰寫程式以及除錯的工具， 提供使用者自定義選項，如調整參數和繪製位置、匯出圖片與外觀樣式。 讓使用者有更彈性操作空間。 【下一頁】 研究時使用的設備，硬體只需要電腦。 【下一頁】 而軟體部分，程式語言使用 C++。 IDE 使用 CLion 開發用的 GUI 則使用 Dear ImGui， 版本控制器則使用 Git。 【下一頁】 研究方法，首先要介紹一些背景知識。 一，Force-directed Drawing 演算法 將節點視為電子，互相有斥力，邊視為彈簧，提供引力將節點往回拉。 以力學的方式決定節點的位置。 二、圖上若有節點，其被拔除後會使圖不連通，則稱該點為關節點。 若一張圖不存在關節點，稱其為 Biconnected Graph。 三、一張圖的某個導出子圖，若滿足 (a) 其為 Biconnected Graph， (b) 加入其他節點便不滿足條件 (a)， 則稱該子圖為 Biconnected Component。 四、Tarjan 演算法， 此算法能夠在線性時間複雜度內找出關節點和分割出 Biconnected Component。 五、執行 Tarjan 演算法後，根據 Biconnected Component 和關節點， 將原圖轉換成一棵樹，稱此樹為該圖的 Block-cut Tree。 【下一頁】 我們為這項專案取了個名字，Graphene。 【下一頁】 而 Graphene 的架構主要分成兩大類，Graphene 和 GUI。 Graphene 處理圖的所有運算，GUI 則負責渲染以及使用者互動。 【下一頁】 Graphene 又可分成四項架構。 Core 負責節點位置運算，是演算法核心區。 Graph 維護圖的結構。 Connected Component 維護圖的連通塊。 而最後一項則是維護每個連通塊形成的 Block-cut Tree。 【下一頁】 GUI 可分成四項架構。 這部分將於後面的研究結果做說明。 【下一頁】 接下來是本次研究的重點，設計節點的布局，決定其位置的方法。 概要如下： 首先，我們先決定每個 Biconnected Component 當中每個節點的相對位置。 接著決定每個 Connected Component 當中 Biconnected Component 的相對位置。 最終決定不同 Connected Component 的分布。 【下一頁】 首先是 Biconnected Component 內部的佈局。 這部分較單純，直接使用 Force-directed Drawing Algorithm 決定節點的相對位置即可。 而經過測試，由 Eades 提出的力函數有相當不錯的表現。 【下一頁】 接著是 Connected Component 內部的佈局。 這部分我們尚未完成，以下將介紹我們的構思。 參考右圖，紅色點為關節點，黃色框為 Biconnected Component。 由前述背景知識可知，Block-cut Tree 將圖分成許多區塊，如棕色區域標示， 而每個區塊在 Block-cut Tree 上都對應到一個節點。 因此我們以 Block-cut Tree 為主軸， 使用常見畫樹的演算法 — Radial Tree Layout 決定每個區塊的分佈， 中心點為 Block-cut Tree 的重心， 而同樣深度的區塊則分佈於同個橢圓軌道。 【下一頁】 最後是不同 Connected Component 的分佈。 再次使用 Force-directed Drawing Algorithm 的概念， 計算每對不同 Connected Component 的點之間的斥力， 並加總到各自的 Connected Component， 最後每個 Connected Component 根據合力移動。 然而這樣有個問題，每個 Connected Component 之間的距離會越來越遠。 因此我們想出了解決方法， 【下一頁】 那就是賦予每個 Connected Component 一個指向原點的力， 力與質心到原點的距離、節點數量成正比。 【下一頁】 而上述方法的運行結果如下： 《停留 2 秒》 【END】 ## 未來展望 — 結束 【BEGIN】 綜合以上所述，我們將尚未完成的工作與未來目標進行了統整。 首先是完成繪圖程式的優化， 包含實踐 Radial Tree Layout Algorithm、 進行 Angular Resolution 的優化 （避免邊之間的夾角過小）、 以及程式效率的優化。 接著是完善基本功能， 包含支援重邊、自環的繪製， 能在邊上顯示權重，以及將節點、邊標上醒目強調的功能。 再來是加上演算法學習用的功能， 例如演算法逐格動畫、時間軸功能、 提供教學者設計演算法教材的功能，和支援圖片輸出。 而我們的終極目標，是將這支繪圖程式公開發表，向外宣傳、推廣。 不管是程式競賽選手或是學習、教授演算法的人，都能受惠於這支工具。 【下一頁】 以下是我們進行研究時所參考的資料。 【下一頁】 我們的報告到此結束， 有任何問題歡迎於 QA 時間提出。 謝謝大家的聆聽。