友链
关于
Java生态
Taketoday

JGraphT简介

2025/04/11

1. 概述

大多数时候，当我们实现基于图的算法时，我们还需要实现一些实用函数。

JGraphT是一个开源Java类库，它不仅为我们提供了各种类型的图，还提供了许多有用的算法来解决最常见的图问题。

在本文中，我们将了解如何创建不同类型的图以及使用所提供的实用程序。

2. Maven依赖

首先向我们的Maven项目添加依赖：

<dependency>
    <groupId>org.jgrapht</groupId>
    <artifactId>jgrapht-core</artifactId>
    <version>1.0.1</version>
</dependency>

最新版本可以在Maven Central找到。

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 有向图/无向图

它还允许我们创建有向/无向图。

在我们的示例中，我们将创建一个有向图并使用它来演示其他实用函数和算法：

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详细信息请参见此处。

4. API算法

现在，我们已经获得了完整的图对象，让我们来看看一些常见的问题及其解决方案。

4.1 图迭代

我们可以根据需要使用各种迭代器(例如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}可以被视为强连通子图。

我们可以为上图列出四个这样的子图：

{v9},{v8},{v5,v6,v7},{v1,v2,v3,v4}

列出所有强连通子图的实现：

@Test
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 欧拉回路

图G中的欧拉回路是包含G的所有顶点和边的回路，包含该回路的图称为欧拉图。

我们来看看图表：

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);
            });
}

现在，我们可以使用API测试图是否包含欧拉电路：

@Test
void givenGraph_whenCheckEluerianCycle_thenGetResult() {
    HierholzerEulerianCycle eulerianCycle
            = new HierholzerEulerianCycle<>();

    assertTrue(eulerianCycle.isEulerian(simpleGraph));
}
@Test
void whenGetEulerianCycle_thenGetGraphPath() {
    HierholzerEulerianCycle eulerianCycle
            = new HierholzerEulerianCycle<>();
    GraphPath path = eulerianCycle.getEulerianCycle(simpleGraph);

    assertTrue(path.getEdgeList()
            .containsAll(simpleGraph.edgeSet()));
}

4.5 哈密顿电路

恰好访问每个顶点一次的GraphPath称为哈密顿路径。

哈密顿环(或哈密顿电路)是一条哈密顿路径，使得(在图中)从路径的最后一个顶点到第一个顶点有一条边。

我们可以使用HamiltonianCycle.getApproximateOptimalForCompleteGraph()方法找到完全图的最佳哈密顿环。

此方法将返回近似的最小旅行商行程(哈密顿循环)，最优解是NP完全的，因此这是一个在多项式时间内运行的不错的近似值：

void whenGetHamiltonianCyclePath_thenGetVerticeSequence() {
    List<String> verticeList = HamiltonianCycle
        .getApproximateOptimalForCompleteGraph(completeGraph);
 
    assertEquals(verticeList.size(), completeGraph.vertexSet().size());
}

4.6 循环检测器

我们还可以检查图中是否存在任何循环，目前，CycleDetector仅支持有向图：

@Test
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允许我们生成图的可视化并将其保存为图像，首先让我们从Maven Central添加jgrapht-ext扩展依赖：

<dependency>
    <groupId>org.jgrapht</groupId>
    <artifactId>jgrapht-ext</artifactId>
    <version>1.0.1</version>
</dependency>

接下来，让我们创建一个具有3个顶点和3条边的简单有向图：

@BeforeEach
public void createGraph() {
    File imgFile = new File("src/test/resources/graph.png");
    imgFile.createNewFile();

    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
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，它接收我们的图作为构造函数参数，并对其应用了mxCircleLayout，这将以圆形的方式布局可视化效果。

此外，我们使用mxCellRenderer创建BufferedImage，然后将可视化内容写入png文件。

我们可以在浏览器或我们最喜欢的渲染器中看到最终的图像：

可以在官方文档中找到更多详细信息。

6. 总结

JGraphT提供了几乎所有类型的图和各种图算法，我们介绍了一些常用API的使用方法，也可以在官方页面上探索该库。

Show Disqus Comments

Post Directory

扫码关注公众号：Taketoday
发送 290992
即可立即永久解锁本站全部文章