電腦科學與資訊工程科Computer Science & Information Engineering190006
圖論演算法學習用之繪圖程式 Taiwan
本研究針對學習圖論演算法的需求,設計一套使用者友善的繪圖軟體Graphene。Graphene繪圖程式除了提供高可讀性的繪製結果,作為輔助繪圖的工具外,也可直接輸入競賽題目的文字格式測試資料產生繪圖結果,並結合現有繪圖演算法,改善、優化樹與類樹圖的繪製結果。此外,也加入時間軸、自訂外觀、參數調整、匯出圖片等功能,幫助學習者理解圖論演算法,亦可幫助教師製作教材,有助於圖論演算法教學。 Graphene採用的繪圖演算法以force-directed graph drawing演算法為基礎,實作節點的分布。然而初始的節點分布會影響繪圖結果,因此我們利用biconnected component、block-cut tree等圖論結構對圖的繪製進行優化。首先找出圖的biconnected component及關節點,重新定義block-cut tree裡的block,接著利用radial tree的布局方式配置每個block,再套用force-directed graph drawing演算法,得到最後的布局結果。如此可以減少不同block之間的交錯,得到較佳的結果。