后端 绘制有向无环图(DAG图)_dag java实现

因为公司的某个系统比较古老，里面的 job 的管理几乎都是直接通过操作数据库来实现的，对于一般的操作还可以忍受，但是每次想知道 job 之间的依赖关系的时候，就会相当难受，于是便脑袋很抽地一定要写一个查询系统能快速查询 job 之间的依赖关系。

分析

在项目开始之前，大概稍微估算了一下难点，大概可以分为以下两点：

如何在前端显示该依赖图
如何提高查询效率
1
2

此篇文章只看第一个问题，由于是本人是前端渣，于是只能去网上搜相应图形显示插件。

前端插件选择

找了很久，终于在 echarts 上找到了一个稍微适合自己的图形插件了，

http://echarts.baidu.com/examples/editor.html?c=graph-simple

不过，这个插件只是一个简单图的插件，也就是说这个插件并不会帮你进行自动定位相应的点，我们需要自己确定各个点的坐标。

解决方案

通过观察发现，该插件上的坐标只需要确定相对坐标就行了，它会根据相对位置进行自动定位，于是感觉瞬间轻松了许多。

仔细思考，发现 job 之间的依赖关系是一个有向无环图，于是开始构思。

要求：

将点按层次显示，保证前面层的点只依赖后面层的点 (同一层也禁止存在依赖关系)。
使得图尽可能整洁，尽量减少线段之间的交叉
1
2

解决方案：

通过拓扑排序来实现点的层次选择，每次将所有入度为 0 的点分为同一层即可
通过与前面层的点之间的关系设置相应的权重，同层之间根据权重来排序。我记得好像可以通过动态规划得到最优解的，不过实现起来太麻烦了，就算了
1
2

代码如下：

import java.util.*;


 * 作用: 绘制有向无环图(DAG图)
 *
 * 说明:
 * 配合Echarts的simple graph使用，地址见http://echarts.baidu.com/examples/editor.html?c=graph-simple
 * 用来进行点的坐标定位
 *
 * 使用条件: 图必须是一个有向无环图(DAG图)
 *
 * 调用方式: return new DagGraphUtil(points, links).drawDagGraph()
 *
 * 参数:
 * points的格式为 ['点1','点2','点3','点4']
 * links的格式为 [{"source":"点1","target":"点2"},{"source":"点2","target":"点3"},{"source":"点3","target":"点4"}]
 *
 * 返回结果:
 * {
 *     "points": [{"name": "点1","x":100,"y":100},{"name":"点2","x":200,"y":200}, ...],
 *     "links": [{"source":"点1","target":"点2"},{"source":"点2","target":"点3"}, ...]
 * }
 *
 *
 * 主要算法: 拓扑排序
 */
public class  {
    private final int MAX_LENGTH_X = 900;
    private final int MAX_LENGTH_Y = 1000;
    private int maxX;
    private Map<String, Integer> toNum;
    private Map<String, Integer> xPosition;
    private Map<String, Integer> yPosition;
    private Map<String, Integer> pointWeight;
    private List<Integer> ySize;
    private List<String> points;
    private List<Map<String, String>> links;

    public (List<String> points, List<Map<String, String>> links) {
        this.points = points;
        this.links = links;
        toNum = new HashMap<>(points.size());
        xPosition = new HashMap<>(points.size());
        yPosition = new HashMap<>(points.size());
        pointWeight = new HashMap<>(points.size());
        maxX = 0;
        ySize = new ArrayList<>();

        for (String point : points) {
            toNum.put(point, 0);
            pointWeight.put(point, 0);
        }
        for (Map<String, String> link : links) {
            String toPoint = link.get("target");
            addMapValue(toNum, toPoint, 1);
        }
    }

    public Map<String, Object> drawDagGraph() {
        Map<String, Object> result = new HashMap<>(3);
        dfs(0);
        List<Map<String, Object>> pList = new ArrayList<>(points.size());
        for (String point : points) {
            int xUnitLength = MAX_LENGTH_X / maxX;
            int x = xPosition.get(point) * xUnitLength + xUnitLength / 2;
            int yUnitLength = MAX_LENGTH_Y / ySize.get(xPosition.get(point));
            int y = yPosition.get(point) * yUnitLength + yUnitLength / 2;
            Map<String, Object> map = new HashMap<>(3);
            map.put("name", point);
            map.put("x", x);
            map.put("y", y);
            pList.add(map);
        }
        result.put("points", pList);
        result.put("links", links);
        return result;
    }

    private void dfs(int depth) {
        List<String> currentPoints = new ArrayList<>();
        for (String key : toNum.keySet()) {
            if (toNum.get(key) == 0) {
                currentPoints.add(key);
                addMapValue(toNum, key, -1);
            }
        }
        if (currentPoints.isEmpty()) {
            return;
        }
        maxX = depth + 1;
        ySize.add(currentPoints.size());
        Collections.sort(currentPoints, new Comparator<String>() {
            
            public int compare(String o1, String o2) {
                return pointWeight.get(o1) - pointWeight.get(o2);
            }
        });
        for (int i = 0, len = currentPoints.size(); i < len; i++) {
            String point = currentPoints.get(i);
            xPosition.put(point, depth);
            yPosition.put(point, i);
            for (Map<String, String> link : links) {
                if (link.get("source").equals(point)) {
                    maxMapValue(pointWeight, link.get("target"), i + 1);
                    addMapValue(toNum, link.get("target"), -1);
                }
            }
        }
        dfs(depth + 1);
    }

    private void addMapValue(Map<String, Integer> map, String key, Integer value) {
        if (map.containsKey(key)) {
            map.put(key, map.get(key) + value);
        } else {
            map.put(key, value);
        }
    }

    private void maxMapValue(Map<String, Integer> map, String key, Integer value) {
        if (!map.containsKey(key) || map.get(key) == 0 || map.get(key) < value) {
            map.put(key, value);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125