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(深度优先),ClosestFirstIteratorRandomWalkIterator,我们可以根据实际的需求选择合适的迭代器来遍历图。

迭代器的创建方法很简单,只需要传入图对象即可:

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上获取。