1. 概述
当我们解决基于图数据结构相关算法时,如果自己实现那会很麻烦,还容易出差,扩展性和灵活性也较差。
JGraphT 是一个由Java编写的开源库,它实现了各种图数据结构,同时还提供了多种算法来解决常见的图问题。
本文,我们将学习如何使用JGraphT创建不同类型的图,以及如何使用它提供的这些功能。
2. Maven 依赖
添加Maven依赖:
<dependency>
<groupId>org.jgrapht</groupId>
<artifactId>jgrapht-core</artifactId>
<version>1.0.1</version>
</dependency>
获取最新版本请访问 Maven 中央仓库。
3. 创建图
JGraphT 支持各种类型的图。
3.1. 简单图
创建一个顶点类型为String
的简单图:
Graph<String, DefaultEdge> g
= new SimpleGraph<>(DefaultEdge.class);
g.addVertex("v1");
g.addVertex("v2");
g.addEdge("v1", "v2");
3.2. 有向/无向图
JGraphT支持创建有向/无向图。
下面,我们创建一个有向图,后面的算法演示例子中将用到它:
DirectedGraph<String, DefaultEdge> directedGraph
= new DefaultDirectedGraph<>(DefaultEdge.class);
directedGraph.addVertex("v1");
directedGraph.addVertex("v2");
directedGraph.addVertex("v3");
directedGraph.addEdge("v1", "v2");
// Add remaining vertices and edges
3.3. 完全图
类似的,我们可以创建完全图:
public void createCompleteGraph() {
completeGraph = new SimpleWeightedGraph<>(DefaultEdge.class);
CompleteGraphGenerator<String, DefaultEdge> completeGenerator
= new CompleteGraphGenerator<>(size);
VertexFactory<String> vFactory = new VertexFactory<String>() {
private int id = 0;
public String createVertex() {
return "v" + id++;
}
};
completeGenerator.generateGraph(completeGraph, vFactory, null);
}
3.4. 多重图
除了简单图,API还为我们提供了创建多重图的方法(两个顶点之间具有多个路径的图)。
此外,我们可以在任何图中对边设置权重。
下面我们创建一个有权多重图:
public void createMultiGraphWithWeightedEdges() {
multiGraph = new Multigraph<>(DefaultWeightedEdge.class);
multiGraph.addVertex("v1");
multiGraph.addVertex("v2");
DefaultWeightedEdge edge1 = multiGraph.addEdge("v1", "v2");
multiGraph.setEdgeWeight(edge1, 5);
DefaultWeightedEdge edge2 = multiGraph.addEdge("v1", "v2");
multiGraph.setEdgeWeight(edge2, 3);
}
除此之外,我们还可以创建不可修改(只读)和可监听(监听和跟踪修改事件)的图和子图。 同样,我们还可以创建这些图的所有组合。
更多API详细信息,可以查阅JavaDoc。
4. 图算法
创建好图对象之后,下面我们学习如何用它解决常见算法问题。
org.jgrapht.alg 包中提供了非常多的算法,例如PageRank(网页排序)、Louvain(社团挖掘)、KCore(社区发现、金融风控)、最短路径等等。
4.1. 图的遍历
JGraphT提供几种不同的迭代器(Iterator),例如BreadthFirstIterator
(广度优先),DepthFirstIterator
(深度优先),ClosestFirstIterator
,RandomWalkIterator
,我们可以根据实际的需求选择合适的迭代器来遍历图。
迭代器的创建方法很简单,只需要传入图对象即可:
DepthFirstIterator depthFirstIterator
= new DepthFirstIterator<>(directedGraph);
BreadthFirstIterator breadthFirstIterator
= new BreadthFirstIterator<>(directedGraph);
创建好迭代器之后,我们可以像普通集合遍历一样,使用hasNext()
和next()
方法来遍历图。
4.2. 寻找最短路径
org.jgrapht.alg.shortestpath
包中提供了多种最短路径算法的实现,如Dijkstra, Bellman-Ford, Astar 和 FloydWarshall 算法
下面使用 Dijkstra(迪杰斯特拉) 算法寻找最短路径:
@Test
void whenGetDijkstraShortestPath_thenGetNotNullPath() {
DijkstraShortestPath dijkstraShortestPath
= new DijkstraShortestPath(directedGraph);
List<String> shortestPath = dijkstraShortestPath
.getPath("v1","v4").getVertexList();
assertNotNull(shortestPath);
}
类似地,我们也可以使用Bellman-Ford(贝尔曼-福特算法)算法实现:
@Test
void whenGetBellmanFordShortestPath_thenGetNotNullPath() {
BellmanFordShortestPath bellmanFordShortestPath
= new BellmanFordShortestPath(directedGraph);
List<String> shortestPath = bellmanFordShortestPath
.getPath("v1", "v4")
.getVertexList();
assertNotNull(shortestPath);
}
4.3. 寻找强连通子图
在开始实现之前,我们先简单了解下何为强连通子图。仅当子图中的每一对顶点之间都存在路径,则该子图是强连通的。
在我们的例子中,{v1,v2,v3,v4}可以被视为强连通子图的条件是,如果我们从当前顶点开始遍历,可以达到任意顶点。
从上面有向图的示图中,我们可以列举出4个连通子图:
{v9},{v8},{v5,v6,v7},{v1,v2,v3,v4}
实现代码:
@Test
public void
whenGetStronglyConnectedSubgraphs_thenPathExists() {
StrongConnectivityAlgorithm<String, DefaultEdge> scAlg
= new KosarajuStrongConnectivityInspector<>(directedGraph);
List<DirectedSubgraph<String, DefaultEdge>> stronglyConnectedSubgraphs
= scAlg.stronglyConnectedSubgraphs();
List<String> stronglyConnectedVertices
= new ArrayList<>(stronglyConnectedSubgraphs.get(3)
.vertexSet());
String randomVertex1 = stronglyConnectedVertices.get(0);
String randomVertex2 = stronglyConnectedVertices.get(3);
AllDirectedPaths<String, DefaultEdge> allDirectedPaths
= new AllDirectedPaths<>(directedGraph);
List<GraphPath<String, DefaultEdge>> possiblePathList
= allDirectedPaths.getAllPaths(
randomVertex1, randomVertex2, false,
stronglyConnectedVertices.size());
assertTrue(possiblePathList.size() > 0);
}
4.4. 欧拉回路 (Eulerian Circuit)
如果图G中的一个路径包括每个边恰好一次,则该路径称为欧拉路径(Euler path)。 如果一个回路是欧拉路径,则称为欧拉回路(Euler circuit)
对应的图:
public void createGraphWithEulerianCircuit() {
SimpleWeightedGraph<String, DefaultEdge> simpleGraph
= new SimpleWeightedGraph<>(DefaultEdge.class);
IntStream.range(1,5)
.forEach(i-> simpleGraph.addVertex("v" + i));
IntStream.range(1,5)
.forEach(i-> {
int endVertexNo = (i + 1) > 5 ? 1 : i + 1;
simpleGraph.addEdge("v" + i,"v" + endVertexNo);
});
}
现在我们可以利用JGraphT提供的API测试一个图是否包含欧拉路径:
@Test
public void givenGraph_whenCheckEluerianCycle_thenGetResult() {
HierholzerEulerianCycle eulerianCycle
= new HierholzerEulerianCycle<>();
assertTrue(eulerianCycle.isEulerian(simpleGraph));
}
@Test
public void whenGetEulerianCycle_thenGetGraphPath() {
HierholzerEulerianCycle eulerianCycle
= new HierholzerEulerianCycle<>();
GraphPath path = eulerianCycle.getEulerianCycle(simpleGraph);
assertTrue(path.getEdgeList()
.containsAll(simpleGraph.edgeSet()));
}
4.5. 哈密顿回路(Hamiltonian Circuit)
若图G中一条路径通过且仅通过每一个顶点一次,称这条路径为哈密顿路径。
如果哈密顿路径是一个环,即首尾节点相连,则称这条路径为哈密顿回路。
我们可以利用HamiltonianCycle.getApproximateOptimalForCompleteGraph()
方法寻找完全图中最优哈密顿回路。
This method will return an approximate minimal traveling salesman tour (Hamiltonian cycle). The optimal solution is NP-complete, so this is a decent approximation that runs in polynomial time:
public void
whenGetHamiltonianCyclePath_thenGetVerticeSequence() {
List<String> verticeList = HamiltonianCycle
.getApproximateOptimalForCompleteGraph(completeGraph);
assertEquals(verticeList.size(), completeGraph.vertexSet().size());
}
4.6. 检测图中是否有环
我们可以使用CycleDetector
判断图中是否有环,目前CycleDetector
只支持有向图:
@Test
public void whenCheckCycles_thenDetectCycles() {
CycleDetector<String, DefaultEdge> cycleDetector
= new CycleDetector<String, DefaultEdge>(directedGraph);
assertTrue(cycleDetector.detectCycles());
Set<String> cycleVertices = cycleDetector.findCycles();
assertTrue(cycleVertices.size() > 0);
}
5. 将图可视化
JGraphT 支持生成图的可视化界面并保存为图片。
为此我们需要先添加扩展依赖 jgrapht-ext:
<dependency>
<groupId>org.jgrapht</groupId>
<artifactId>jgrapht-ext</artifactId>
<version>1.0.1</version>
</dependency>
创建一个具有3个顶点和3个边的简单有向图:
@BeforeEach
public void createGraph() {
DefaultDirectedGraph<String, DefaultEdge> g =
new DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);
String x1 = "x1";
String x2 = "x2";
String x3 = "x3";
g.addVertex(x1);
g.addVertex(x2);
g.addVertex(x3);
g.addEdge(x1, x2);
g.addEdge(x2, x3);
g.addEdge(x3, x1);
}
然后将其可视化:
@Test
public void givenAdaptedGraph_whenWriteBufferedImage_thenFileShouldExist() throws IOException {
JGraphXAdapter<String, DefaultEdge> graphAdapter =
new JGraphXAdapter<String, DefaultEdge>(g);
mxIGraphLayout layout = new mxCircleLayout(graphAdapter);
layout.execute(graphAdapter.getDefaultParent());
BufferedImage image =
mxCellRenderer.createBufferedImage(graphAdapter, null, 2, Color.WHITE, true, null);
File imgFile = new File("src/test/resources/graph.png");
ImageIO.write(image, "PNG", imgFile);
assertTrue(imgFile.exists());
}
这里我们创建一个JGraphXAdapter
实例,它接收graph作为构造函数参数,然后应用到mxCircleLayout
。
然后,我们使用mxCellRenderer
创建一个BufferedImage
,最后把可视化结果写入png文件中。
最后使用图片浏览器查看我们渲染后的图片:
更详细资料可以访问官方文档.
6. 总结
JGraphT 提供几乎所有类型的图和各种图算法。我们介绍了最常用到的API使用方法,学习更多用法你可以访问JGraphT 官网。
惯例,本文完整源代码可从GitHub上获取。