遍历有向网格链路实现

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

复杂链路示意图如下：

复杂网路链路场景描述

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));
    }
}

运行结果：

截图红框就是本文示意图的所有链路。