在 Java 中使用 Gremlin 返回唯一路径

Question

我遇到了 Gremlin 返回重复路径的问题，我想知道是否有人可以帮助我。我是 Gremlin 的新手，所以如果我犯了任何简单的错误，我深表歉意。

我的数据库的一种简单形式由超过 50 个节点和超过 5000 条边组成，其中边被认为是单向的，但是在两个节点之间可能存在双向的边，从而导致循环结构（因此节点 A -> B - > A)，同样你可以有 (A -> B -> C -> A).

我想要完成的是遍历网络，返回起始节点和结束节点之间的每条唯一路径，它没有循环。下面是我的代码示例。

final List<List> paths = new ArrayList<List>();
String endNodeID = endNode.getVertex().getId().toString();
new GremlinPipeline<Vertex, ArrayList<Vertex>>(startNode.getVertex())
    .as("x").out("OutboundLink").simplePath()
    .loop("x", new PipeFunction<LoopPipe.LoopBundle<Vertex>, Boolean>() {
                @Override
                public Boolean compute(final LoopPipe.LoopBundle<Vertex> loopBundle) {
                    return loopBundle.getLoops() <= 8;
                }
            }, new PipeFunction<LoopPipe.LoopBundle<Vertex>, Boolean>() {
                @Override
                public Boolean compute(final LoopPipe.LoopBundle<Vertex> loopBundle) {
                    return endNodeID.equals(loopBundle.getObject().getId().toString());
                }
            }).simplePath().filter(new PipeFunction<Vertex, Boolean>() {

                @Override
                public Boolean compute(final Vertex arg0) {
                    return targetId.equals(arg0.getId().toString());
                }
            }).path(new PipeFunction<Vertex, String>() {
                @Override
                public String compute(final Vertex vertex) {
                    return vertex.getId().toString();
                }
            }).fill(paths);

我相信它的作用

获取起始顶点
将位置声明为 X
关注 X 的所有出站链接
删除任何带循环的路径（例如 A -> B-> C -> D-> B-> E）
循环回到 X 最多 8 次，但是如果一条路径到达结束节点，则停止该路径进一步前进。
重新检查循环路径。
在 endNode 处对路径进行过滤。
填充列表。

从这里我目前得到以下不需要的行为 - 重复路径 - 到达 endNodeID 但继续的路径。

虽然之后我可以在代码中更正此问题（在一个模拟中，它从 10000 条路径更正为仅 200 条路径），但这看起来确实是一种资源浪费。

如有任何帮助，我们将不胜感激。

Answer 1

对于 Titan 0.5.4，我也从未 simplePath() 为我工作。 API 文档表明它的目的是检测和过滤掉循环路径，但对我来说可能是一种误解。我最终得到的是编写自己的循环检测代码。

示例图：

            +--+        
     +------+V1+------+ 
     |      +--+      | 
     v                | 
              ^       | 
     +--+     |       v 
     |V2+-----+          
     |  |            +--+
     +--+ <----------+V3|
     |               ++-+
     |                | 
     |                | 
     |                | 
     |      +--+      | 
     +----> |V4| <----+ 
            +--+

以下代码生成路径

v1->v2->v4
v1->v3->v4
v1->v3->v2->v4

Gremlin 管道：

public static List<List<Element>> findPathsBetweenSimple(final Vertex from, final Vertex to) {
    final Object endID = to.getId();
    GremlinPipeline<Vertex, List<Element>> pipe = new GremlinPipeline<>(from);
    pipe.as("startAt")
            .out()
            .loop("startAt", new PipeFunction<LoopBundle<Vertex>, Boolean>() {
                @SuppressWarnings("unchecked")
                @Override
                public Boolean compute(LoopBundle<Vertex> lb) {
                    Boolean doContinue = Boolean.TRUE;
                    LOG.trace("Loop cnt: " + lb.getLoops() + "; Vertex: " + lb.getObject());
                    if (containsLoop(lb.getPath(), lb.getObject())) {
                        LOG.debug("Loop detected in path. Aborting. " + lb.getPath());
                        doContinue = Boolean.FALSE;
                    } else if (endID.equals(lb.getObject().getId())) {
                        LOG.debug("Path found: " + lb.getPath() + ", " + lb.getObject());
                        doContinue = Boolean.FALSE;
                    }
                    return doContinue;
                }
            })
            .has("id", endID)
            .path();
    return pipe.toList();
}

循环检测：

private static boolean containsLoop(final List<Element> path, Vertex current) {
    boolean loopDetected = false;

    final List<Vertex> vPath = new ArrayList<>();
    for (Element element : path) {
        if (element instanceof Vertex) {
            vPath.add((Vertex) element);
        }
    }
    vPath.add(current);

    for (Vertex v : vPath) {
        if (Collections.frequency(vPath, v) > 1) {
            loopDetected = true;
            break;
        }
    }

    return loopDetected;
}

在 Java 中使用 Gremlin 返回唯一路径

Returning unique paths with Gremlin in Java

java

groovy

gremlin