Jgrapht使用及介绍.ppt

《Jgrapht使用及介绍.ppt》由会员分享，可在线阅读，更多相关《Jgrapht使用及介绍.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、JGraphT包简介包简介1JGraphT简介项目主页项目主页：http:/ 图形可视化JGraphT涉及了几乎所有的对图这一数据结构的操作。例如，创建图创建图，修改图修改图，删除删除图图，添加顶点添加顶点，构造边构造边，图的遍历图的遍历，图的图的映射映射，连通性检查连通性检查，求最短路径求最短路径，求图的最小点覆盖最小点覆盖4 尽管JGraphT的设计是简单，安全类型的，但是功能却很强大。例如，图的顶点可是任何对象。您可以基于字符串，字符串，URL,XML文档档，等等创建图。甚至，你可以根据图来创建图。5与其他包（库，组件）的联系1.java.util（包含 collection框架、遗留的

2、 collection类、事件模型、日期和时间设施、国际化和各种实用工具类（字符串标记生成器、随机数生成器和位数组）2.Jgraph J纯Java开发的图形组件,支持拖，放，缩放，合并等其它操作。它可以被结合到任何的Swing应用程序当中。3.java.awt包含用于创建用户界面和绘制图创建用户界面和绘制图形图像形图像的所有类。6前端API的接口和类接口和类7Grapht接口 图结构的根接口根接口 public interface Graph 1.public Set getAllEdges(V sourceVertex,V targetVertex);2.public E getEdge(V

3、 sourceVertex,V targetVertex);3.public EdgeFactory getEdgeFactory();84.publicEaddEdge(VsourceVertex,VtargetVertex);5.publicbooleanaddEdge(VsourceVertex,VtargetVertex,Ee);6.publicbooleanaddVertex(Vv);7.publicbooleancontainsEdge(Ee);8.publicbooleancontainsVertex(Vv);9.publicbooleancontainsEdge(Vsource

4、Vertex,VtargetVertex);910.publicSetedgesOf(Vvertex);11.publicSetedgeSet();12.publicSetremoveAllEdges(VsourceVertex,VtargetVertex);13.publicbooleanremoveAllEdges(Eedges);14.publicbooleanremoveAllVertices(Vvertices);15.publicEremoveEdge(VsourceVertex,VtargetVertex);10Jgrapht简介16.publicbooleanremoveEdg

5、e(Ee);17.publicbooleanremoveVertex(Vv);18.publicSetvertexSet();19.publicVgetEdgeSource(Ee);20.publicVgetEdgeTarget(Ee);21.publicdoublegetEdgeWeight(Ee);11DirectedGraph.java有向图有向图publicinterfaceDirectedGraph extendsGraph1.publicintinDegreeOf(Vvertex);2.publicSetincomingEdgesOf(Vvertex);3.publicintout

6、DegreeOf(Vvertex);4.publicSetoutgoingEdgesOf(Vvertex);12UndirectedGraph.java无向图无向图publicinterfaceUndirectedGraph extendsGraph publicintdegreeOf(Vvertex);13EdgeFactory.java1.GraphHelper.java（publicabstractclassGraphHelpe extendsGraphs）2.GraphMapping.java（bidirectionalmapping）3.GraphPath.java4.VertexF

7、actory.java5.ListenableGraph.java6.WeightedGraph.java14Alg包包包简介（或作用）：提供图的一些基本算法。提供图的一些基本算法。1.ConnectivityInspector.java（连通性检查）（主要用的是图的遍历遍历方法）2.DijkstraShortestPath.java3.VertexCovers.java（点覆盖点覆盖）15迪杰斯特拉算法 用来求从某个源点到其余其余各个顶点的最短路径，按照路径长度递增递增的次序产生的。1617从顶点A（源点）到顶点B，C，D，E，F的最短距离初态为，10，30，100S=AT=B,C,D,E,

8、F从集合T中选取到顶点A路径长度最短的顶点u加入到集合S中S、T集合的状态变为：S=A,CT=B,D,E,F(10)(，30，100)18 根据算法思想：集合S每加入一个新的顶点u，都要修改顶点A到集合T中剩余顶点的最短路径长度值 当S=A，C后，A到其它顶点B，D，E，F的最短路径改变为S=A,CT=B,D,E,F(10)(，60，30，100)不断重复上述过程，直到集合T的顶点全部加入到S中或无通路为止。19BC10(A,C)D60(A,C,D)50(A,E,D)E30(A,E)30(A,E)F100(A,F)100(A,F)90(A,E,F)60(A,E,D,F)V(J)CEDFSA,C

9、A,C,EA,C,E,DA,C,E,D,F20 VertexCovers 设G，V*包含于V，若对于eE，vV*，使得v与e相关联，则称v覆盖e，并称V*为G的点覆盖集或简称点覆盖。V*是G的点覆盖，若V*的任何真子集都不是点覆盖，则称V*是极小点覆盖，顶点个数最少的点覆盖称为最小的点覆盖，其顶点个数称为点覆盖数，记作0(G)或简记为0.21该类中主要有两个函数1.publicstaticSetfind2ApproximationCover(Graphg)（近似的，相似的）2.SetfindGreedyCover(UndirectedGraphg)（贪婪算法贪婪算法，每次循环中，找出度最大的顶

10、点加到集合中，直到所有边被覆盖）找到一个图的真正的最小点覆盖是一个 NP-Completeproblem22Demo包包包简介（或作用）：演示演示程序1.HelloJGraphT.java（AsimpleintroductiontousingJGraphT）2.JGraphAdapterDemo.java（Ademo（演示）applet（小程序）thatshowshowtouseJGraphtovisualize（使可视化）JGraphTgraphs.）3.PerformanceDemo.java（AsimpledemototestmemoryandCPUconsumptiononagraph

11、with3million elements.一个简单的演示，测试内存和CPU消耗图300万的内容）23Event包包简介（或作用）：Eventclassesandlistenerinterfaces,usedtoprovideachangenotificationmechanismongraphmodification（修改变动）events.事件类和监听器的接口，在图修改事件中用来提供变动通知机制241.ConnectedComponentTraversalEvent.java（关于连通分量的一个遍历事件）2.EdgeTraversalEvent.java（边的遍历）3.GraphChang

12、eEvent.java（定义了一个 protectedinttype用来指示状态）4.GraphEdgeChangeEvent.java5.GraphVertexChangeEvent.java(指示一个图的顶点是否发生变化或者即将即将变化)6.GraphListener.java（如果图发生变化则通知监听器）257.TraversalListener.java（listenerongraphiteratororonagraphtraverser）8.TraversalListenerAdapter.java（Anemptydo-nothingimplementation（实施，执行）ofth

13、eTraversalListenerinterface usedforsubclasses.）9.VertexSetListener.java（当图中点的集合发生变化时通知监听器）10.VertexTraversalEvent.java26Ext包包简介（或作用）：Extensions（扩展）andintegration（集成）meanstootherproducts.我们只用到了其中的一个类JGraphModelAdapter.java一个适配器适配器，把JGraphT图转换成Jgraph图，当要把一个JGraphT图可视化的时候用到这个类。27Generate包包的简介（或作用）：Gene

14、rators（发生器）forgraphsofvarioustopologies（拓扑结构）.用到的类有：1.EmptyGraphGenerator.java（创建一个任意大小的空图，只有顶点没有边）2.GraphGenerator.java（为创建新的图结构定义了一个接口）283.LinearGraphGenerator.java（产生一个任意大小的线性图线性图）4.RingGraphGenerator.java（创建一个环形环形图图）5.WheelGraphGenerator.java（创建一个轮轮图图，一个圈C和一个顶点v，C上的所有点都与v相邻）29Traverse包包的简介（或作用）：

15、Graphtraversalmeans.用到的类有：1.AbstractGraphIterator.java（一个graphiterator的空的实现，以尽量减少执行graphiterator所需消耗。）2.BreadthFirstIterator.java（图的一个广度优广度优先先模式）3.ClosestFirstIterator.java（图的一个closest-first最近优先最近优先模式）304.DepthFirstIterator.java（深度优先深度优先模式）5.CrossComponentIterator.java（Providesacross-connected-compo

16、nenttraversalfunctionalityforiteratorsubclasses.）6.GraphIterator.java（图迭代器）7.TopologicalOrderIterator.java（拓扑排序迭（拓扑排序迭代器）代器）31拓扑排序方法：1.在有向图有向图中选一个没有前驱没有前驱的顶点并且输出2.从图中删除该顶点和所有以它为尾的边。重复1，2步，直至所有顶点都已经输出。3233A A A ABFECDBFECDFCDBFDB34FBF最后得到的拓扑排序为A,E,C,D,B,F 0 0 0 014532/*title：拓扑排序*input:一个有向无环图，表述为一个邻

17、接矩阵graphn，其中graphi0为顶点i的入度，其余为其后继结点*output:一个拓扑序列list*/importjava.util.*;publicclassTopologicalSortTestpublicstaticvoidmain(Stringargs)intgraph=0,1,2,3,2,1,1,4,2,4,3,0,3,4,;intlist=newintgraph.length;35TopologicalSorttopologicalSort=newTopologicalSort();topologicalSort.input(graph);list=topologicalS

18、ort.getList();for(intl:list)System.out.print(l+);classTopologicalSortintgraph;intlist;voidinput(intgraph)this.graph=graph;list=newintgraph.length;calculate();36voidcalculate()Stackstack=newStack();for(inti=0;igraph.length;i+)if(graphi0=0)stack.push(i);inti=0;while(stack.empty()!=true)listi=(Integer)

19、stack.pop();for(intj=1;jgraphlisti.length;j+)intk=graphlistij;if(-graphk0)=0)stack.push(k);i+;if(igraph.length)System.out.println(存在环，不可排序！);System.exit(0);intgetList()returnlist;37Util包 包的简介（或作用）：Non-graph-specificdatastructures,algorithms,andutilitiesusedbyJGraphT.被JGraphT用到的非图的具体数据结构，算法和实用程序。只用到了一个类FibonacciHeap.java 这个类实现一个Fibonacci堆堆数据结构。38 斐波那契堆斐波那契堆中的树都是有根的但是无序。每个节点x包含指向父节点的指针px和指向任意一个子结点的childx。x的所有子节点都用双向循环链表链接起来，叫做x的子链表。子链表中的每一个节点y都有指向它的左兄弟的lefty和右兄弟的righty。如果节点y是x仅有的子节点，则lefty=righty=y。39谢谢！40