Java图数据结构：JGraphT的介绍和用法

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. 算法

创建好图对象之后，下面我们学习如何用它解决常见算法问题。

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
    public void whenGetDijkstraShortestPath_thenGetNotNullPath() {
        DijkstraShortestPath dijkstraShortestPath 
          = new DijkstraShortestPath(directedGraph);
        List<String> shortestPath = dijkstraShortestPath
          .getPath("v1","v4").getVertexList();
     
        assertNotNull(shortestPath);
    }

类似地，我们也可以使用Bellman-Ford（贝尔曼-福特算法）算法实现：

@Test
public 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个边的简单有向图：

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