寻找排除特定边缘的最短路径？ [英] finding shortest path that excludes particular edges?

问题描述

我使用Py2neo，但这可能并不重要，因为这很可能需要通过编写Cypher查询来完成。

基本上，我想要在子图中寻找最短路径，其中子图是整个图中的大部分，但是边的一小部分（百万分之一或更少）被删除。

例如，假设我有节点A，B和C以及边（A-> B），（A-> C），（B-> C）。当然，从A到C的最短路径是通过直接连接。但是如果我想找到不使用该边的最短路径，它必须是AB C。

另外，这个将是用户可以在多用户（网络）应用程序中指定的内容。所以我无法真正改变数据库本身......如果这不是问题，我可以在边缘allow：true / false上创建一个属性并将其设置为false，但这会混淆应用程序行为所有当前用户。

其中的一个变体是不允许：sessionID1，sessionID230，sessionID1010，即实际存储哪些应用程序会话想要排除当然，我实际上可以通过从neo4j获得所需的节点并将它们保留在队列中来实现BFS在Python中的实现。而不是让neo4j做搜索，但肯定会慢得多，对吧？

有什么想法？谢谢

编辑：请求查看代码。

以下是我目前如何获得最短路径我首先在索引中查找两个节点。现在图像还有一个边缘列表（即唯一关系），必须在最短路径搜索中被忽略。

 从py2neo导入neo4j 
 
g = neo4j.GraphDatabaseService（）
 
 def shortest_path（a，b）：
a = g.get_indexed_node（worddex，word ，a）
b = g.get_indexed_node（worddex，word，b）
如果不是a和b：返回None 
 query_string =START starting = node（％d），结束=节点（％d）MATCH p = shortestPath（开始 -  [* .. 100] -end）RETURN p％（a._id，b._id）
 result = neo4j.CypherQuery（g，query_string） .execute（）
如果不是len（result）：return None 
p = result [0] .p 
 ret = [] 
 for p.nodes中的节点：$ b​​ $ b ret.append（node [word]）
 return ret 
  

编辑2：示例控制台： http://console.neo4j.org/r/3c1rgn

很容易找到最短的友谊路径b在任何两个人之间，但是如果我们想要找到一个不涉及特定友谊关系（或特定友谊关系）的最短友谊路径，但是如果不首先修改数据库呢？例如，我们想找到从鲍勃到乔的最短的友谊路径，我们暂时假设鲍勃和乔本身不是朋友，也不是爱丽丝和珍妮特。 方案

你不能使用' allShortestPaths '选项，并使用它来拒绝包含一些特定的rel类型或节点类型使用Python的路径？我想这取决于你想要限制结果的方式和参数，以及它们是否可以使用只有cypher以路径形式返回到python的方式来检测。

<另一种方法是指示Cypher将所有可能的路径从一个节点返回到另一个节点（一些智能限制可以在查询本身中应用）。

然后根据Cypher返回的路径集合，可以运行一些Python代码来拒绝包含某种特定的rel类型或者您不感兴趣的节点类型的路径。然后您将留下一个可能的集合符合您的验收标准的路径（除最短条件外）。然后，您可以使用python简单地计算路径的长度并使用最小的路径。

实际上，Cypher本身可以为所有路径返回路径的长度。
这已经被问过，所以这里是一个问题供您参考。这个问题被接受的答案是我正在谈论的。

I'm using Py2neo, but that probably doesn't matter since this will most likely need to be done by writing a Cypher query.

Essentially, I want to find a shortest path in a subgraph, where the subgraph is most of the whole graph but with a very small fraction (a millionth or less) of the edges removed.

For example, say I have nodes A, B, and C, and edges (A->B), (A->C), (B->C). Of course, the shortest path from A to C is via the direct connection. But if I wanted to find the shortest path that doesn't use that edge, it would have to be A B C.

Also, this will be something that a user can specify in a multi-user (web) application. So I can't really alter the database itself...if that weren't an issue, I could maybe create a property on edges "allow: true/false" and set it to false, but that would mess with application behavior for all current users.

A variation on that would be to have "disallow: sessionID1, sessionID230, sessionID1010", i.e. actually store which application sessions want to exclude that edge in the edge itself, but this also does not seem ideal.

Of course, I could actually implement the BFS in python by getting nodes as needed from neo4j and keeping them on a queue instead of having neo4j do the search, but surely that would be much slower, right?

Any thoughts? Thanks

EDIT: request to see code.

Below is how I'm currently getting the shortest path between two nodes that I first look up in an index. Now image there's also a list of edges (that is, unique relationships) that have to be ignored in the shortest path search.

from py2neo import neo4j

g = neo4j.GraphDatabaseService()

def shortest_path(a, b):
    a = g.get_indexed_node("worddex", "word", a)
    b = g.get_indexed_node("worddex", "word", b)
    if not a and b: return None
    query_string = "START beginning=node(%d), end=node(%d) MATCH p = shortestPath(beginning-[*..100]-end) RETURN p" % (a._id, b._id)
    result = neo4j.CypherQuery(g, query_string).execute()
    if not len(result): return None
    p = result[0].p
    ret = []
    for node in p.nodes:
        ret.append(node["word"])
    return ret

EDIT 2: example console: http://console.neo4j.org/r/3c1rgn

It's easy to find a shortest "friendship path" between any two people, but what if we want to find a shortest friendship path that doesn't involve a particular friendshi rel (or particular set of friendship rels), but without modifying the database first? e.g., we want to find the shortest friendship path from bob to joe wherein we momentarily assume bob and joe aren't friends themselves, nor are alice and janet.

解决方案

Can't you use the 'allShortestPaths' option in cypher and use it to reject paths which contain some specific rel types or node types using python? I guess it would depend on how and on what parameters you want to restrict results, and whether they can be detected using only what cypher returns to python in the form of a path.

Another way to do it would be to instruct Cypher to return ALL POSSIBLE PATHS from a node to another (some smart restrictions can be applied within the query itself here).

Then based on the collection of paths Cypher returns, you can run some Python code to reject paths which contain, say, a particular rel type or a node type that you are not interested in. You will then be left with a collection of possible paths fitting your acceptance criteria (except the shortest condition). You can then simply calculate the length of the path using python and use the smallest.

In fact, the length of the path can be returned by Cypher itself for all paths. This has already been asked before, so here is the question for your reference. The accepted answer to that question is what I am talking about.

这篇关于寻找排除特定边缘的最短路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！