java - 确定通过元素的路径

Question

我有一个类 Item，它使用一个字符作为标识符。

public class Item {

    private char identifier;
    private Set<Character> predecessors;
    private Set<Character> successors;

    // Constructor, getters and setters...

}

我希望能够检索由Path类表示的路径，其中包含一个简单的有序列表Item：

public class Path {

    private List<Item> items;

    // Constructor, getters and setters 

}

为了存储和管理我的项目和路径，我使用了一个专门的类。它包含两个Set包含这些类型中的每一个。我可以使用其标识符检索任务。

public class SimpleClass {

    private Set<Item> items;
    private Set<Path> paths;

    // Constructor, getters and setters

    public Optional<Item> getItemById(char identifier) {
        /// ....
    }

}

我想创建一个方法来返回一个Set包含每个Path但我做不到的方法。欢迎提供一点帮助。一个小例子来说明我的观点：

• D 和 E 是 G 的前件
• G 是 D 和 E 的继任者
• A、B、D、G、J、K 是一条路径
• A、C、F、H、J、K 是一条路径

更新/注意：我正在寻找通过一组项目构建路径

标签： java

Answer 1

一种快速而肮脏的递归算法。我只是创建了第一个地图来加快项目检索。看看它是否有效，尝试理解它并改变它。

/**
 * Build all paths
 */
public void buildPaths() {
    Map<Character,Item> itemsByID=new HashMap<>();
    for (Item i:items) {
        itemsByID.put(i.getIdentifier(), i);
    }
    List<Item> starts=items.stream().filter(i->i.getPredecessors().isEmpty()).collect(Collectors.toList());
    for (Item st:starts) {
        Path p=new Path();
        p.getItems().add(st);
        buildPath(p,itemsByID);
    }
}

/**
 * Build the next step of the given path
 * @param p
 * @param itemsByID
 */
private void buildPath(Path p,Map<Character,Item> itemsByID) {
    Item last=p.getItems().get(p.getItems().size()-1);
    Set<Character> successors=last.getSuccessors();
    // no successor, path is finished, add to collection
    if (successors.isEmpty()) {
        paths.add(p);
    // one successor continue on same path
    } else if (successors.size()==1){
        p.getItems().add(itemsByID.get(successors.iterator().next()));
        buildPath(p,itemsByID);
    } else {
        // multiple successors, create a new path for each branch
        for (Character c:successors) {
            Path p1=new Path();
            p1.getItems().addAll(p.getItems());
            p1.getItems().add(itemsByID.get(c));
            buildPath(p1, itemsByID);
        }
    }
}