加权图数据库推荐 [英] Weighted graph database recommedations

问题描述

如何快速搜索加权图中的k条最短路径?关键字搜索节点是一个加号，但是可以在外部完成.主要关注的问题是有效地寻找节点之间的最佳路径.

What would be a good database for fast search of the k shortest paths in a weighted graph? Keyword search for nodes would be a plus, but that could be done externally. The main concern is efficiently searching for the best paths between nodes.

推荐答案

此问题已有近四年的历史了，自发布此问题以来，图形数据库的世界已经走了很长一段路.几种产品可能可以有效地执行此搜索.我将提供一个示例，说明如何使用Objectivity/DB来执行此搜索.

This post is nearly four years old and the world of graph databases has come a long way since this question was posted. Several products could probably perform this search efficiently. I will provide an example of how Objectivity/DB could be used to perform this search.

Objectivity/DB是基于模式的对象/图形数据库，具有一组完整的图形导航查询功能.它具有自己的DO查询语言.

Objectivity/DB is a schema-based object/graph database with a complete set of graph navigational query capabilities. It has its own DO Query Language.

让我们从这张城镇和道路的图像上绘制一个图形:

Let's build a graph from this image of towns and roads:

让我们按照以下方式创建架构:

Let's create our schema as follows:

UPDATE SCHEMA { 
    CREATE CLASS Town  {
        name        : STRING,               
        from        : List { Element: 
                        Reference { EdgeClass: Road, EdgeAttribute: from }, 
                        CollectionTypeName: TreeListOfReferences 
                    },
        to          : List { Element: 
                        Reference { EdgeClass: Road, EdgeAttribute: to }, 
                        CollectionTypeName: TreeListOfReferences 
                    }       
    }
        
    CREATE CLASS Road {
        distance    : INTEGER { Storage: B32 }, 
        from        : Reference { referenced: Town, Inverse: to },
        to          : Reference { referenced: Town, Inverse: from }
    }
};

然后我们可以加载数据以匹配上图:

And then we can load our data to match the picture above:

let townA = create Town { name: "TownA" };
let townB = create Town { name: "TownB" };
let townC = create Town { name: "TownC" };
let townD = create Town { name: "TownD" };
let townE = create Town { name: "TownE" };
let townF = create Town { name: "TownF" };
let townG = create Town { name: "TownG" };
let townH = create Town { name: "TownH" };

let roadAB = create Road { distance: 4, from: $townA, to: $townB };
let roadBC = create Road { distance: 5, from: $townB, to: $townC };
let roadCH = create Road { distance: 10, from: $townC, to: $townH };
let roadAD = create Road { distance: 3, from: $townA, to: $townD };
let roadDC = create Road { distance: 6, from: $townD, to: $townC };
let roadDH = create Road { distance: 8, from: $townD, to: $townH };
let roadAE = create Road { distance: 4, from: $townA, to: $townE };
let roadED = create Road { distance: 2, from: $townE, to: $townD };
let roadEF = create Road { distance: 4, from: $townE, to: $townF };
let roadFG = create Road { distance: 3, from: $townF, to: $townG };
let roadGH = create Road { distance: 10, from: $townG, to: $townH };
let roadDG = create Road { distance: 8, from: $townD, to: $townG };

现在我们需要定义体重计算器运算符:

Now we need to define our weight calculator operator:

CREATE WEIGHT CALCULATOR shortestRoute {
    minimum:    0,
    default:    0, 
    edges: {
        ()-[r:Road]->(): r.distance
    }
};

Objectivity/DB在其他图形数据库中是唯一的，因为它允许您定义多个权重计算器，这些计算器可以计算边缘属性或同一数据集中各种简单或复杂因素的边缘权重.您无需将权重作为属性嵌入数据中.

Objectivity/DB is unique from other graph databases because it allows you to define multiple weight calculators that can calculate an edge weight on an attribute of an edge or on a variety of simple or complex factors across the same dataset. You do not need to embed the weight as an attribute in the data.

最后是我们的查询:

MATCH m = LIGHTEST shortestRoute 
           ((:Town {name == 'TownA'})-[*]->(:Town {name == 'TownH'})) 
RETURN m;

运行此查询将为我们提供以下结果:

Running this query gives us the following results:

DO> MATCH m = LIGHTEST  shortestRoute ((:Town {name == 'TownA'})-[*]->(:Town {name == 'TownH'})) RETURN m;

{
  _Projection
  {
    m:WALK
    {
      length:2,
      weight:11.0000,     <-----This is the weight of the shortest path.
      edges:
      {
        EDGE
        {
          weight:3.00000,
          from:3-3-1-4,           <--- This is the object id of TownA
          fromClass:'Town',
          attribute:'to',
          edgeData:3-3-1-35,
          edgeDataClass:'Road',
          to:3-3-1-10,             <--- This is the object id of TownD
          toClass:'Town'
        },
        EDGE
        {
          weight:8.00000,
          from:3-3-1-10,             <--- This is the object id of TownD
          fromClass:'Town',
          attribute:'to',
          edgeData:3-3-1-41,
          edgeDataClass:'Road',
          to:3-3-1-18,             <--- This is the object id of TownH
          toClass:'Town'
        }
      }
    }
  }
}

最后，我们可以找到k条最短路径.这有点困难，因为使用Objectivity的DO查询语言时，我们必须猜测最重路径的最大权重，并在MAX WEIGHT子句中使用它.就我而言，我使用25.0作为权重值，大于图表中的任何路径权重.

Finally, we can find the k shortest paths. This is a little harder because with Objectivity's DO query language we have to make a guess as to the maximum weight for the heaviest path and use that in the MAX WEIGHT clause. In my case I am using 25.0 as the weight value greater than any path-weight in the graph.

查询如下:

MATCH m = MAX WEIGHT 25.0 routeDistance 
          ((:Town {name == 'TownA'})-[*]->(:Town {name == 'TownH'})) 
          order by weight(m) asc take 3 
          RETURN m

我们可以稍微修改查询，仅返回权重:

We can modify the query slightly and only return the weights:

MATCH m = MAX WEIGHT 25.0 routeDistance 
          ((:Town {name == 'TownA'})-[*]->(:Town {name == 'TownH'})) 
          order by weight(m) asc take 3 
          RETURN weight(m);

{
  _Projection
  {
    weight(m):11.0000
  },
  _Projection
  {
    weight(m):14.0000
  },
  _Projection
  {
    weight(m):19.0000
  }
}

这篇关于加权图数据库推荐的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！