基于JUNG框架和MongoDB的網絡圖生成技術

王銳 徐捷

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

基于JUNG框架和MongoDB的網絡圖生成技術

王銳1徐捷2

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

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

JUNG framework；MongoDB database；networkgraph generation technology；visualization

1、引言

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

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

2、JUNG框架和MongoDB數據庫

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

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

2.2、MongoDB數據庫[3-4]

Mongo是使用C++開發的，MongoDB數據庫具有面向集合的存儲、動態查詢、完整的索引支持和查詢監視等諸多鮮明的特征。根據官方網站的描述：MongoDB適用于一下場景：

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

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

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

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

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

3、網絡圖生成技術研究

3.1、一般網絡圖設計需求分析

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

1)可以實現領域擴展；

2)可以實現人機交互；

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

4)對繪制的網絡圖能夠實現縮放和拖動，以及修改；

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

3.2、網絡圖技術組成

根據給出的需求分析，設計出一個通用的網絡圖生成技術系統，其組成框架及信息流的如圖1所示。

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

圖1 網絡圖技術組成及信息流動

4、技術實現

4.1、JUNG編程實現

本文使用MyEclips7.0作為開發環境，采用JUNG2.0.1作為網絡圖開發低層庫。其中JUNG包可以在SourceForge下載。

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

JUNG有4個基礎類是編程重點：Graph、Layout、Renderer和VisualizationViewer。要建立網絡關系圖編程，則需求建立一個Graph對象，然后建立Layout和Renderer對象，同Layout和Renderer對象創建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);

……

上面給出了繪制網絡圖的最基本方法，其功能是繪制出頂點和邊，其效果如圖3所示。圖3是在上面代碼基礎上加入了鼠標監聽、用戶交換等功能。

4.2、MongoDB數據庫連接

網絡圖的生成需要大量數據的交互和存儲，為此，本文研究設計的網絡圖生成技術系統采用了MongoDB數據，下面給出的代碼是利用Java語言連接MongoDB的一種方式。

//Mongo對象

mongo = new Mongo();

//類似數據庫的選擇數據庫

db = mongo.getDB(dbName);

//類似選擇表

dbc = db.getCollection(collName);……

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

4.3、結果展示

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

圖2 手動繪制網絡圖效果

下面給出的演示程序時根據鄰接矩陣定義網絡圖的結構。鄰接矩陣如下：

圖3 繪制給定鄰接矩陣網絡圖

該圖按照給定的矩陣進行繪制,并計算出相應邊的距離,運算后得出的結論如下所示:

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]

………

從而可以明確,該技術系統目前雖然比較簡單,但具有了一般網絡圖生成系統的特性和可擴展性,結合的節點計算、權值估計等算法也運行良好。

5、結束語

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

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

[2]JUNG 官方網站, http://jung.sourceforge.net/applet/index.html.

[3]網樹禾. 圖論[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-），男，山東郯城人，學員，從事基于文本數據庫的社會網絡分析法研究。

JUNG框架；MongoDB數據庫；網絡圖生成技術；可視化