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

Question

我编写了一个算法来计算和存储 DAG 的所有路径，并且它在小图上运行得很好 - 但现在我正在寻求提高它在较大图上运行的效率。该算法的核心逻辑在下面的 createSF() 和 makePathList() 中，其他方法是帮助器 - 我可以看到追加是一个瓶颈。然而，我想最大的帮助是设计一个可以在字典中存储路径的数据结构，因为许多路径是由其他路径组成的，这是我问题的关键。

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< 的变体/a>.另一种选择可能是使用 Lempel- 的某些变体Ziv 表示。这取决于您的 DAG 类型以及您希望如何处理路径信息。

Answer 2

看一下 Graphviz 的 DOT 源代码，它可能会给你一些想法。

Answer 3

请允许我首先提出两条（希望有帮助的）评论：

我在理解您的代码时遇到了一些困难，因为某些方法名称误导了我。从名字上看，我期待的是别的东西。我可以建议一些重构吗：（

makePathList -> createPathList  // you actually create a List here
append -> createPathList // yes, same name as above because it creates the same
                         // type of list, just with different parameters

删除了在 Robert 编辑后变得过时的部分答案）

正如 Margus 所说，用 StringBuilder 附加链替换字符串连接并不会提高性能。无论如何，编译器可能会优化 String 串联到 StringBuilder 附加（我见过这样的字节代码）。

您可以尝试将 DAG 转换为树结构。引入一个不可见的根，将所有节点作为直接子节点。现在，为每个节点添加它的后继节点（子节点和/或同级节点）。现在叶子的数量应该等于路径的数量，并且从根到任何叶子的每个图都是 DAG 中的一条路径。

编辑

一个小改进 - 它是微优化，但至少会留下更少的垃圾：

private List<String> append(String node, List<String> allPathsStartingAfterNode) {
    List<String> allPathsStartingAtNode = new ArrayList<String>();
    String nodeWithSeparator = node + "/";

    for (String aPathStartingAfterNode : allPathsStartingAfterNode) {
        allPathsStartingAtNode.add(nodeWithSeparator + aPathStartingAfterNode);
    }

    return allPathsStartingAtNode;
}

Answer 4

一个简单的修改（取决于您如何使用数据）可能是延迟加载路径，这样如果您倾向于只使用几个路径，您甚至永远不会生成一些路径。

当然，这完全取决于预期用途