java - 图算法 - 寻求提高可扩展性

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 表示中的内容的任何其他信息。

如果您想分别计算每条路径的内容，或者计算所有路径的总和/最小值/最大值之类的值，也可以使用 DAG 本身来完成。

如果您坚持保存单独的路径，一种选择是将您的 DAG 转换为 Trie 的变体。 .另一种选择是使用 Lempel-Ziv 的某些变体。表示。这取决于您的 DAG 类型，以及您希望如何处理路径信息。