图算法 - 希望提高可扩展性

Question

我编写了一个算法来计算和存储DAG的所有路径,它在小图上运行得很好 - 但现在我希望提高它在大图上运行的效率.该算法的核心逻辑在下面的createSF()和makePathList()中,其他方法是帮助器 - 我可以看到append是一个瓶颈.但是,我想最大的帮助是设计一个可以在字典中存储路径的数据结构,因为许多路径都是由其他路径组成的,这是我的问题的症结所在.

private Multiset<String> paths = new Multiset<String>();    

public Multiset<String> createSF(DAGNode n) {

    for (DAGNode succ : n.getSuccessors())
        createSF(succ);
    if (!n.isVisited())
        for (String s : makePathList(n)) 
            paths.put(s);

    n.setVisited(true);
    return paths;
}

private List<String> makePathList(DAGNode n) {
    List<String> list = new ArrayList<String>();

    list.add(n.getLabel());
    for (DAGNode node : n.getSuccessors())
        list.addAll(append(n.getLabel(), makePathList(node)));

return list;
}

private List<String> append(String s, List<String> src) {
    List<String> ls = new ArrayList<String>();
    for (String str : src) 
    ls.add(s + "/" + str);

    return ls;
}

编辑:

我现在使用路径对象来表示路径,并将瓶颈针对这两种方法:

public List<Path> createPathList(Tree n) {
    List<Path> list = new ArrayList<Path>();
    list.add(new Path(n.getNodeName()));
    for (Tree node : n.getSuccessors()) {
        list.addAll(append(n.getNodeName(), createPathList(node)));
    }
    return list;
}

public List<Path> append(String s, List<Path> src) {
    List<Path> ls = new ArrayList<Path>();
    for (Path path : src) {
        ls.add(new Path(path, s));
    }
    return ls;
}

麻烦的是,当图形大小为M时,这些方法将被调用M次,这意味着这里创建了很多列表...是否有更有效的方法来构建createPathList()的返回值？

Answer 1

为了回答这个问题,有必要了解为什么需要路径列表.路径列表不会为您提供有关DAG表示中的内容的任何其他信息.

如果要分别计算每条路径的内容,或者计算所有路径上的sum/min/max之类的东西,也可以使用DAG本身来完成.

如果您坚持保存单独的路径,则可以选择将DAG转换为Trie的变体.另一种选择可能是使用Lempel-Ziv表示的一些变体.这取决于您的DAG类型,以及您对路径信息的期望.