graph-databases - 加权图数据库推荐

Question

什么是快速搜索加权图中 k 条最短路径的好数据库？节点的关键字搜索将是一个加号，但这可以在外部完成。主要关注的是有效地搜索节点之间的最佳路径。

Answer 1

这篇文章已有将近四年的历史，自从发布这个问题以来，图形数据库的世界已经取得了长足的进步。有几种产品可能可以有效地执行此搜索。我将提供一个示例，说明如何使用 Objectivity/DB 来执行此搜索。

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

让我们根据这张城镇和道路的图像构建一个图表:

让我们按如下方式创建我们的架构:

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 }
    }
};

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

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 };

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

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

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

最后是我们的查询:

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

运行此查询会得到以下结果:

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 作为大于图中任何路径权重的权重值。

查询如下:

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

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

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
  }
}