找到从源到目标覆盖所有边的所有可能路径集

Question

我有一个有向图。我想找到从源到目标的所有可能路径，覆盖所有转换。这与“覆盖所有顶点的所有可能路径”不同。该图将正好有一个起始顶点，并且可能有多个结束顶点。如果没有传出转换，则节点是结束节点。集合中的路径可能具有重复的变换，但不能具有重复的顶点。附有一个示例有向图。顶点a（黑色）是起始顶点，顶点e和f是结束节点（黄色）。此图的解决方案如下所示。

a-f
a-b-f
a-b-c-e
a-b-c-d-e
a-b-c-d-b-f

您可以看到最后一条路径有两次b。这是有效的。i、 例如，一条路径可以多次具有相同的顶点。相应的转换为

t18
t1-t7
t1-t2-t3
t1-t2-t4-t5
t1-t2-t4-t6-t7

您可以看到，没有路径具有重复的变换。我需要一个java程序来做到这一点。我写了一个程序来解决这个问题。但它给出了所有没有重复顶点的路径。因此，我丢失了一些边，尽管它覆盖了所有节点。下面给出了我编写的代码

private Stack<Vertex> path = new Stack<Vertex>(); // the current path
private Set<Vertex> onPath = new HashSet<Vertex>(); // the set of vertices
public void AllPaths(Vertex s) {
    enumerate2(s);
}

private void enumerate(Vertex v) {
    // add node v to current path from source
    path.push(v);
    onPath.add(v);
    if (v.getOutgoings().size() == 0) {
        printPath(path);
        addToRawPaths(path);
    }

    // consider all neighbors that would continue path with repeating a node
    else {
        EList<Transition> ts = v.getOutgoings();
        for (Transition w : ts) {
            if (!onPath.contains(w.getTarget())) { // !onPath.contains(w.getTarget())
                enumerate(w.getTarget());
            }
        }
    }

    // done exploring from v, so remove from path
    path.pop();
    onPath.remove(v);
}

使用这个，我可以

a-f
a-b-f
a-b-c-e
a-b-c-d-e

但是我需要像我上面描述的那样的东西。你可以假设我在这段代码中使用的这些api，或者你可以实现新的。甚至psudocode也可以。我需要解决方案来应用于基于模型的测试工具以生成测试用例。非常感谢。

Answer 1

当前，当您找到已包含在onPath中的顶点时，将停止枚举。这不应该是你的规则。相反，当当前路径上相继存在currentVertex、nextCandidateVertex和w.getTarget（）对时，应该停止枚举。

为了实现这一点，我将使用HashSet

实际上，您可以使用path堆栈实现相同的功能，但查找现有对可能需要O（n）VS摊销O（1），并使用HashSet的建议方法