类超立方体网络中二项树构造模拟系统设计和实现 计算机科学与技术专业

类超立方体网络中二项树构造模拟系统目录摘要 1Abstract 2前言 4第一章绪论 61.1开发背景 61.2主要内容 71.3主要目标 7第二章技术背景 92.1JUNG及JavaSwing 92.1.1JUNG工具介绍 92.1.2Swing相关介绍 102.2关于Java 112.3二项树和JDBC 122.3.1关于运用JDBC连接数据库 122.3.2二项树的构造 14第三章需求分析 163.1总体需求分析 163.2图展示部分 163.2.1创建 173.2.2展示 173.2.3退出 183.3树展示部分 193.3.1创建 193.3.2展示 213.4构建二项树 22第四章系统设计 244.1开发运行环境 244.2关于系统部署 244.3功能概述 254.4系统数据库 264.4.1表名及其作用 264.4.2表用途 274.5数据库具体介绍 27第五章功能模块的实现 285.1主界面 285.2图演示 295.2.1创建 295.2.2退出 315.3树演示 315.3.1创建 315.3.2演示 345.4二项树的构建 36第六章结束语 40参考文献 41致 谢 42摘要近年来，互连网络（InterconnectionNetwork）成为了高性能并行计算机主要的研究课题之一。互连网络包含了多个学科领域的知识，包括计算机科学领域、信息化技术领域、通信领域以及数学领域等。同时，互联网络的结构也是多种多样的，超立方体（Hypercube）作为一个优秀的网络拓扑结构早先就已被提出。超立方体具有高度的对称性、正则性、短直径性、强容错性、可靠性、可嵌入性、可扩展性和网络良好的通信能力等众多优点，因此深受研究者们的喜爱，成为近些年来国际研究的热点之一。除此之外，超立方体网络还拥有众多优秀的变型网络，如交叉立方体、莫比乌斯立方体、扭立方体等。互连网络可以通过一个简单图G=(V(G);E(G))来表示，其中V(G)代表G的顶点集，E(G)代表G上的边集。在互连网络的设计和分析过程中，衡量一个互连网络的优劣的重要指标之一就是图嵌入能力。定义两个图G和H，由G到H的嵌入定义成由图G到图H的一个单射，G为客图，H为主图。主图应该具有优秀的图嵌入能力，使得客图的并行算法能得到高效的执行。衡量图嵌入能力的常用指标包括有拥塞、负载、扩张和膨胀，关于图嵌入最优性能的求解也是NP难的问题。二叉树是在各种系统中最常用的生成树结构，特别是在超立方体系统中。Loetal.将二叉树确定为并行分治算法的理想计算结构。Hsu表示在前缀计算中使用二叉树。二叉树结构也被广泛应用于数据的积累（也称为还原）和数据广播。随着计算机系统中处理器数量的增加，处理器失效的概率也会增加。在一个超立方体的生成二叉树中，如果连接两个节点的任何链接出现故障，那么树将被断开连接。这可能危及到使用这棵树的应用程序。这个问题的挑战在于识别一个生成二叉树它连接系统中的所有节点，只使用健康链接。在本文中，先是主要讲述了关于本课题的相关技术以及最近在超立方体上的研究成果。接着对模拟系统的设计需求进行了剖析，明确了此次模拟系统的设计方向目标。在明确了方向目标之后，紧接着将系统的模块进行了划分。对于系统的中心板块，本文着重进行了介绍。本课题的模拟系统主要是通过Java来完成设计的。通过主界面的菜单选项就可以观看到有关于超立方体中二项树的构造模拟的过程展示。关键词：超立方体，二项树，构造模拟AbstractInrecentyears,InterconnectionNetworkhasbecomeoneofthemainresearchtopicsofhighperformanceparallelcomputer.Theinterconnectionnetworkencompassesawiderangeofdisciplines,includingcomputerscience,informationtechnology,communications,andmathematics.Atthesametime,thestructureoftheInternetisdiverse,andHypercube(Hypercube)hasbeenproposedasanexcellentnetworktopology.Hypercubewithhighsymmetry,regularity,shortdiameter,strongfaulttoleranceandreliability,canbeembedded,scalabilityandnetworkmanyadvantagessuchasgoodcommunicationability,theresearchersloved,becomeoneoftheinternationalresearchhotspotinrecentyears.Inaddition,thehypercubenetworkalsohasanumberofexcellentvariationnetworks,suchascrosscube,mobiuscube,twistcubeandsoon.TheinterconnectnetworkcanbeobtainedthroughasimplegraphG=(V(G);E(G)),whereV(G)representsthevertexsetofG,andE(G)representstheedgesetonG.Intheprocessofdesignandanalysisofinterconnectionnetwork,oneoftheimportantindexestomeasureaninterconnectionnetworkistheimageembeddingcapability.DefinetwographsGandH,andtheembeddingfromGtoHisdefinedasasingleshotfromgraphGtofigureH,GforguestgraphandHformastergraph.Themasterdiagramshouldhaveexcellentimageembeddingcapability,sothattheparallelalgorithmcanbeexecutedefficiently.Thecommonlyusedindexesformeasuringtheembeddingabilityincludecongestion,load,expansionandexpansion,andthesolutiontotheoptimalperformanceofthegraphisalsoaNPhardproblem.Binarytreeisthemostcommonlyusedgenerationtreestructureinvarioussystems,especiallyinhypercubesystems.Loetal.Definedbinarytreeastheidealcomputingstructureforparallelpartitionalgorithm.Hsurepresentstheuseofbinarytreesinprefixcalculations.Binarytreestructureisalsowidelyusedindataaccumulation(alsoknownasreduction)anddatabroadcasting.Asthenumberofprocessorsincreasesinthecomputersystem,theprobabilityofprocessorfailureincreases.Inahypercubegeneratedbinarytree,ifanylinkbetweentwonodesfails,thetreewillbedisconnected.Thiscouldjeopardizetheapplicationusingthetree.Thechallengeistoidentifyabinarytreethatconnectsallnodesinthesystem,usingonlyhealthlinks.Inthispaper,wemainlyfocusontherelatedtechnologiesofthistopicandtherecentresearchresultsonhypercube.Thenthedesignrequirementsofthesimulationsystemareanalyzed,andthedesigndirectionofthesimulationsystemisclarified.Afterclarifyingthedirectiontarget,themoduleofthesystemisdivided.Forthecentralplateofthesystem,thispaperfocusesontheintroduction.ThesimulationsystemofthisprojectisdesignedmainlythroughJava.Throughthemenuoptionofthemaininterface,youcanseetheconstructionsimulationofthebinomialtreeinthehypercube.Keywords:hypercube,binomialtree,structuralsimulation.前言 近年来，并行计算在教育、科研、石油、生物、气象等相关领域成为研究热点。并行计算系统的性能一定意义上由互连网络决定。毫无疑问，对于互连网络和其性质的探讨是很有必要的。我们将互连网络展示为一个简单图，以顶点为处理器，边则为处理器间的通信链路。在一个G=(V,E)的图中，若图G的两个生成树T1和T2符合以下要求：（1）T1、T2的根是一样的，例如它们的顶点r1；（2）G中一顶点v（v≠r），T1和T2中从v到r的路径P和Q是不相交的，也就是说E(P)∩E(Q)=0并且V(P)∩V(Q)=[v,r]，P、Q是相互独立的。假若在图G上能够嵌入n棵以r为根的生成树，并且两两之间是相互独立的，则我们就把这n棵生成树称为G的一组独立生成树。独立生成树应用广泛，所以将独立生成树嵌入网络中的研究就显得很有必要。上面的问题类似于一个嵌入问题，它涉及到将一个主机图（二项树）映射到目标图（超立方体）。有两种类型的嵌入问题：指定的根嵌入和变量的根嵌入。在指定的根嵌入问题中，二项树的根必须映射到超立方体中指定的节点，而在变量根嵌入的问题中，二项树的根可以映射到超立方体中的任何节点。本文主要从系统的模块设计、构造模拟以及最终的实现技术一些方面着手，对类超立方体中二项树的构造模拟进行了分析。具体而言，主要有下列几项要点：1、在运用Java的基础上，模拟系统的所有的功能实现是可以被用户通过主菜单界面认识；2、对类超立方中二项树的嵌入构造进行模拟展示；3、构造模拟系统的框架清晰，界面简洁；4、使得并行计算机具有了通用性。容错能力对于并行计算机中的互联网络而言是很重要的，而对有故障的系统来说，在类超立方体网络中嵌入二项树是有实用价值的。关于本文的章节组织具体如下：在第一章节的绪论中，主要写明了此次课题的背景内容以及目的，还简述了本文章的文章架构；在第二章，简单介绍了此次模拟构造系统所用到的相关的技术；第三章从需求分析入手，对系统的几个模块做了简洁的说明；第四章则主要讲了关于系统的设计，用于开发的环境以及相关的模块、数据库的设计，简要的对相关功能也作了简单的介绍；在第五章，则是对各个功能模块的详细讲述；第六章作为最后一个章节则是对整片文章的一个总结。在文章结尾的是参考文献以及致谢部分。第一章绪论1.1开发背景计算科学（ComputationalDiscipline）在目前的科学界被认为是能够推动科学技术发展的第三门学科。计算科学在推动其他学术发展的同时也拥有着解决21世纪重大科学难题的综合实力。所以，计算科学是科学发展过程中必不可少的重要手段[1]。近年来，各相关领域对于计算能力的需求日益提高，许多具体应用也对计算性能提出了较高的要求。处理器性能的提高的速度基本遵循摩尔定律—每隔18个月翻一番[2]。随着技术的日益成熟，对于单个的处理器来说，提高运行速度和性能也日益困难。多处理器并行计算机的出现打破了单个处理器的这一僵局，满足了人们日益增长的速度性能需求，为实现高性能计算提供了解决办法[3]。高性能计算（HighPerformanceComputing，HPC）具有量大、快速、高效的特点。某种意义上它相当于并行计算（ParallelComputing）或者超级计算（Supercomputing）。换言之，并行计算机也可称为超级计算机或高性能计算机[4]。早期，我们将多个处理器（CPU）组成的计算机系统称为并行计算机，处理器之间通信协作，可以快速高效地解决大型复杂问题[1]。随着工作站机群的加入，多种并行体系结构并存发展着。互连网络（InterconnectionNetworks）是并行计算系统中多个处理机单元之间及处理机与内存单元间的传输机制[4]。一般来说，互连网络的拓扑结构需要在性能和成本上做到高性能低成本。所以，其设计理应符合以下几点原则[6,7]：（1）小顶点度（SmallDegree）：布线容易的同时，还降低网络搭建成本。（2）低通信传输延迟（SmallTransmissionDelay）：目的是最大程度减少网络中任意结点信息传输到其他结点的时间。（3）均匀及对称性（UniformityandSymmetry）：在这一条件下，结点的容量和连线的负载能保持某种平衡。（4）高容错（FaultTolerance）：对图的连通度提出了高要求，对并行计算机很重要。（5）可嵌入（Embeddability）：设计出来的网络要拥有一些简单图（例如树、圈、路）作为其子图。在以上几项原则下，一些较为复杂的互连网络相继被设计出。超立方体（Hypercube）就是一典型，除了递归性，低直径、高连通、对称性、正则性、可嵌入等特性都是其所具备的[5]。因此，超立方体是并行处理及并行计算机系统的常用拓扑结构之一[7,8]。1.2主要内容本系统主要是基于Java平台的开发，主要是一个类超立方体的构造模拟系统。通过系统所展现出来的内容主要是通过主菜单界面，能够看到所展现出来的图和树的构建以及过程的演示。而系统最大的特点就是通过JUNG技术来完成模拟构造系统，之所以选择JUNG技术，是由于它便于完成图或者超立方体网络的结构构造，并且可以完成网络图的可视化。系统的模块主要如下：关于图部分的展示创建过程：用户可以在主菜单页面进行创建选择，选择想要进行展示的图，包括四维、五维的图形。演示过程：用户可以选择演示按钮项开始图的展示过程，这里面包含花簇、线条以及滚动三种选择。退出过程：退出菜单项用于退出目前的效果展示。关于树部分的展示创建过程：用户可以在菜单项中选择创建，选中对应的树进行展示，其中包括一维、二维、三维以及四维。演示过程：用户可以选择演示菜单项，选中对应的效果开始展示，其中包括雷达布局、球布局以及横向布局。雷达布局顾名思义就是将结点像雷达一样地进行构造布局，这些点相应地是可以进行伸展、收缩以及移动操作的。球坐标则是为了便于快速判断树的数量而将所有的结点放在一个球坐标里。退出：退出菜单项用于退出目前的效果展示。二项树部分：通过数据的输入来生成二项树。1.3主要目标互连网络的性能问题毋庸置疑在很多方面都起着决定性的作用。所以理所当然地，对互连网络性能的研究是很有必要的，并将其作为并行计算方向的重要课题。能不能模拟并行计算里经常用到的网络类似树、圈、路径等等这些是评判互连网络性能的主要方向之一。图嵌入在这个领域已经得到了广泛的实践应用。树型结构是一个在并行计算、数据库、网络通信等众多方面都得到重视的非线性数据结构。例举几个较为常见的树型结构，有二叉树（BinaryTree）、独立生成树（IndependentSpanning，IST）、网孔树（MeshofTrees，MOT）、金字塔树（PyramidTrees）等等。关于在互连网络上嵌入这些树型结构的问题已经在学术界被深入探讨，并且也得到了一些不错的成果。主要目标如下所述：（1）图的展示部分：主要是要展示围绕某个中心点而生成的一维、二维、三维、四维以及五维的图形。（2）树的展示部分：从树的生成到展示，树有一维、二维、三维及四维的；展示可以通过雷达、球以及横向的形式展示。（3）关于二项树嵌入问题的研究是很有必要的，由于不可避免地是互连网络的规模是在持续增长的，所以考虑到处理器以及通信链路的故障问题，将二项树的容错嵌入能力纳入考虑研究就很有必要了。在本文所有内容共分为六章：在第一章节的绪论中，主要写明了此次课题的背景内容以及目的，还简述了本文章的文章架构；在第二章，简单介绍了此次模拟构造系统所用到的相关的技术；第三章从需求分析入手，对系统的几个模块做了简洁的说明；第四章则主要讲了关于系统的设计，用于开发的环境以及相关的模块、数据库的设计，简要的对相关功能也作了简单的介绍；在第五章，则是对各个功能模块的详细讲述；第六章作为最后一个章节则是对整片文章的一个总结。在文章结尾的是参考文献以及致谢部分。第二章技术背景本章节主要介绍了系统中用到的主要技术，接下来主要对JUNG开发工具、JavaSwing组件及事件以及MicrosoftOfficeAccess数据库进行了简单介绍。2.1JUNG及JavaSwingJUNG(JavaUniversalNetwork/GraphFramework)是一个软件库，它为建模、分析和可视化数据提供了一种通用的可扩展的语言，这些数据可以表示为图形或是网络。它是用Java编写的，它允许基于环境的应用程序使用JavaAPI的广泛内置功能，以及其他现有的第三方Java库。JavaSwing是一个GUI设计包，也是Java基础类之一，可以提供出一些超越AWT的屏幕显示元素，可以用于构建更好的图形用户界面。所以一般建议用Swing来取代AWT[9]。接下来主要介绍有关于系统中主要使用的JUNG工具以及Swing组件及事件。2.1.1JUNG工具介绍在JUNG中，Grapℎ<V,E>是基础的图结构的接口，V和E则表示的是顶点与边的数据类型。其中，关于这个接口所给予的用于构建图的途径有得到点及边的属性或者集合类；关于顶点及边的增删操作等。除此之外，JUNG还可以通过子接口的状态用于一些类型不一样的图上，比如说：无向图UndirectedGrapℎ<V,E>、有向图DirectedGrapℎ<V,E>、树Tree<V,E>以及森林Forest<V,E>等等。接着举一个小例子来实现并构造一个图。以SparseGraph为例，它表示一个可以有向也可无向的稀疏图，若有并行边的需求，也可以通过SparseMultigraph来实现，若要增加点或者边则分别运用addVertex及addEdge。如下所示代码CreatGraph.java则是构建了一个拥有两边三点的图，在此，点及边都是用的字符串类型，也可改为其他类型进行使用。运行上述代码可得：图显示如下：图2.1三点两边图显示2.1.2Swing相关介绍Swing的组件都是容器，而且许多的组件、类以及接口都是来自javax.swing包。Swing的很多组件都是从AWT继承而来，其中包括JFrame框架、JDialog对话框等。其余的组件则都是属于JCompoent的子类，通过JCompoent类来设置文本的颜色可以如下所示：publicvoidsetForeground(Colorcolor)//用于颜色的选择至于窗口菜单则主要是由菜单栏（JMenBar）、菜单（JMenu）、菜单项（JMenuItem）等组件构成。关于这几类组件的层次构造则是这样安排的，从菜单栏到菜单再到菜单项，其中菜单栏则是在布局管理之外的。关于javax.swing包中菜单组件的层次构造如下所示：图2.2菜单组件及其层次图当有状态发生变化或者有活动产生是，我们将这类情况称为事件（event）。而事件源（eventsource）则是用于产生的组件。当事件源作为一个框架时，点击用于执行关闭命令的按钮，则窗口关闭；当事件源组件为按钮，单击按钮则发生事件。关于事件的产生既可以由系统自己出发也可是用户操作导致。在Java中是将每一个事件都建成一个类的，而且每个类都有一个监听器（listenerinterface），监听器用于处理和执行事件的产生。举例如下：通过点击事件监听器的接口ActionListener来声明actonPerformed()的方法如下，约定了事件的处理方法，此方法的参数e是ActionEvent事件类对象。publicinterfaceActionListenerextendsEventListener//事件监听器接口{publicvoidactionPerformed(ActionEvente);//事件处理方法}窗口的事件监听器接口WindowListener声明了多个窗口事件的处理办法：publicinterfaceWindowListenerextendsEventListener//窗口事件监听器接口{publicvoidwindowOpened(WindowEvente);//窗口打开publicvoidwindowClosing(WindowEvente);//窗口关闭}2.2关于JavaJava是由C++语言变化过来是的，和C++相比较，Java语言有选择性地继承了有关C++的部分语法规则以及面向对象的一些基本机制，改进了C++语言模糊、复杂、不安全以及不适合网络应用等缺陷。Java是一种面向对象的语言，并且其所有的设计都需要在类中来进行实现，所以Java程序可以理解为许多类的集合：有可以支持八种基本数据类型的基本数据类型包装类，从而能够让基本数据类型和类可以相关联；数组被设成引用类型，它的使用是和对象一样的，同时数组都是有一个长度属性的；对于像C语言这种面向过程的设计以及像C++语言中的一些语法规则还有结构、联合及指针等这些数据类型是不支持的。在Java中指针的功能的实现是通过模型来完成的，结构类型的实现是由类来完成的。关于Java的继承机制，Java提供的是单重的继承机制，这种机制可以让所有的类可以形成一种树状结构的类层次结构。在这个树结构中有一个根类Object。关于Object；其中类声明对象的状及和行为是可以由所有的对象进行继承的。Java本身是不可以进行多重继承的，但是是可以通过“单重继承+接口”的办法来实现多重继承的功能。Java语言同时还具有简单性，对问题的表达是追求简单精炼的，这样可以使得程序避免了复杂同时也不会产生歧义。比如说以下标的方式代替指针来对数组进行操作；返回的结果也是用引用类型参数或者是返回值来代替了指针；指针可以用类来替代；丢弃默认参数转而用重载来进行构造，也不会有歧义。所以综上所述会发现即使没有了结构体、指针以及多重继承也不会对Java的功能产生不好的影响，反而Java的机制及性能会更好[9]。由于Java它的小型以及平台无关的特性，加上其适合Internet的环境，所以它成为了热门的编程语言之一。Java具有很多优越的性能，除了是面向对象的语言之外，Java还拥有安全可靠可移植等特点，并且还支持多线程的并发机制。2.3二项树和JDBC在Java程序中，我们通常使用JDBC[10]来访问数据库。而JDBC是用Java编写出来的类。JDBC给对数据库的访问设定了一个标准API（应用程序接口）。基于这个标准，我们可以通过SQL来访问数据库。二项树作为并行分布系统中经常使用的结构是一个拥有规则性以及递归性的图。在一个互连网络中，二项树的嵌入是保证了该网络的良好的可用性。二项树可以使用的地方也很多，比如说在前缀计算[11]、数据分发、数据广播等方面的运用。2.3.1关于运用JDBC连接数据库JDBC（JavaDataBaseConnectivity，Java数据库连接）是一个应用程序（API），可以用于连接、访问以及操作数据库，并且JDBC可以让SQL能在Java中执行并且支持数据库的访问及操作[9]。下面简述一下关于JDBC的一些基本功能：（1）决定程序的类型并与数据库建立起连接。（2）可以拥有关于数据库的一系列信息，比如数据库、表、列以及驱动程序等的属性等。（3）运行并处理SQL语句。执行SQL语句是JDBC中的主要的工作。在执行之前，显示与对应的数据库建立相应的连接；接着在完成语句的执行之后需要对产生的结果有一个处理。上述这些操作主要是通过JDBC中的接口及类来完成的。这里面有四个最重要的，分别是：ResultSet接口用于存储以及查询返回值；Statement接口用于SQL语句的执行以及管理；Connection接口主要是用来管理连接部分的；最后DriverManager接类则是用来管理驱动和创建连接的。如2.3所展示，其关系组织如下：图2.3关于JDBC的构成如果要与相应的数据库进行连接，那么找到相应的JDBC驱动程序则是首要步骤。Java.sal包则是用于来完成这一操作。具体如下：Class.forName(“DriverName”)；上述的DriverName是对应的驱动程序的名称，这是由对应的数据库供应商决定的。在此我们主要讨论了关于JDBC-OBDC桥驱动程序，具体如下：ClassName.forName（“sun.jdbc.odbc.JdbcOdbcDriver”）；通过DriverManager中的getConnection()可以与特定的数据库建立连接。若成功，就返回Connection对象；若失败，就抛出SQLException异常。相应的语句规定应如下：Connectoncon=DriverManager.getConnection(URL,user,password);这中间的URL代表着数据库的地址，它会根据驱动程序类型的不同而发生变化。2.3.2二项树的构造互连网络的性能问题毋庸置疑在很多方面都起着决定性的作用。所以理所当然地，对互连网络性能的研究是很有必要的，并将其作为并行计算方向的重要课题。能不能模拟并行计算里经常用到的网络类似树、圈、路径等等这些是评判互连网络性能的主要方向之一。图嵌入在这个领域已经得到了广泛的实践应用。树型结构是一个在并行计算、数据库、网络通信等众多方面都得到重视的非线性数据结构。例举几个较为常见的树型结构，有二叉树（BinaryTree）、独立生成树（IndependentSpanning，IST）、网孔树（MeshofTrees，MOT）、金字塔树（PyramidTrees）等等。关于在互连网络上嵌入这些树型结构的问题已经在学术界被深入探讨，并且也得到了一些不错的成果。关于二项树，在计算机领域，我们对其的解释和理解是树的每个节点都至多可以有两个分支的树结构，顺其自然地，这个节点的两个子树也就相应地分别被称为左子树和右子树，并且左右的顺序是一定的。在前面的这些前提下，我们可以得知二项树的第i层最多可以有2i−1个结点；深度等于k的时候最多有2在图论中，关于二项树的定义大体上是这样的：二项树是作为一个每个顶点的度都小于等于三的连通无环图。根据上述二项树的定义，我们可以得到如下几项关于二项树的性质：如果有i个支点，M表示树的所有支点的长度之和，N表示叶的长度之和，则N=M+2i；假设有N个节点，可以有H(n)个不一样的二项树，其中H(n)是卡特兰数的第n项，Hn如果一个包含n个节点的完全二项树通过顺序存储，那么可以得到下列关于结点间的关系：第一个，假设存在一个节点编号i>1，那么父节点的就是i/2；第二个，若2∗i≤N，那么左儿子是2∗i；如果2∗i第三个，若2∗i+1≤N，那么右儿子是2∗i+1；如果2∗i+1n个结点的完全二叉树深度表示为log2在二项树中，若N0是叶结点数，N2表示度数是2的结点总数，那么假设二项树的深度是h，那么最多能有2ℎ−1个节点，最少是h，其中二项树非空时，第n层的结点总数是不超过2i−1个（i≥1第三章需求分析随着互连网络的规模在逐日的增大，这就对处理器以及通信链路提出了要求，如果不做提升，不可避免的就会出现故障。首先，在超立方体网络中，经过前人们的研究发现，可以知道超立方体的变型往往比超立方体拥有更多优越的性能，加上二项树优越的嵌入能力，所以研究在类超立方体中如何最高效地去完成二项树的嵌入就显得很有必要。由于故障的出现是难免的，所以拓扑结构的容错性[12]纳入考虑是有很重要的现实意义的。3.1总体需求分析 关于类超立方体网络二项树构造模拟系统的主要目标如下所述：（1）图的展示部分：主要是要展示围绕某个中心点而生成的一维、二维、三维、四维以及五维的图形。（2）树的展示部分：从树的生成到展示，树有一维、二维、三维及四维的；展示可以通过雷达、球以及横向的形式展示。（3）关于二项树嵌入问题的研究是很有必要的，由于不可避免地是互连网络的规模是在持续增长的，所以考虑到处理器以及通信链路的故障问题，将二项树的容错嵌入能力纳入考虑研究就很有必要了。系统总共可以划分为三个模块：图展示部分在这一部分主要是创建超立方体，其中包括四维、五维的，展示效果可以有花簇线条以及滚动几个选择。（2）树展示部分在这一部分主要是关于树的创建，包括从一维到四维的树，展示效果可以有雷达布局、球布局以及横向布局几种选择。（3）二项树部分此部分是关于二项树的构建过程。3.2图展示部分 在这一部分所展示的内容主要是包括图的创建保存以及展示。3.2.1创建在主菜单界面，选择图形演示的菜单项，选择展示的效果，展示完成后，可选择退出当前界面。图3.1详细表达了有关于图创建的步骤以及可能情况。图3.1关于图的创建顺序3.2.2展示图3.2是展示的具体功能顺序图。通过展示的菜单项可以对展示效果进行选择。其中包括花簇、线条以及滚动效果。图3.2展示顺序图3.2.3退出图3.3是退出活动图，通过这个选项，用户可以对是否进行退出操作进行选择，当选定退出菜单项后，会有一个对话框，若确定退出则会退出当前的展示界面，取消则会留在当前界面。图3.3退出界面3.3树展示部分在这一部分主要是关于树的创建、展示以及退出功能。创建的树有一维树、二维树、三维树以及四维的树。3.3.1创建在主菜单界面，可以选择树展示菜单，选择想要进行展示的树以及展示树的效果，完成树的展示后点击退出就可以退出当前展示界面。图3.4是树的创建顺序，详细展示了创建过程中的步骤以及可能状况。图3.4树的创建顺序我们将超立方体中独立生成树[13]的根结点设定为0，并且将一个超立方体Qk分为两个子超立方体QA及QB，其中{0,1,2,…,2k−1}为QA的顶点集合，{2k−1,2k−1+1,2k−1+2,…,2k−1}为QB的顶点集合，QA及Q关于树的创建具体如下：（图3.5为构造过程图）：输入：k输出：Qk具体方法：一：若k=2，则返回独立路径T1<0,1,3,2>及T2<0,2,3,1>，反之则调用二：Qk−1的k−1个独立生成树分别表示为TA,1,TA,2,…,TA,k−1，TB,1,三：（T1,i从1到k−1Ti是由TBi根唯一的孩子和四：（Tk（1）：通过将点0和点2k−1相连接，（2）：i从0执行到k−2，使得点2k−1和2k−1+2i（3）：通过把点v以及顶点v+2k−1相连，可以得到2k−1−1个叶子结点（4）：parent(v,k)=parent(v,1);其中parentv,1=v−2k−1,并且v∈QB，v∉{2k−1图3.5关于树的构造过程3.3.2展示这部分内容主要是对树展示的详细介绍。进行展示时有雷达布局、球布局以及横向布局的效果。在图3.6中详细展示了关于树的展示顺序，如下所示：图3.6树的展示顺序3.4构建二项树下面对二项树的构建过程进行了一个举例演示，其中假设起点为1，接着输入2,3,4，然后具体的二项树的构建是由下列步骤形成的：（1）首先创建起点1；（2）把结点同21进行与操作，若得到的仍为21，那就添上一条边，且起点就是该结点，而终点则为相对应的结点数减去21；反之，则添上一条边，起点仍是各自的结点，但是终点变为相对应的结点加上21。根据这个规则，我们可以知道，将1同2（3）经过上述的运算后，目前的结点有1和3，这次与结点相与的数是22，其余依次推理，若与两结点与操作后得到的仍是22，则添上一条边，且对应起点不变，终点结点减去22；相反，若结果不为22，则添上一条边起点不变，终点加上22。根据上述算法，目前有（4）经过类推，可以得到接下来的四条新增边分别为(1,9)，(3,11)，(5,13)，(7,15)。其中进行与操作的数为输入数的减1取得结果。图3.7二项树举例第四章系统设计4.1开发运行环境本系统的开发环境为MyEclipse、JDK1.6、JUNG及MicrosoftOfficeAccess。本系统在WindowsVista、MyEclipse和MicrosoftOfficeAccess平台上运行。4.2关于系统部署图4.1关于包结构关于系统的包结构主要有Main_Test、Graph、Tree以及数据库公共服务四项。它们实现的主要功能分别为主界面功能、图演示功能、树演示功能以及系统内所有的数据信息的存放。（1）关于Main_Test包：MainScreen类：主要用于界面的风格以及位置的设定，也包括了一些菜单功能，是程序的主入口。（2）Graph包：CreateGraph-3类：用于3维图的构建；Graph_EdgeLabel类：用于改变线条的形状。（3）Tree包：CreateTree_1234_radiallayout类：用于1，2，3，4维树的构建，并且以雷达的效果展示。（4）数据库公共服务：主要任务是存取数据。4.3功能概述 如4.2所示为系统的基本构造图：图4.2系统基本结构（1）图演示部分创建：用户可以自主选择要创建的图形的种类，共有四维及五维两个选项。展示：用户可以在演示选项中选择以什么样的形式对图进行展示，其中包括了花簇、线条以及滚动三种效果。退出：用于退出当前的展示界面。（2）树演示部分创建：同图的创建相似，用户可以自主选择所要构建的树的类型，有从一维到四维树可进行选择。展示：在此菜单项，用户可以选择展示模式，如雷达、球布局或是横向的布局效果来进行展示。关于构建二项树：依据二项树定义，体现出二项树构建的过程。4.4系统数据库 在本系统中，采用的数据库为MicrosoftOfficeAccess，其中一共有表6张。具体描述如下。4.4.1表名及其作用在此系统中用的是MicrosoftOfficeAccess数据库，其中有名为Graph3.mdb、Graph4.mdb、Graph5.mdb的数据库，而每个数据库都有Vertex及Edge两个表。表4-1、表4-2、表4-3则是关于上述各库和表的介绍。标题描述数据库名称Graph3.mdb表名称Vertex、Edge用途存储3维图形的顶点、边的信息表4-1Graph3.mdb数据库标题描述数据库名称Graph4.mdb表名称Vertex、Edge用途存储4维图形的顶点、边的信息表4-2Graph4.mdb数据库标题描述数据库名称Graph5.mdb表名称Vertex、Edge用途存储5维图形的顶点、边的信息表4-3Graph5.mdb数据库4.4.2表用途上述的三个数据库中都拥有这点及边的信息，并且其中的两个表之间是相互对应的有关联的，因此点和边的数据类型在设定以及保存时要统一。表名描述Vertex存储图中点的信息Edge存储图中边的信息表4-4关于表的说明4.5数据库具体介绍本系统的三个数据库Graph3.mdb、Graph4.mdb及Graph5.mdb中都有两张表，为Vertex和Edg，由于它们的存储结构是差不多一致的，所以接下来就对这两张表进行详细表述。（1）点信息（Vertex）在构建图的时候，需要用到Vertex表内的信息。字段名称数据类型大小允许为空说明vertex_numInt4No点编号（自动标识ID）vertex_nameString20No点的名称表4-5Vertex表（2）边信息（Edge）在创建图时也需要用到Edge表中信息。字段名称数据类型大小允许为空说明edge_numint4No边的编号vertex1String20No边的起始点vertex2String20No边的终点表4-6Edge表第五章功能模块的实现在前面已经介绍了关于本系统的需求分析和设计。本章节主要对各模块的实现做了具体详细的解释。5.1主界面通过Java中的菜单组件，完成了主界面的设计。其中主要有五个类用于构建菜单：JMenBar、JMenu、JMenuItem、JCheckBoxMenuItem和JRadioButtonMenuItem。而菜单项则是可以用JMenuItem、JCheckBoxMenuItem或JRadioButtonMenuItem来构建。在本系统中则主要用到了一个JMenBar及三个JMenu1、JMenu2、JMenu3还有多个JMenuItem组件。其中JMenu1、JMenu2、JMenu3分别为图演示、树演示以及创建二项树。以下为相关部分代码：为了对菜单做出相应的响应，则需要用到actionPerformed()处理方法。具体如下：在对菜单项进行单击操作后，会有图5.1的效果。对前后变化进行对比，可认知菜单组件的作用。如下所示单击后出现的下拉菜单项。图5.1主界面5.2图演示5.2.1创建当菜单项被选中时，需要同数据库建立连接，从而获取相应的点及边的信息。当选中四维图时，图的展示如下所示，当要求显示最短路径后，图变化如下图5.2所示。图5.2四维图和四维不同的是，在五维的图形中，用户是可以对中心点进行选择的，并且可以选择相应想要的图的维数。如5.3所示。图5.3五维图5.2.2退出当用户点击退出菜单项时，则会跳出一个确认对话框来确认用户是否真的决定退出，关于一个问题的多个选项可以通过JOPtionPane的showConfirmDialog静态方法，设计代码如下：实际效果图如下：图5.4退出5.3树演示5.3.1创建树的构建是由一维树构建二维树，二维树构建三维树，三维树构建四维树，四维树构建五维树，关于这个构造算法在JUNG工具中有专用的接口及相关办法。将有向图作为基础来实现Tree接口的代码如下所示：创建完树后，需要通过JUNG的可视化功能的基本组BasicVisualizationServer类来实现树的可视化。在构造BasicVisualizatio