美文网首页
无向图绘画树状拓扑图算法

无向图绘画树状拓扑图算法

作者: bobcorbett | 来源:发表于2017-08-15 16:31 被阅读0次

    基于目前Network项目需要,研究相关树形算法
    该需求难点如下:
    1、目前拓扑图是无向图,而树大多数都是基于有向图来画的,无法确定根节点
    2、网络拓扑中存在回环问题,导致链路可能会存在重叠问题

    针对问题1,目前根据所有节点的连通度来计算得出连通度最大的点作为根节点。
    问题2目前没有完美的解决方案。

    目前这边demo的算法分为2种
    1、根据每层叶子节点个数切割X轴坐标,然后平均分布在一条直线上。
    效果图如下:


    代码比较简单,暂时就不公布了。

    2、类似于一种递归的方式,从第一层叶子节点开始切割X轴,第二层叶子节点的范围不能超过上层节点之间的节点间距。
    直接看图:


    这种方式的弊端显而易见,如果后面存在大量叶子节点的枝节点,那么这里的叶子会非常密集

    改变一下根节点样子或许会好一些,但是这边会出现回路重合链路问题:

    下面贴上部分代码:

    public ResponseEntity<NodeList> getTreeTopo() {
        NodeList nodeList = new NodeList();
        HashMap<String, Connectivity> nodeCountMap = new HashMap<>();
        //统计所有节点的连通度
        for (int i = 0; i < lineTempList.size(); i++) {
            if (nodeCountMap.containsKey(lineTempList.get(i).getUplinkNodeId().toString())) {
                nodeCountMap.get(lineTempList.get(i).getUplinkNodeId().toString())
                        .setCount(nodeCountMap.get(lineTempList.get(i).getUplinkNodeId().toString()).getCount() + 1);
            } else {
                Connectivity connectivity = new Connectivity();
                connectivity.setCount(1);
                nodeCountMap.put(lineTempList.get(i).getUplinkNodeId().toString(), connectivity);
            }
            if (nodeCountMap.containsKey(lineTempList.get(i).getNodeId().toString())) {
                nodeCountMap.get(lineTempList.get(i).getNodeId().toString())
                        .setCount(nodeCountMap.get(lineTempList.get(i).getNodeId().toString()).getCount() + 1);
            } else {
                Connectivity connectivity = new Connectivity();
                connectivity.setCount(1);
                nodeCountMap.put(lineTempList.get(i).getNodeId().toString(), connectivity);
            }
        }
         
        //找到最大连通度的节点
        int maxConnectivity = 0;
        String rootNodeId = "";
        for(String nodeId : nodeCountMap.keySet()) {
            if(nodeCountMap.get(nodeId).getCount()>maxConnectivity) {
                maxConnectivity = nodeCountMap.get(nodeId).getCount();
                rootNodeId = nodeId;
            }
        }
         
        int treeLevel = 1; //树高度
        Set<String> nodeSet = new HashSet<>();//记录所有已经分配过坐标的节点,用于查重
        Map<String, NodeListInner> nodePositionMap = new HashMap<>();//记录所有节点坐标
        Map<String, NodeCount> subNodesCountMap = new HashMap<>();
        rootNodeId="35";//手工设置根节点
        nodeSet.add(rootNodeId);
        NodeListInner rootNode = new NodeListInner();
        rootNode.setNodeId(rootNodeId);
        rootNode.setX("2000");
        rootNode.setY("400");//假设画布为4000*4000
        nodeList.add(rootNode);
        nodePositionMap.put(rootNodeId, rootNode);
        //根节点放在(2000,400)位置
        List<Point> subPoint = getSubPoint(rootNodeId, nodeSet, subNodesCountMap);
        subNodesCountMap.get(rootNodeId).setSpace(3800);//两边各留100空间
        List<Point> parentPoint = new ArrayList<>();//需要保留父节点的信息
        Point rootPoint = new Point();
        rootPoint.setNodeId(rootNodeId);
        rootPoint.setParentId(null);
        parentPoint.add(rootPoint);
        while (subPoint.size() != 0) {// 如果遍历到树的最高一层,则结束循环
            //根据父节点的位置来分配叶子节点的位置
            for(int j=0;j<parentPoint.size();j++) {
                if(subNodesCountMap.get(parentPoint.get(j).getNodeId()).getCount()==0) {
                    continue;
                }
                int gap = subNodesCountMap.get(parentPoint.get(j).getNodeId()).getSpace() / subNodesCountMap.get(parentPoint.get(j).getNodeId()).getCount();//子节点得到点与点之间的间距距离
                int rightDeviation = 0;//单数往右偏移
                int leftDeviation = - gap;//双数往左偏移
                //获得子节点数据
                List<Point> point = new ArrayList<>();
                point = getSubPoint(parentPoint.get(j).getNodeId(), nodeSet, subNodesCountMap);
                //遍历节点然后赋予坐标值
                for(int i=0;i<point.size();i++) {
                    if(!subNodesCountMap.containsKey(point.get(i).getNodeId())) {
                        NodeCount nodeCount = new NodeCount();
                        nodeCount.setSpace(gap);
                        subNodesCountMap.put(point.get(i).getNodeId(), nodeCount);
                    } else {
                        subNodesCountMap.get(point.get(i).getNodeId()).setSpace(gap);//这一个迭代的子节点是下一个迭代的父节点
                    }
                     
                    NodeListInner node = new NodeListInner();
                    node.setNodeId(point.get(i).getNodeId());
                    if((i+1)%2==1) {//单数往右偏移
                        node.setX((rightDeviation+Integer.parseInt(nodePositionMap.get(parentPoint.get(j).getNodeId()).getX()))+"");
                        node.setY(400+treeLevel*400+"");
                        rightDeviation += gap;
                    } else {//双数往左偏移
                        node.setX((leftDeviation+Integer.parseInt(nodePositionMap.get(parentPoint.get(j).getNodeId()).getX()))+"");
                        node.setY(400+treeLevel*400+"");
                        leftDeviation -= gap;
                    }
                    nodePositionMap.put(point.get(i).getNodeId(),node);
                    nodeList.add(node);
                    nodeSet.add(node.getNodeId());
                }
            }
            parentPoint = new ArrayList<>(subPoint);
            subPoint.clear();
            for (int i = 0; i < parentPoint.size(); i++) {//统计还有没有下一层叶子节点
                subPoint.addAll(getSubPoint(parentPoint.get(i).getNodeId(), nodeSet, subNodesCountMap));
            }
            treeLevel+=1;
        }
         
        for (int j = 0; j < nodeList.size(); j++) {//补上节点之间的线
            List<Line> lines = new ArrayList<>();
            for (int i = 0; i < lineTempList.size(); i++) {
                if (nodeList.get(j).getNodeId().equals(lineTempList.get(i).getUplinkNodeId().toString())) {
                    Line line = new Line();
                    line.setDest(lineTempList.get(i).getNodeId().toString());
                    line.setDestX(nodePositionMap.get(lineTempList.get(i).getNodeId().toString()).getX());
                    line.setDestY(nodePositionMap.get(lineTempList.get(i).getNodeId().toString()).getY());
                    lines.add(line);
                }
            }
            nodeList.get(j).setLine(lines);
        }
         
        HttpHeaders headers = new HttpHeaders();
        headers.setContentType(MediaType.APPLICATION_JSON_UTF8);
        headers.add("Access-Control-Allow-Methods", "POST, GET, OPTIONS, DELETE, PUT");
        headers.add("Access-Control-Allow-Origin", "*");
        headers.add("Access-Control-Allow-Headers", "x-requested-with,content-type");
        return new ResponseEntity<NodeList>(nodeList, headers, HttpStatus.OK);
    }
     
    private List<Point> getSubPoint(String nodeId, Set<String> nodeSet, Map<String, NodeCount> subNodesCountMap) {
        int count = 0;
        List<Point> result = new ArrayList<>();
        for (int i = 0; i < lineTempList.size(); i++) {
            if (lineTempList.get(i).getUplinkNodeId().toString().equals(nodeId)) {
                if (!nodeSet.contains(lineTempList.get(i).getNodeId().toString())) {
                    // 存储对端节点
                    Point point = new Point();
                    point.setNodeId(lineTempList.get(i).getNodeId().toString());
                    point.setParentId(nodeId);
                    result.add(point);
                    count++;
                }
            }
            if (lineTempList.get(i).getNodeId().toString().equals(nodeId)) {
                if (!nodeSet.contains(lineTempList.get(i).getUplinkNodeId().toString())) {
                    // 存储对端节点
                    Point point = new Point();
                    point.setNodeId(lineTempList.get(i).getUplinkNodeId().toString());
                    point.setParentId(nodeId);
                    result.add(point);
                    count++;
                }
            }
        }
        if(!subNodesCountMap.containsKey(nodeId)) {
            NodeCount nodeCount = new NodeCount();
            nodeCount.setCount(count);
            subNodesCountMap.put(nodeId, nodeCount);
        } else {
            subNodesCountMap.get(nodeId).setCount(count);
        }
        return result;
    }
    

    相关文章

      网友评论

          本文标题:无向图绘画树状拓扑图算法

          本文链接:https://www.haomeiwen.com/subject/smrvrxtx.html