ArangoDB：すべての最短経路を見つける

Question

2頂点間の最短経路をすべて取得したい。

例：

LET source = (FOR x IN Entity FILTER x.objectID == "organization_1" 
    return x)[0] 
LET destination = (FOR x IN Entity FILTER x.objectID == "organization_129" 
    return x)[0] 
FOR node, edge, path IN 1..2 ANY source._id GRAPH "m" 
    FILTER LAST(path.vertices)._id == destination._id 
    LIMIT 100 
RETURN path 

問題：私のノードAとBの間のすべての最短経路を与えるだけで2つのブルーパス

を返す必要がありますこれは私がこれまで持っているものです。 1.非常に遅いです（70 mioノードのようなグラフでは18秒かかります）。 2.すべてのパスが見つかりますが、すべてが欲しいだけです最短パス

更新 私はコメントから2段階クエリソリューションを試しました。 問題は、2番目のクエリにも非常に遅い

Query string: 
FOR source IN Entity FILTER source.objectID == "organization_1" 
LIMIT 1 
FOR node, edge, path 
    IN 1..@depth ANY source._id 
    GRAPH "m" 
    OPTIONS {uniqueVertices: "path"} 
    FILTER node.objectID == "organization_129" 
    RETURN path 

Execution plan: 
Id NodeType   Est. Comment 
    1 SingletonNode  1 * ROOT 
11 IndexNode   1  - FOR source IN Entity /* hash index scan */ 
    5 LimitNode   1  - LIMIT 0, 1 
    6 CalculationNode  1  - LET #6 = source.`_id` /* attribute expression */ /* collections used: source : Entity */ 
    7 TraversalNode  346  - FOR node /* vertex */, path /* paths */ IN 1..2 /* min..maxPathDepth */ ANY #6 /* startnode */ GRAPH 'm' 
    8 CalculationNode 346  - LET #10 = (node.`objectID` == "organization_129") /* simple expression */ 
    9 FilterNode   346  - FILTER #10 
10 ReturnNode   346  - RETURN path 

Indexes used: 
By Type Collection  Unique Sparse Selectivity Fields      Ranges 
11 hash Entity   false false  100.00 % [ `objectID` ] (source.`objectID` == "organization_1") 
    7 edge ACTIVITYPARTY false false  100.00 % [ `_from`, `_to` ]   base INBOUND 
    7 edge ACTIVITYPARTY false false  100.00 % [ `_from`, `_to` ]   base OUTBOUND 
    7 edge ACTIVITY_LINK false false  100.00 % [ `_from`, `_to` ]   base INBOUND 
    7 edge ACTIVITY_LINK false false  100.00 % [ `_from`, `_to` ]   base OUTBOUND 
    7 edge ENTITY_LINK  false false  70.38 % [ `_from`, `_to` ]   base INBOUND 
    7 edge ENTITY_LINK  false false  70.38 % [ `_from`, `_to` ]   base OUTBOUND 
    7 edge RELATION  false false  20.49 % [ `_from`, `_to` ]   base INBOUND 
    7 edge RELATION  false false  20.49 % [ `_from`, `_to` ]   base OUTBOUND 
    7 edge SOFT_LINK  false false  100.00 % [ `_from`, `_to` ]   base INBOUND 
    7 edge SOFT_LINK  false false  100.00 % [ `_from`, `_to` ]   base OUTBOUND 

Traversals on graphs: 
Id Depth Vertex collections      Edge collections             Options         Filter conditions 
    7 1..2 Activity, Entity, SOFT_LINK, Property ACTIVITYPARTY, ENTITY_LINK, SOFT_LINK, RELATION, ACTIVITY_LINK uniqueVertices: path, uniqueEdges: path 

Optimization rules applied: 
Id RuleName 
    1 move-calculations-up 
    2 move-filters-up 
    3 move-calculations-up-2 
    4 move-filters-up-2 
    5 use-indexes 
    6 remove-filter-covered-by-index 
    7 remove-unnecessary-calculations-2 
    8 optimize-traversals 
    9 move-calculations-down 

Answer 1

であることをあなたが頻繁にあなたのパフォーマンスが遅くなり、完全なコレクションのスキャンを回避するために、コレクションEntityにフィールドobjectID上のハッシュインデックスを必要とするすべての最初のです。

最短パスをすべて取得するには、最初にAQL SHORTEST_PATHを使用して1つの最短パスを検索し、訪問された頂点の数を返します。サブクエリは必要ありません（クエリのように）。その後

FOR source IN Entity FILTER source.objectID == "organization_1" 
LIMIT 1 
FOR destination IN Entity FILTER destination.objectID == "organization_129" 
LIMIT 1 
RETURN sum(
    FOR v, e 
    IN ANY 
    SHORTEST_PATH source._id TO destination._id 
    GRAPH "m" 
    RETURN 1)-1 

Iは、トラバーサルの深さを制限するために使用されるバインド・パラメータ@depth、として最初のクエリからの結果と別のクエリを実行することになります。

FOR source IN Entity FILTER source.objectID == "organization_1" 
LIMIT 1 
FOR node, edge, path 
    IN 1..@depth ANY source._id 
    GRAPH "m" 
    OPTIONS {uniqueVertices: "path"} 
    FILTER node.objectID == "organization_129" 
    RETURN path 

注：それはすでに最後の頂点（同じことがedgeに適用される）であるので、あなたは、単にnodeを使用することができ、あなたがLAST(path.vertices)を使用する必要はありませんパスの最後の頂点をフィルタリングするために。