JGraphT计算关键路径

标签：jgrapht activityGraph graph 路径 JGraphT org import addEdge 关键

简介

JGraphT 是一个Java实现的图论数据结构和算法库。本文讲介绍通过JGaphT来计算关键路径。

关键路径：用于在进度模型中估算最短工期，关键路径是项目中时间最长的活动时间。

案例

描述

下图Graph1-进度网络图表示项目的各项任务关系图以及任务的预计工期。为了采用图计算，这里将任务的预期工期转换为边的权重，如图Graph2-从后往前推，Graph3-从前往后推两种方式。

Graph2-从后往前推：边的权重表示箭头指向的任务预期工期。

Graph3-从前往后推：边的权重表示箭尾指向的任务预期工期。

JGraphT计算关键路径_JavaGraph

程序准备

通过JGraphT构建图和计算路径，引入对应的库。这里采用maven管理依赖。

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

<!-- 可选，扩展能力 -->
<dependency>
  <groupId>org.jgrapht</groupId>
  <artifactId>jgrapht-ext</artifactId>
  <version>1.5.2</version>
</dependency>
<dependency>
  <groupId>org.jgrapht</groupId>
  <artifactId>jgrapht-io</artifactId>
  <version>1.5.2</version>
</dependency>

程序示例1

示例2采用JGraphT提供的具体图实现类创建图，通过对应的API实现新增顶点，边，以及边的权重设置。

package org.deeplearning.graph;

import com.mxgraph.layout.mxCircleLayout;
import com.mxgraph.layout.mxIGraphLayout;
import com.mxgraph.util.mxCellRenderer;
import org.jgrapht.Graph;
import org.jgrapht.GraphPath;
import org.jgrapht.alg.cycle.CycleDetector;
import org.jgrapht.alg.shortestpath.AllDirectedPaths;
import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
import org.jgrapht.ext.JGraphXAdapter;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleDirectedWeightedGraph;
import org.jgrapht.graph.builder.GraphTypeBuilder;

import javax.imageio.ImageIO;
import java.awt.*;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;

public class CriticalPath {

    public static void main(String[] args) {

        // 构造图
        Graph<String, DefaultEdge> activityGraph = buildStyle1();

        // 检测是否有环
        CycleDetector<String, DefaultEdge> cycleDetector = new CycleDetector<>(activityGraph);
        System.out.println("图是否有环：" + cycleDetector.detectCycles());

        // Dijkstra 最短路径
        DijkstraShortestPath<String, DefaultEdge> dijkstraShortestPath = new DijkstraShortestPath<>(activityGraph);
        GraphPath<String, DefaultEdge> dijkstraGraphPath = dijkstraShortestPath.getPath("A", "G'");
        System.out.println(dijkstraGraphPath.getVertexList());

        // C->G G' 所有路径
        AllDirectedPaths<String, DefaultEdge> allDirectedPaths = new AllDirectedPaths<>(activityGraph);
        allDirectedPaths.getAllPaths("A", "G'", true, null).forEach(it -> {
            System.out.println(it.getVertexList() + " weight=" + it.getWeight());
        });
    }

    private static SimpleDirectedWeightedGraph<String, DefaultEdge> buildStyle1() {

        SimpleDirectedWeightedGraph<String, DefaultEdge> activityGraph = new SimpleDirectedWeightedGraph<>(DefaultEdge.class);

        //添加顶点
        activityGraph.addVertex("A");
        activityGraph.addVertex("B");
        activityGraph.addVertex("C");
        activityGraph.addVertex("D");
        activityGraph.addVertex("E");
        activityGraph.addVertex("F");
        activityGraph.addVertex("G");
        activityGraph.addVertex("G'");

        //添加边
        activityGraph.addEdge("A", "B");
        activityGraph.addEdge("A", "C");
        activityGraph.addEdge("A", "D");

        activityGraph.addEdge("B", "E");
        activityGraph.addEdge("B", "F");
        activityGraph.addEdge("C", "F");

        activityGraph.addEdge("E", "G");
        activityGraph.addEdge("F", "G");
        activityGraph.addEdge("D", "G");

        activityGraph.addEdge("G", "G'");

        //设置边权重
        activityGraph.setEdgeWeight("A", "B", 4.0D);
        activityGraph.setEdgeWeight("A", "C", 4.0D);
        activityGraph.setEdgeWeight("A", "D", 4.0D);

        activityGraph.setEdgeWeight("B", "E", 5.0D);
        activityGraph.setEdgeWeight("B", "F", 5.0D);
        activityGraph.setEdgeWeight("C", "F", 4.0D);

        activityGraph.setEdgeWeight("E", "G", 4.0D);
        activityGraph.setEdgeWeight("F", "G", 1.0D);
        activityGraph.setEdgeWeight("D", "G", 7.0D);

        activityGraph.setEdgeWeight("G", "G'", 2.0D);

        return activityGraph;
    }
}

程序示例2

示例2采用JGraphT提供的Builder模式来生成不同类型的图，以及图的构建。比如：有向图，有权重，不存在自身环，不存在多边，通过新增边来完成顶点，边，权重的设置。

package org.deeplearning.graph;

import com.mxgraph.layout.mxCircleLayout;
import com.mxgraph.layout.mxIGraphLayout;
import com.mxgraph.util.mxCellRenderer;
import org.jgrapht.Graph;
import org.jgrapht.GraphPath;
import org.jgrapht.alg.cycle.CycleDetector;
import org.jgrapht.alg.shortestpath.AllDirectedPaths;
import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
import org.jgrapht.ext.JGraphXAdapter;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleDirectedWeightedGraph;
import org.jgrapht.graph.builder.GraphTypeBuilder;

import javax.imageio.ImageIO;
import java.awt.*;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;

public class CriticalPath {

    public static void main(String[] args) {

        // 构造图
        Graph<String, DefaultEdge> activityGraph = buildStyle2();

        // 检测是否有环
        CycleDetector<String, DefaultEdge> cycleDetector = new CycleDetector<>(activityGraph);
        System.out.println("图是否有环：" + cycleDetector.detectCycles());

        // Dijkstra 最短路径
        DijkstraShortestPath<String, DefaultEdge> dijkstraShortestPath = new DijkstraShortestPath<>(activityGraph);
        GraphPath<String, DefaultEdge> dijkstraGraphPath = dijkstraShortestPath.getPath("A", "G'");
        System.out.println(dijkstraGraphPath.getVertexList());

        // C->G G' 所有路径
        AllDirectedPaths<String, DefaultEdge> allDirectedPaths = new AllDirectedPaths<>(activityGraph);
        allDirectedPaths.getAllPaths("A", "G'", true, null).forEach(it -> {
            System.out.println(it.getVertexList() + " weight=" + it.getWeight());
        });
    }


    //构造图
    private static Graph<String, DefaultEdge> buildStyle2() {
        return GraphTypeBuilder.<String, DefaultEdge>directed()
                .vertexClass(String.class)
                .edgeClass(DefaultEdge.class)
                .weighted(true)
                .allowingSelfLoops(false)
                .allowingMultipleEdges(false)
                .buildGraphBuilder()
                .addEdge("A", "B", 4.0D)
                .addEdge("A", "C", 4.0D)
                .addEdge("A", "D", 4.0D)
                .addEdge("B", "E", 5.0D)
                .addEdge("B", "F", 5.0D)
                .addEdge("C", "F", 4.0D)
                .addEdge("E", "G", 4.0D)
                .addEdge("F", "G", 1.0D)
                .addEdge("D", "G", 7.0D)
                .addEdge("G", "G'", 2.0D)
                .build();
    }
}

输出结果

图是否有环：false
[A, C, F, G, G']
[A, B, F, G, G'] weight=12.0
[A, B, E, G, G'] weight=15.0
[A, C, F, G, G'] weight=11.0
[A, D, G, G'] weight=13.0

结果分析

上述程序示例1和程序示例2的代码基于Graph3-从前往后推构建图，区别在于构建图采用的JGraphT API不同，其它是相同的。从输出结果分析：

图不存在环，符合我们创建图的参数设置
最短路径 A-C-F-G-G' 符合人工计算的结果
所有从A到G‘的路径以及权重和符合人工计算的结果
根据关键路径的定义，那么图Graph1-进度网络图中关键路径则是A到G'的最长路径（权重最大）即：A->B->E->G (注意不含G' 因为G'是我们为了采用图的路径计算引入的）

图相关资料

https://jgrapht.org/#docs a Java library of graph theory data structures and algorithms
https://www.geeksforgeeks.org/graph-types-and-applications/ 图类型和应用
https://www.geeksforgeeks.org/introduction-to-graphs-data-structure-and-algorithm-tutorials/ 图数据结构和算法手册
图论部分简介 - OI Wiki (oi-wiki.org)

标签：jgrapht,activityGraph,graph,路径,JGraphT,org,import,addEdge,关键
From： https://blog.51cto.com/aiilive/7178098

简介

案例

描述