通过元素确定路径

Question

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

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) {
        /// ....
    }

}

null

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

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