当前位置：首页 > news >正文

遍历有向网络链路实现

news 来源：原创 2024/9/19 15:12:41

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

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

复杂网路链路场景描述

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

程序如何算出所有链路？

设计思路：

节点场景：

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

在这里插入图片描述

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

@Data
public class LinkItem {// 该节点IDprivate 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));}
}