遍历有向网格链路实现

在实际的业务中，我们可能遇到复杂规则（多个或与条件组合），复杂链路等类似场景问题，如：规则引擎相关业务，生产任务排期等。

复杂链路示意图如下：
在这里插入图片描述

复杂网路链路场景描述

  1. 有一个或多个开始节点，有一个或多个结束节点；
  2. 各节点通过有向箭头来描述节点之间的关系；
  3. 关系节点之间不可形成回路；
  4. 节点数量不固定，关系不固定。

程序如何算出所有链路？

设计思路：

节点场景：

  • 开始节点：如图编号1所示
  • 中间节点：如图编号2所示
  • 终止节点：如图编号3所示
  • 零节点：没有关系的节点，如图编号4所示

在这里插入图片描述

如何定义数据模型去描述节点之间的关系呢？

@Data
public class LinkItem {

    // 该节点ID
    private Integer id;

    // 可到达该节点的ID列表
    private List<Integer> pre;

    // 该节点可以到达哪些节点的ID列表
    private List<Integer> next;

    public LinkItem(Integer id, List<Integer> pre, List<Integer> next) {
        this.id = id;
        this.pre = pre;
        this.next = next;
    }
}

如何校验回路链路？

如下图形成了回路：
在这里插入图片描述
思路：链路是由一个个节点有序链接而成，出现了回路，就说明遍历到该节点时，该节点或该节点的next节点出现在该链路中了。

关键代码

package com.example.demo.util;

import cn.hutool.core.collection.CollUtil;
import com.alibaba.fastjson2.JSON;
import com.example.demo.domain.Link;
import com.example.demo.domain.LinkItem;
import lombok.extern.slf4j.Slf4j;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

@Slf4j
public class LinkHandlerUtil {

    public static List<Link> getAllLink(List<LinkItem> linkItems) {

        if (CollUtil.isEmpty(linkItems)) {
            log.info("LinkHandlerUtil.getRuleCondition(), linkItems is null");
            throw new RuntimeException("参数为空");
        }

        // 链路数据处理
        List<Link> result = new ArrayList<>();
        handlerLinkData(result, linkItems);

        return result;
    }

    /**
     * 找出所有链路数据
     *
     * @param list
     * @param linkItems
     */
    private static void handlerLinkData(List<Link> list, List<LinkItem> linkItems) {

        // 1.找出初始链路
        for (LinkItem linkItem : linkItems) {
            if (CollUtil.isEmpty(linkItem.getPre())) {
                linkItemHandler(linkItem, list, linkItems);
            }
        }

        // 2. 递归出所有链路
        boolean flag = allLinkIsEnd(list, linkItems);
        while (!flag) {

            for (LinkItem linkItem : linkItems) {
                if (CollUtil.isNotEmpty(linkItem.getPre())) {
                    linkItemHandler(linkItem, list, linkItems);
                }
            }

            flag = allLinkIsEnd(list, linkItems);
        }
    }

    /**
     * 校验该链路是否结束
     *
     * @param link
     * @param linkItems
     * @return
     */
    private static boolean linkIsEnd(Link link, List<LinkItem> linkItems) {

        List<Integer> itemIds = link.getItemIds();
        LinkItem linkItem = getItemById(itemIds.get(itemIds.size() - 1), linkItems);
        if (CollUtil.isNotEmpty(linkItem.getNext())) {
            return false;
        }

        return true;
    }

    /**
     * 判断所有链路是否都结束了
     *
     * @param links
     * @param linkItems
     * @return
     */
    private static boolean allLinkIsEnd(List<Link> links, List<LinkItem> linkItems) {

        if(CollUtil.isEmpty(links)) {
            return true;
        }

        for (Link link : links) {
            boolean flag = linkIsEnd(link, linkItems);
            if (!flag) {
                return false;
            }
        }

        return true;
    }

    /**
     * 获取ItemById
     * @param id
     * @param linkItems
     * @return
     */
    private static LinkItem getItemById(Integer id, List<LinkItem> linkItems) {

        for (LinkItem linkItem : linkItems) {
            if (linkItem.getId().equals(id)) {
                return linkItem;
            }
        }

        return null;
    }

    /**
     * 节点校验
     * @param id
     * @param link
     * @param linkItems
     */
    private static void itemIdIsValid(Integer id, Link link, List<LinkItem> linkItems) {

        LinkItem linkItem = getItemById(id, linkItems);
        if (null == linkItem) {
            throw new RuntimeException("参数linkItem为空");
        }

        // 链路是否包含当前节点校验
        List<Integer> itemIds = link.getItemIds();
        if (itemIds.contains(linkItem.getId())) {
            throw new RuntimeException("参数链路规则校验失败");
        }

        // 链路是否包含当前节点的next节点校验
        if (CollUtil.isNotEmpty(linkItem.getNext())) {
            for (Integer itemId : linkItem.getNext()) {
                if (itemIds.contains(itemId)) {
                    throw new RuntimeException("参数链路规则校验失败");
                }
            }
        }
    }

    /**
     * 节点链路处理
     * @param linkItem
     * @param list
     * @param linkItems
     */
    private static void linkItemHandler(LinkItem linkItem, List<Link> list, List<LinkItem> linkItems) {

        // 场景1： pre-无，next-无
        if (CollUtil.isEmpty(linkItem.getPre()) && CollUtil.isEmpty(linkItem.getNext())) {
            Link link = new Link();
            List<Integer> itemIds = new ArrayList<>();
            itemIds.add(linkItem.getId());
            link.setItemIds(itemIds);
            list.add(link);
            return;
        }

        // 场景2：pre-无， next-有，开始节点，链路中需要添加当前节点和next节点
        if (CollUtil.isEmpty(linkItem.getPre()) && CollUtil.isNotEmpty(linkItem.getNext())) {
            for (Integer id : linkItem.getNext()) {
                Link link = new Link();
                List<Integer> itemIds = new ArrayList<>();
                itemIds.add(linkItem.getId());
                itemIds.add(id);
                link.setItemIds(itemIds);
                list.add(link);
            }
            return;
        }

        // 场景3：pre-有， next-无，终止节点，链路无需处理
        if (CollUtil.isNotEmpty(linkItem.getPre()) && CollUtil.isEmpty(linkItem.getNext())) {
            // 由于终止节点已经在场景4里面添加了，所以此处无需任何处理
            return;
        }

        // 场景4： pre-有， next-有，中间节点，由于当前节点已经在场景2添加过了，此时只需要添加next节点
        if (CollUtil.isNotEmpty(linkItem.getPre()) && CollUtil.isNotEmpty(linkItem.getNext())) {

            if(CollUtil.isEmpty(list)) {
                throw new RuntimeException("参数校验失败，中间节点链路不可为空");
            }

            List<Link> newList = new ArrayList<>();
            List<Link> removeList = new ArrayList<>();

            // 先找出该节点对应的链路
            for (Link link : list) {

                List<Integer> itemIds = link.getItemIds();
                Integer id = link.getItemIds().get(itemIds.size() - 1);

                if (id.equals(linkItem.getId())) {

                    for (int i = 0; i < linkItem.getNext().size(); i++) {

                        // 校验当前节点是否合法
                        itemIdIsValid(linkItem.getNext().get(i), link, linkItems);

                        // 删除原来的链路
                        removeList.add(link);

                        // 补充一个新的链路，并将该节点的next节点加入链路中
                        Link newLink = new Link();
                        List<Integer> newRuleItems = new ArrayList<>();
                        newRuleItems.addAll(link.getItemIds());
                        newRuleItems.add(linkItem.getNext().get(i));
                        newLink.setItemIds(newRuleItems);
                        newList.add(newLink);
                    }
                }
            }

            if (CollUtil.isNotEmpty(newList)) {
                list.removeAll(removeList);
                list.addAll(newList);
            }
        }
    }

    
}

Link：

@Data
public class Link {
    private List<Integer> itemIds;
}

结果验证

该数据来源于本文开头的示意图。

public static void main(String[] args) {

    List<LinkItem> linkItems = new ArrayList<>();

    linkItems.add(new LinkItem(1, null, Arrays.asList(2, 6)));
    linkItems.add(new LinkItem(2, Arrays.asList(1, 6), Arrays.asList(3, 7)));
    linkItems.add(new LinkItem(3, Arrays.asList(2, 10), Arrays.asList(4, 12)));
    linkItems.add(new LinkItem(4, Arrays.asList(3, 11), Arrays.asList(5, 7)));
    linkItems.add(new LinkItem(5, Arrays.asList(4, 8, 12), null));
    linkItems.add(new LinkItem(6, Arrays.asList(1), Arrays.asList(2)));
    linkItems.add(new LinkItem(7, Arrays.asList(2, 4), Arrays.asList(8)));
    linkItems.add(new LinkItem(8, Arrays.asList(7), Arrays.asList(5)));
    linkItems.add(new LinkItem(9, null, Arrays.asList(10, 13)));
    linkItems.add(new LinkItem(10, Arrays.asList(9), Arrays.asList(3)));
    linkItems.add(new LinkItem(11, Arrays.asList(12), Arrays.asList(4)));
    linkItems.add(new LinkItem(12, Arrays.asList(3), Arrays.asList(5, 11)));
    linkItems.add(new LinkItem(13, Arrays.asList(9), Arrays.asList(15, 17)));
    linkItems.add(new LinkItem(15, Arrays.asList(13), Arrays.asList(16)));
    linkItems.add(new LinkItem(16, Arrays.asList(15), Arrays.asList(17)));
    linkItems.add(new LinkItem(17, Arrays.asList(13, 16), null));
    linkItems.add(new LinkItem(18, null, null));
    linkItems.add(new LinkItem(19, null, Arrays.asList(20)));
    linkItems.add(new LinkItem(20, Arrays.asList(19), null));

    List<Link> links = getAllLink(linkItems);
    for (Link link : links) {
        log.info("{}", JSON.toJSONString(link));
    }
}

运行结果：

截图红框就是本文示意图的所有链路。
在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/872837.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

机器学习如何用于音频分析？

机器学习如何用于音频分析？

机器学习如何用于音频分析&#xff1f; 一、说明 近十年来&#xff0c;机器学习越来越受欢迎。事实上&#xff0c;它被用于医疗保健、农业和制造业等众多行业。随着技术和计算能力的进步&#xff0c;机器学习有很多潜在的应用正在被创造出来。由于数据以多种格式大量可用&…
阅读更多...
EasyExcel实现复杂Excel的导入

EasyExcel实现复杂Excel的导入

最近项目中遇到一个复杂的Excel的导入&#xff0c;并且数据量较大。因为数据不规则&#xff0c;所以只能使用POI进行自定义读取&#xff0c;但是发现数据量大之后&#xff0c;读取数据非常耗时。后面换成EasyExcel&#xff0c;性能起飞。 1. Excel样板 如上图&#xff0c;需要…
阅读更多...
USB - 笔记

USB - 笔记

1.USB接口区分 2 充电宝 图中提到的各种充电协议都是用于快速充电技术的标准，适用于不同品
阅读更多...
Chrome 浏览器插件获取网页 window 对象（方案三）

Chrome 浏览器插件获取网页 window 对象（方案三）

前言 最近有个需求&#xff0c;是在浏览器插件中获取 window 对象下的某个数据&#xff0c;当时觉得很简单&#xff0c;和 document 一样&#xff0c;直接通过嵌入 content_scripts 直接获取&#xff0c;然后使用 sendMessage 发送数据到插件就行了&#xff0c;结果发现不是这…
阅读更多...
JAMA network open|自动化定量评估胃肠道肿瘤中三级淋巴结构的机器学习模型｜文献精析·24-09-07

JAMA network open|自动化定量评估胃肠道肿瘤中三级淋巴结构的机器学习模型｜文献精析·24-09-07

小罗碎碎念 这篇文章报道了一种基于机器学习模型的自动化方法&#xff0c;用于在常规组织病理学图像中检测和分类胃肠道癌症中的三级淋巴结构&#xff0c;并验证了其与患者生存预后的关联。 在这项多中心诊断/预后研究中&#xff0c;开发了一种基于机器学习的计算工具&#xff…
阅读更多...
【pyhton】python如何实现将word等文档中的文字转换成语音

【pyhton】python如何实现将word等文档中的文字转换成语音

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…
阅读更多...
数据结构基本知识

数据结构基本知识

一、什么是数据结构 1.1、组织存储数据 ---------》内存&#xff08;存储&#xff09; 1.2、研究目的 如何存储数据&#xff08;变量&#xff0c;数组....)程序数据结构算法 1.3、常见保存数据的方法 数组&#xff1a;保存自己的数据指针&#xff1a;是间接访问已经存在的…
阅读更多...
移远通信高端5G智能模组SG560D-NA率先通过PTCRB认证

移远通信高端5G智能模组SG560D-NA率先通过PTCRB认证

近日&#xff0c;移远通信宣布&#xff0c;其基于高通QCM6490平台打造的高端5G智能模组SG560D-NA顺利通过PTCRB认证。 在此之前&#xff0c;该模组还获得了美国FCC和加拿大IC认证&#xff0c;这意味着&#xff0c;其已完全满足北美地区的相关标准和规定&#xff0c;能够支持相关…
阅读更多...
【AI大模型应用开发】2.1 Function Calling连接外部世界 - 入门与实战（1）

【AI大模型应用开发】2.1 Function Calling连接外部世界 - 入门与实战（1）

Function Calling是大模型连接外部世界的通道&#xff0c;目前出现的插件&#xff08;Plugins &#xff09;、OpenAI的Actions、各个大模型平台中出现的tools工具集&#xff0c;其实都是Function Calling的范畴。时下大火的OpenAI的GPTs&#xff0c;原理就是使用了Function Cal…
阅读更多...
C++ | Leetcode C++题解之第355题设计推特

C++ | Leetcode C++题解之第355题设计推特

题目&#xff1a; 题解&#xff1a; class Twitter {struct Node {// 哈希表存储关注人的 Idunordered_set<int> followee;// 用链表存储 tweetIdlist<int> tweet;};// getNewsFeed 检索的推文的上限以及 tweetId 的时间戳int recentMax, time;// tweetId 对应发送…
阅读更多...
828华为云征文 | 华为云Flexus X实例上实现Docker容器的实时监控与可视化分析

828华为云征文 | 华为云Flexus X实例上实现Docker容器的实时监控与可视化分析

Docker容器监控之 CAdvisorInfluxDBGranfana 需要了解 本文章主要讲述在 华为云Flexus X 实例上搭建开源的容器管理平台&#xff0c;使用的Web UI界面来简化和优化容器及集群的管理和监控选择合适的云服务器&#xff1a; 本文采用的是 华为云服务器 Flexus X 实例&#xff08;…
阅读更多...
Prefetch文件分析

Prefetch文件分析

目录 介绍步骤 介绍 Prefetch&#xff08;预读取&#xff09;&#xff0c;从Windows XP开始引入&#xff0c;用来加速应用程序启动过程。Prefetch包含可执行文件的名称、文件时间戳、运行次数、上次执行时间、Hash等。Win7上记录最近128个可执行文件的信息&#xff0c;Win8-10…
阅读更多...
正点原子STM32F103+ESP8266+DS18B20+DHT11连接阿里云

正点原子STM32F103+ESP8266+DS18B20+DHT11连接阿里云

文章目录 MQTT协议1. 基础知识2. 报文形式3. 连接报文4. 心跳报文5. 订阅报文5.1. 订阅主题报文SUBSCRIBE5.2. 订阅确认SUBACK5.3. 取消订阅UNSUBSCRIBE5.4. 取消订阅确认UNSUBACK 6. 发布报文6.1. 发布消息PUBLISH6.2. 发布确认PUBACK 7. 阿里云账号创建8. 网络调试助手接入阿…
阅读更多...
Java | Leetcode Java题解之第389题找不同

Java | Leetcode Java题解之第389题找不同

题目&#xff1a; 题解&#xff1a; class Solution {public char findTheDifference(String s, String t) {int ret 0;for (int i 0; i < s.length(); i) {ret ^ s.charAt(i);}for (int i 0; i < t.length(); i) {ret ^ t.charAt(i);}return (char) ret;} }
阅读更多...
Matplotlib 颜色设置详解

Matplotlib 颜色设置详解

在使用matplotlib进行颜色绘制的时候,如绘制图表、背景色或者对文字设置的时候都可以配置颜色, 以下说明主流的三种颜色使用方法 颜色名称 可以是直接使用颜色名称的字符串对color进行赋值,包括可以使用首字母缩写或者完整拼写的形式,以下为部分颜色的书写形式 缩写版 • …
阅读更多...
Spring Boot 多数据源配置（JPA）

Spring Boot 多数据源配置（JPA）

目录 前言 前置环境 pom yml Entity Dao Config Controller 演示 前言 一般一个系统至少有一个数据源&#xff0c;用来持久化业务数据以及查询。单个数据源的系统很常见&#xff0c;在 Spring Boot 框架下配置也很简单。在约定大于配置这个思想下&#xff0c;只需要在…
阅读更多...
递推，CF 353D - Queue

递推，CF 353D - Queue

目录 一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 二、解题报告 1、思路分析 2、复杂度 3、代码详解 一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 353D - Queue 二、解题报告 1、思路分析 手玩一下&#xff0c;我们发现相…
阅读更多...
[数据集][目标检测]人脸口罩佩戴目标检测数据集VOC+YOLO格式8068张3类别

[数据集][目标检测]人脸口罩佩戴目标检测数据集VOC+YOLO格式8068张3类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;8068 标注数量(xml文件个数)&#xff1a;8068 标注数量(txt文件个数)&#xff1a;8068 标注…
阅读更多...
uniapp写的一个年月日时分秒时间选择功能

uniapp写的一个年月日时分秒时间选择功能

代码: <template><view><picker mode"multiSelector" :value"multiIndex" :range"multiRange" change"onMultiChange"><view class"picker">当前选择&#xff1a;{{ formattedDateTime }}</vie…
阅读更多...
VisualStudio环境搭建C++

VisualStudio环境搭建C++

Visual Studio环境搭建 说明 C程序编写中&#xff0c;经常需要链接头文件(.h/.hpp)和源文件(.c/.cpp)。这样的好处是&#xff1a;控制主文件的篇幅&#xff0c;让代码架构更加清晰。一般来说头文件里放的是类的申明&#xff0c;函数的申明&#xff0c;全局变量的定义等等。源…
阅读更多...
最新文章

Copyright @ 2022~2023