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

王銳 徐捷

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

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

王銳1徐捷2

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

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

JUNG framework；MongoDB database；networkgraph generation technology；visualization

1、引言

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1、一般網(wǎng)絡圖設計需求分析

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

1)可以實現(xiàn)領域擴展；

2)可以實現(xiàn)人機交互；

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

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

5)對網(wǎng)絡圖進行計算，諸如最大流、最小費用等。

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

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

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

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

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

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

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

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

JUNG有4個基礎類是編程重點：Graph、Layout、Renderer和VisualizationViewer。要建立網(wǎng)絡關系圖編程，則需求建立一個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)絡圖的最基本方法，其功能是繪制出頂點和邊，其效果如圖3所示。圖3是在上面代碼基礎上加入了鼠標監(jiān)聽、用戶交換等功能。

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

網(wǎng)絡圖的生成需要大量數(shù)據(jù)的交互和存儲，為此，本文研究設計的網(wǎng)絡圖生成技術(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ù)庫進行維護，即查詢、刪除和插入等操作。

4.3、結(jié)果展示

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

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

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

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

該圖按照給定的矩陣進行繪制,并計算出相應邊的距離,運算后得出的結(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)絡圖生成系統(tǒng)的特性和可擴展性,結(jié)合的節(jié)點計算、權(quán)值估計等算法也運行良好。

5、結(jié)束語

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

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

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

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

[4]張先迪, 李正良. 圖論及其應用[M].北京:高等教育出版設.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-），男，山東郯城人，學員，從事基于文本數(shù)據(jù)庫的社會網(wǎng)絡分析法研究。

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