王銳 徐捷

1.國防科技大學(xué)電子科學(xué)與工程學(xué)院，湖南 長沙 410073；2.國防科技大學(xué)信息工程研究所，湖南 長沙 410073

基于JUNG框架和MongoDB的網(wǎng)絡(luò)圖生成技術(shù)

王銳1徐捷2

1.國防科技大學(xué)電子科學(xué)與工程學(xué)院，湖南 長沙 410073；2.國防科技大學(xué)信息工程研究所，湖南 長沙 410073

由于在實(shí)際應(yīng)用中海量、異構(gòu)數(shù)據(jù)大量出現(xiàn)，以及基于Web架構(gòu)的廣泛采用，傳統(tǒng)關(guān)系數(shù)據(jù)庫在數(shù)據(jù)管理及可視化方面已經(jīng)難以勝任。JUNG是基于Java語言的開源框架，可以方便地實(shí)現(xiàn)網(wǎng)絡(luò)圖生成，并與聚類、最短路和最大流等算法相結(jié)合。MongoDB是開源數(shù)據(jù)庫，提供了Java開發(fā)包。本文綜合利用兩者的特點(diǎn)研究了一種網(wǎng)絡(luò)圖生成技術(shù)。通過測試，該技術(shù)運(yùn)行快捷穩(wěn)定，可以生成相關(guān)領(lǐng)域的網(wǎng)絡(luò)圖，可用于商業(yè)、金融、軍事等多個(gè)領(lǐng)域的信息處理與可視化。

JUNG framework；MongoDB database；networkgraph generation technology；visualization

1、引言

隨著計(jì)算機(jī)科學(xué)和信息科學(xué)的推動(dòng)，圖論和網(wǎng)絡(luò)流理論已經(jīng)形成了一門既有趣又有用、既成熟又活躍的學(xué)科分支。并且其形成網(wǎng)絡(luò)圖在工程領(lǐng)域獲得廣泛的應(yīng)用，但隨著實(shí)際應(yīng)用中海量、異構(gòu)數(shù)據(jù)的大量出現(xiàn)，以及基于Web架構(gòu)的廣泛應(yīng)用，如何快捷地分布式管理數(shù)據(jù)并繪制網(wǎng)絡(luò)圖是現(xiàn)今研究人員所面臨的主要問題。針對網(wǎng)絡(luò)圖繪制近幾年來出現(xiàn)了很多有創(chuàng)意的開源框架。如JUNG、JFreeChart、JChar2D等等，都有其自身的特點(diǎn)。相對而言，JUNG框架在對圖形化支持和交互式數(shù)據(jù)訪問等方面更勝一籌[1]。而MongoDB是一個(gè)高性能，開源，無模式的基于分布式文檔存儲的數(shù)據(jù)庫，它不僅使用十分方便，而且數(shù)據(jù)被分組以BSON（鍵-值對）的形式存儲在數(shù)據(jù)集中，不需要任何Schema，可以將異構(gòu)數(shù)據(jù)存儲在同一個(gè)數(shù)據(jù)庫中，同時(shí)其每個(gè)數(shù)據(jù)集合中包括不同類型數(shù)據(jù)，具有很高的查詢速度[2]。因而在存在海量異構(gòu)數(shù)據(jù)且需要進(jìn)行分析并可視化的大型組織中，這兩者結(jié)合用于信息處理具有明顯優(yōu)勢，雖然目前很少有公開文獻(xiàn)對此方面進(jìn)行專門研究，但相信基于JUNG框架和MongoDB數(shù)據(jù)庫的應(yīng)用開發(fā)將會越來越多。

因此考慮到JUNG類庫框架的巨大圖形可視化功能，以及MongoDB數(shù)據(jù)庫數(shù)據(jù)處理的高效性，以及其對異構(gòu)數(shù)據(jù)的充分支持，本文采用JUNG作為網(wǎng)絡(luò)圖生成技術(shù)的低層框架，并采用MongoDB數(shù)據(jù)庫作為數(shù)據(jù)持久層，從而實(shí)現(xiàn)網(wǎng)絡(luò)圖生成技術(shù)的研究設(shè)計(jì)，并給出了開發(fā)實(shí)例，可用于商業(yè)、金融、軍事等多個(gè)鄰域的信息處理與可視化。

2、JUNG框架和MongoDB數(shù)據(jù)庫

2.1、JUNG框架簡介[1-3]

Jung（the Java Universal Network/Graph Framework）是一個(gè)開源軟件包，它提供了一種公共和可擴(kuò)展的框架來實(shí)現(xiàn)數(shù)據(jù)的建模、分析和可視化展示并能夠被繪制成圖形或網(wǎng)絡(luò)。其目的在于未開發(fā)關(guān)于圖或網(wǎng)絡(luò)結(jié)構(gòu)的應(yīng)用程序提供一個(gè)以用、通用的基礎(chǔ)架構(gòu)。使用Jung功能調(diào)用，可以方便的構(gòu)造圖或網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)，應(yīng)用經(jīng)典算法（如聚類、最短路徑、最大流量等），編寫和測試用戶自己的算法，以及可視化的顯示數(shù)據(jù)的網(wǎng)絡(luò)圖。

2.2、MongoDB數(shù)據(jù)庫[3-4]

Mongo是使用C++開發(fā)的，MongoDB數(shù)據(jù)庫具有面向集合的存儲、動(dòng)態(tài)查詢、完整的索引支持和查詢監(jiān)視等諸多鮮明的特征。根據(jù)官方網(wǎng)站的描述：MongoDB適用于一下場景：

（1）網(wǎng)站數(shù)據(jù)：Mongo非常適合實(shí)時(shí)的插入，更新于查詢，并具備網(wǎng)站試試數(shù)據(jù)存儲所需的復(fù)制及高度伸縮性。

（2）緩存：由于性能很高，Mongo也適合作為信息基礎(chǔ)設(shè)施的緩存層。在系統(tǒng)重啟之后，由Mongo搭建的持久化緩存層可以避免下層的數(shù)據(jù)源過載。

（3）大尺寸，低價(jià)值的數(shù)據(jù)：使用傳統(tǒng)關(guān)系型數(shù)據(jù)庫存儲一些數(shù)據(jù)時(shí)可能會比較昂貴，在此之前，很多時(shí)候程序員往往會選擇傳統(tǒng)的文件進(jìn)行存儲。

（4）高伸縮性的場景：Mongo非常適合由數(shù)十或數(shù)百臺服務(wù)器組成的數(shù)據(jù)庫。Mongo的路線圖中已經(jīng)包含對MapReduce引擎的內(nèi)置支持。

（5）用于對象及JSON數(shù)據(jù)的存儲：Mongo的BSON數(shù)據(jù)格式非常適合文檔化格式的存儲及查詢。

3、網(wǎng)絡(luò)圖生成技術(shù)研究

3.1、一般網(wǎng)絡(luò)圖設(shè)計(jì)需求分析

拋開領(lǐng)域知識，網(wǎng)絡(luò)圖都是由頂點(diǎn)和邊組成，頂點(diǎn)和邊之間的關(guān)系都可以通過一個(gè)唯一的鄰接矩陣來表示。本文要實(shí)現(xiàn)的技術(shù)的基本需求為：

1)可以實(shí)現(xiàn)領(lǐng)域擴(kuò)展；

2)可以實(shí)現(xiàn)人機(jī)交互；

3)可以對給定的臨界矩陣進(jìn)行繪制；

4)對繪制的網(wǎng)絡(luò)圖能夠?qū)崿F(xiàn)縮放和拖動(dòng)，以及修改；

5)對網(wǎng)絡(luò)圖進(jìn)行計(jì)算，諸如最大流、最小費(fèi)用等。

3.2、網(wǎng)絡(luò)圖技術(shù)組成

根據(jù)給出的需求分析，設(shè)計(jì)出一個(gè)通用的網(wǎng)絡(luò)圖生成技術(shù)系統(tǒng)，其組成框架及信息流的如圖1所示。

技術(shù)核心是JUNG框架提供的接口類庫。其中Layout、可視化以及Graph中的節(jié)點(diǎn)、邊的繪制都是有其提供。MongoDB在該技術(shù)系統(tǒng)中起到數(shù)據(jù)持久層的功用，同時(shí)也為用戶對網(wǎng)絡(luò)圖的修改和擴(kuò)展提供依據(jù)。

圖1 網(wǎng)絡(luò)圖技術(shù)組成及信息流動(dòng)

4、技術(shù)實(shí)現(xiàn)

4.1、JUNG編程實(shí)現(xiàn)

本文使用MyEclips7.0作為開發(fā)環(huán)境，采用JUNG2.0.1作為網(wǎng)絡(luò)圖開發(fā)低層庫。其中JUNG包可以在SourceForge下載。

JUNG包中包含所有需要的Jar文件，將其解壓到一個(gè)目錄中即可。在MyEclipse中在建立的工程所在的目錄下使用Configure Build Path 菜單命令激活“l(fā)ibrary”選項(xiàng)卡，然后使用“Add External JARS”按鈕將JUNG包中Jar文件全部設(shè)為系統(tǒng)類庫。這樣在工程中建立的網(wǎng)絡(luò)圖生成系統(tǒng)就可以訪問JUNG所提供的方法和數(shù)據(jù)了。

JUNG有4個(gè)基礎(chǔ)類是編程重點(diǎn)：Graph、Layout、Renderer和VisualizationViewer。要建立網(wǎng)絡(luò)關(guān)系圖編程，則需求建立一個(gè)Graph對象，然后建立Layout和Renderer對象，同Layout和Renderer對象創(chuàng)建VisualizationViewer對象。具體代碼片段如下：

SparseMultigraphg = new SparseMultigraph();

g.addVertex("1");

g.addVertex("2");

g.addVertex("3");

g.addEdge("Edge-A","1", "2");

g.addEdge("Edge-B", "2","3",EdgeType.DIRECTED);g.addEdge("Edge-C", "4", "5");System.out.println("The graph g = " + g.toString());

Layoutlayout =new CircleLayout(g);

BasicVisualizationServervv = new BasicVisualizationServer(layout);

this.getContentPane().add(vv);

this.pack(); this.setVisible(true);

……

上面給出了繪制網(wǎng)絡(luò)圖的最基本方法，其功能是繪制出頂點(diǎn)和邊，其效果如圖3所示。圖3是在上面代碼基礎(chǔ)上加入了鼠標(biāo)監(jiān)聽、用戶交換等功能。

4.2、MongoDB數(shù)據(jù)庫連接

網(wǎng)絡(luò)圖的生成需要大量數(shù)據(jù)的交互和存儲，為此，本文研究設(shè)計(jì)的網(wǎng)絡(luò)圖生成技術(shù)系統(tǒng)采用了MongoDB數(shù)據(jù)，下面給出的代碼是利用Java語言連接MongoDB的一種方式。

//Mongo對象

mongo = new Mongo();

//類似數(shù)據(jù)庫的選擇數(shù)據(jù)庫

db = mongo.getDB(dbName);

//類似選擇表

dbc = db.getCollection(collName);……

數(shù)據(jù)庫連接好后，在繪圖過程中需要對數(shù)據(jù)庫進(jìn)行維護(hù)，即查詢、刪除和插入等操作。

4.3、結(jié)果展示

圖2給出的是一個(gè)可以進(jìn)行編輯的網(wǎng)絡(luò)圖的繪制過程，首先可以通過鼠標(biāo)向圖板上（平面繪圖窗口）繪制網(wǎng)絡(luò)節(jié)點(diǎn)，然后將相關(guān)聯(lián)的節(jié)點(diǎn)連接，可以定義邊的方向。系統(tǒng)可以自動(dòng)給出邊的長度，對于這個(gè)長度可以根據(jù)實(shí)際問題進(jìn)行更改，或者調(diào)整頂點(diǎn)的位置改變邊長。系統(tǒng)是根據(jù)頂點(diǎn)間的距離作出的估算。頂點(diǎn)的信息和邊的信息被自動(dòng)存儲到MongoDB數(shù)據(jù)庫中。

圖2 手動(dòng)繪制網(wǎng)絡(luò)圖效果

下面給出的演示程序時(shí)根據(jù)鄰接矩陣定義網(wǎng)絡(luò)圖的結(jié)構(gòu)。鄰接矩陣如下：

圖3 繪制給定鄰接矩陣網(wǎng)絡(luò)圖

該圖按照給定的矩陣進(jìn)行繪制,并計(jì)算出相應(yīng)邊的距離,運(yùn)算后得出的結(jié)論如下所示:

Vertices:2,4,9,8,6,1,3,7,5,0

Edges:3[9,6] 7[6,3] 2[4,0] 0[2,5]17[0,7] 1[4,4] 6[8,0] 10[3,9] 5[8,9]13[5,8] 15[0,6] 9[1,5] 11[3,0] 4[8,2]8[1,2] 12[7,1]

The shortest unweighted path from 0 to 9 is:

[6, 5]

………

從而可以明確,該技術(shù)系統(tǒng)目前雖然比較簡單,但具有了一般網(wǎng)絡(luò)圖生成系統(tǒng)的特性和可擴(kuò)展性,結(jié)合的節(jié)點(diǎn)計(jì)算、權(quán)值估計(jì)等算法也運(yùn)行良好。

5、結(jié)束語

本文根據(jù)JUNG開源框架提供豐富的接口和數(shù)據(jù)以及MongoDB數(shù)據(jù)庫靈活的操作方式和動(dòng)態(tài)查詢模式，研究設(shè)計(jì)了網(wǎng)絡(luò)圖生成系統(tǒng)，不僅可以繪制用戶參與的網(wǎng)絡(luò)圖繪制也可以實(shí)現(xiàn)讀取鄰接矩陣進(jìn)行自動(dòng)繪制。這樣的網(wǎng)絡(luò)圖繪制技術(shù)系統(tǒng)可以應(yīng)用到多種工程和軍事仿真領(lǐng)域，通過同領(lǐng)域知識相結(jié)合可以產(chǎn)生更加復(fù)雜和多變的網(wǎng)絡(luò)圖系統(tǒng)。

[1]http://sourceforge.net/projects/jung/files/

[2]JUNG 官方網(wǎng)站, http://jung.sourceforge.net/applet/index.html.

[3]網(wǎng)樹禾. 圖論[M]. 北京：科學(xué)出版社.2004

[4]張先迪, 李正良. 圖論及其應(yīng)用[M].北京:高等教育出版設(shè).2005

Network-Graph Gerneration System Based on JUNG Framework and MongoDB

Wang Rui1XU Jie2
1. School of Electronic Science and Engineering, NUDT, Changsha 410073, China;2. Institute of Information Engineering, NUDT, Changsha 410073, China)

As the emergence of massdata, and the prevalence of web-based architecture, traditional relational database performs incompetently in database management and visualization. JUNG is an open framework based on Java, it could enable network graph easily, and combine the algorithms like classification, the shortest path algorithm and maxflow algorithm. MongoDB is a open source database,and provides Java package. A network-graph generation technology is designed in the paper that using both JUNG and MongoDB. The tests demonstrate the technology operates quickly and stably and could generate the network graphs, which coulddeal with the data processing and visualization in fields as commerce, finance and military.

10.3969/j.issn.1001-8972.2011.02.043

王銳（1983-），男，山東郯城人，學(xué)員，從事基于文本數(shù)據(jù)庫的社會網(wǎng)絡(luò)分析法研究。

JUNG框架；MongoDB數(shù)據(jù)庫；網(wǎng)絡(luò)圖生成技術(shù)；可視化