基于JUNG框架和MongoDB的网络图生成技术

2011-10-09王锐徐捷

中国科技信息 2011年2期

关键词：邻接矩阵网络图开源

王锐徐捷

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.