圖布局算法綜述

《圖布局算法綜述》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、OVERVIEWOFALGORITHMSFORGRAPHDRAWING圖布局算法綜述BostjanPajntarDepartmentofKnowledgeTechnologiesJozefStefanInstituteJamova39,1000Ljubljana,Slovenia（南斯拉夫）Tel:+38614773128E-mail:bostjan.pajntar@ijs.si摘要本文綜述若干種圖可視化算法，并詳細描述了最常用的幾個算法。本文的首要目的是幫助讀者選擇合適的算法去可視化關(guān)系數(shù)據(jù)。另一方面，也可以當作對圖布局算法及其發(fā)展的歷史回顧

2、1概要從前，信息只是一種commodity（?商品，不足大量）。然而隨著互聯(lián)網(wǎng)的發(fā)展，大規(guī)模的數(shù)據(jù)變得隨處可見。問題從獲取信息，變?yōu)槌槿∑渲械挠杏帽断?。使用統(tǒng)計分析與數(shù)據(jù)挖掘，我們能夠抽取所需的信息。但是，由于顯示是平面的，大部分這些數(shù)據(jù)挖掘的結(jié)杲難以為人們所閱讀，由此就產(chǎn)牛-了對可視化的需求。因為一張圖畫常常可以蘊含一篇文章（的信息），對任何關(guān)系數(shù)據(jù)的描繪成為了一種非常常用的表示已獲信息的途徑。2關(guān)于圖圖論中的定義在不同文獻中有所不同。針對我們的需求，圖G的一個寬松的定義是一個三元組（V,E,X）-頂點集V?邊集E?函數(shù)兒映射每條邊的端點到一

3、個頂點一個循環(huán)是一條兩端指向相同頂點的邊。一條多重邊表示兩個頂點同時關(guān)聯(lián)多條邊（圖1）。一個沒冇循環(huán)和多重邊的圖稱為簡單圖。如果邊是冇向的，則圖為冇向圖（digraph）。Figure1:Graphwithoneloopandonemulti3圖的大?。╯ize,規(guī)模）關(guān)于圖的大小并沒有專門的術(shù)語。圖的大小常常被定義為頂點的數(shù)冃，這并非是一個最好的定義。由于計算機運行速度L1益增長，圖的大小會隨著時間而改變（譯者注：喑示圖的大小跟計算機運行速度應(yīng)該聯(lián)系起來）。也許一種更好的定義就是將圖的大小和計算復(fù)雜度（譯者注：以下可以理解為單位時間計算機可處

4、理的頂點數(shù)n）聯(lián)合起來。我們把圖劃分為小、中、大（large）、超大（huge）。?對于小圖，基木上可以使用任何算法。冃前這種圖的規(guī)模為n10（最大為150個頂點）-中圖可以被多項式時間復(fù)雜度的算法所繪制。這種圖的規(guī)模也是足夠小，以被繪制在常用的屏幕上，其數(shù)量為n100o?大圖不能被直接地繪制（由于屏幕象索不足）。然而，這種圖仍然足以存放在內(nèi)存中。■更大的圖就稱為超大圖（內(nèi)存都放不下整個圖的數(shù)據(jù)）同時，我們也按稠密程序把圖分為［5］：-稀疏：Ev=V（譯者注：劃為理由可能是根據(jù)樹的性質(zhì)E=V-1）?一般：V3V（譯者注：

5、劃為理由可能是根據(jù)平面圖的充分條件E>=3V-6）這種命名法認為樹是稀疏的，而四方體和多面體則為一般圖。4圖的嵌入（Embbeding,譯者注：可認為是平面化planarization）圖可視化的質(zhì)量誠然是一種主觀判斷。它依賴于圖，以及我們希望從中獲取的信息。目前，關(guān)于人們?nèi)绾螐膱D屮閱讀信息的研究比較少［7］,大多數(shù)準則是直觀的選擇出來的。首要的指導(dǎo)思想是：用戶必須能夠從圖中獲取他所感興趣的信息，而口越簡單越好。以下是關(guān)于好的圖繪制的準則：■頂點必須均勻地分布在屏幕?邊交叉必須只有少量?邊長度必須均勻?圖結(jié)構(gòu)中的對稱性必須表現(xiàn)出來-圖必須被包含

6、在一，個畫面中（原文為:Grafshouldbeboundinsideaframe,譯文可能有誤）這些準則常常描述了我們的需求。然而，也有例外。?平面繪制可能有更好的結(jié)果，如果邊具有不同的長度（圖3,4）。?對于大圖，頂點必須被聚類；一種可視化的方法是所有同類的頂點被繪制為一點。?對于十分稠密的圖，対邊進行合并具有一定的意義。利用這個方法，可能將非平血圖進行平面繪制。（以下是按次方法對一個96個頂點的完全圖的繪制）Figure2:Fullgraphon96nodesindeleconfluemdraw力送.5算法可視化圖具有許多種方法。常用的對

7、簡單無向圖的方法是物理類比的（譯者注：將圖類比為一定的物理模型，如具有引力斥力的彈簧和粒子）。然而，如果圖具有其他的特征，我們可以使用其他的方法。5.1對于具有附加屬性的圖的算法5.1.1正交風(fēng)格圖可以被繪制在正交柵格上。這種方法常常用于有向圖，如我們所見的圖表（diagram）。每條邊都可以曲折，但每部分都必須是水平或者垂直。由此每個邊交叉都是正交的。這樣有利于對圖的閱讀。5.1.2Sugiyama風(fēng)格圖布局的--種好方法是層次化布局。對于DAG（有向無循環(huán)圖），我們可以根據(jù)拓撲順序?qū)D進行層次化。接著我們就可以得到一個流程圖，其所有邊都指向

8、同個方向。例如，有一條從A指向B的邊，A就在B的上方或左方。這種方法的一個優(yōu)點是所有圖都可以轉(zhuǎn)換為DAG。Sugiyama提出了一個很好的算法［11］