8000 Further improvements of graph queries. All queries should now be noti… · cloud-coders/arangodb@fad7567 · GitHub
[go: up one dir, main page]
Skip to content

Commit fad7567

Browse files
mchackimchacki
committed
Further improvements of graph queries. All queries should now be noticably faster.
1 parent 47b8ca2 commit fad7567

File tree

7 files changed

+892
-662
lines changed

7 files changed

+892
-662
lines changed

‎js/apps/system/_admin/aardvark/APP/frontend/js/modules/org/arangodb/general-graph.js

Lines changed: 34 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -3485,6 +3485,9 @@ Graph.prototype._absoluteEccentricity = function(vertexExample, options) {
34853485
"ex1": ex1
34863486
};
34873487
var result = db._query(query, bindVars).toArray();
3488+
if (result.length === 1) {
3489+
return result[0];
3490+
}
34883491
return result;
34893492
};
34903493

@@ -3534,6 +3537,9 @@ Graph.prototype._eccentricity = function(options) {
35343537
"options": options
35353538
};
35363539
var result = db._query(query, bindVars).toArray();
3540+
if (result.length === 1) {
3541+
return result[0];
3542+
}
35373543
return result;
35383544
};
35393545

@@ -3624,6 +3630,9 @@ Graph.prototype._absoluteCloseness = function(vertexExample, options) {
36243630
"ex1": ex1
36253631
};
36263632
var result = db._query(query, bindVars).toArray();
3633+
if (result.length === 1) {
3634+
return result[0];
3635+
}
36273636
return result;
36283637
};
36293638

@@ -3682,24 +3691,28 @@ Graph.prototype._closeness = function(options) {
36823691
"options": options
36833692
};
36843693
var result = db._query(query, bindVars).toArray();
3694+
if (result.length === 1) {
3695+
return result[0];
3696+
}
36853697
return result;
36863698
};
36873699

3688-
3689-
36903700
////////////////////////////////////////////////////////////////////////////////
36913701
/// @startDocuBlock JSF_general_graph_absolute_betweenness
36923702
/// @brief Get the
36933703
/// [betweenness](http://en.wikipedia.org/wiki/Betweenness_centrality)
36943704
/// of all vertices in the graph.
36953705
///
3696-
/// `graph._absoluteBetweenness(options)`
3706+
/// `graph._absoluteBetweenness(vertexExample, options)`
36973707
///
36983708
/// The complexity of the function is described
36993709
/// [here](../Aql/GraphOperations.html#the_complexity_of_the_shortest_path_algorithms).
37003710
///
37013711
/// @PARAMS
37023712
///
3713+
/// @PARAM{vertexExample, object, optional}
3714+
/// Filter the vertices, see [Definition of examples](#definition_of_examples)
3715+
///
37033716
/// @PARAM{options, object, optional}
37043717
/// An object defining further options. Can have the following values:
37053718
/// * *direction*: The direction of the edges. Possible values are *outbound*, *inbound* and *any* (default).
@@ -3741,18 +3754,23 @@ Graph.prototype._closeness = function(options) {
37413754
/// @endDocuBlock
37423755
//
37433756
////////////////////////////////////////////////////////////////////////////////
3744-
Graph.prototype._absoluteBetweenness = function(options) {
3757+
Graph.prototype._absoluteBetweenness = function(example, options) {
37453758

37463759
var query = "RETURN"
37473760
+ " GRAPH_ABSOLUTE_BETWEENNESS(@graphName"
3748-
+ ',@options'
3749-
+ ')';
3761+
+ ",@example"
3762+
+ ",@options"
3763+
+ ")";
37503764
options = options || {};
37513765
var bindVars = {
3766+
"example": example,
37523767
"graphName": this.__name,
37533768
"options": options
37543769
};
37553770
var result = db._query(query, bindVars).toArray();
3771+
if (result.length === 1) {
3772+
return result[0];
3773+
}
37563774
return result;
37573775
};
37583776

@@ -3809,6 +3827,9 @@ Graph.prototype._betweenness = function(options) {
38093827
"options": options
38103828
};
38113829
var result = db._query(query, bindVars).toArray();
3830+
if (result.length === 1) {
3831+
return result[0];
3832+
}
38123833
return result;
38133834
};
38143835

@@ -3883,6 +3904,9 @@ Graph.prototype._radius = function(options) {
38833904
"options": options
38843905
};
38853906
var result = db._query(query, bindVars).toArray();
3907+
if (result.length === 1) {
3908+
return result[0];
3909+
}
38863910
return result;
38873911
};
38883912

@@ -3956,6 +3980,9 @@ Graph.prototype._diameter = function(options) {
39563980
"options": options
39573981
};
39583982
var result = db._query(query, bindVars).toArray();
3983+
if (result.length === 1) {
3984+
return result[0];
3985+
}
39593986
return result;
39603987
};
39613988

@@ -4593,7 +4620,7 @@ exports._undirectedRelation = _undirectedRelation;
45934620
/// Deprecated function (announced 2.3)
45944621
exports._directedRelation = function () {
45954622
return _relation.apply(this, arguments);
4596-
} ;
4623+
};
45974624
exports._relation = _relation;
45984625
exports._graph = _graph;
45994626
exports._edgeDefinitions = _edgeDefinitions;

‎js/apps/system/_admin/aardvark/APP/frontend/js/modules/org/arangodb/graph/traversal.js

Lines changed: 155 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -98,6 +98,20 @@ function clone (obj) {
9898
return copy;
9999
}
100100

101+
////////////////////////////////////////////////////////////////////////////////
102+
/// @brief test if object is empty
103+
////////////////////////////////////////////////////////////////////////////////
104+
105+
function isEmpty(obj) {
106+
for(var key in obj) {
107+
if (obj.hasOwnProperty(key)) {
108+
return false;
109+
}
110+
}
111+
return true;
112+
}
113+
114+
101115
////////////////////////////////////////////////////////////////////////////////
102116
/// @brief traversal abortion exception
103117
////////////////////////////////////////////////////////////////////////////////
@@ -1261,6 +1275,136 @@ function dijkstraSearch () {
12611275
};
12621276
}
12631277

1278+
function dijkstraSearchMulti () {
1279+
return {
1280+
nodes: { },
1281+
1282+
requiresEndVertex: function () {
1283+
return true;
1284+
},
1285+
1286+
makeNode: function (vertex) {
1287+
var id = vertex._id;
1288+
if (! this.nodes.hasOwnProperty(id)) {
1289+
this.nodes[id] = { vertex: vertex, dist: Infinity };
1290+
}
1291+
1292+
return this.nodes[id];
1293+
},
1294+
1295+
vertexList: function (vertex) {
1296+
var result = [ ];
1297+
while (vertex) {
1298+
result.push(vertex);
1299+
vertex = vertex.parent;
1300+
}
1301+
return result;
1302+
},
1303+
1304+
buildPath: function (vertex) {
1305+
var path = { vertices: [ vertex.vertex ], edges: [ ] };
1306+
var v = vertex;
1307+
1308+
while (v.parent) {
1309+
path.vertices.unshift(v.parent.vertex);
1310+
path.edges.unshift(v.parentEdge);
1311+
v = v.parent;
1312+
}
1313+
return path;
1314+
},
1315+
1316+
run: function (config, result, startVertex, endVertex) {
1317+
var maxIterations = config.maxIterations, visitCounter = 0;
1318+
1319+
var heap = new BinaryHeap(function (node) {
1320+
return node.dist;
1321+
});
1322+
1323+
var startNode = this.makeNode(startVertex);
1324+
startNode.dist = 0;
1325+
heap.push(startNode);
1326+
1327+
while (heap.size() > 0) {
1328+
if (visitCounter++ > maxIterations) {
1329+
var err = new ArangoError();
1330+
err.errorNum = arangodb.errors.ERROR_GRAPH_TOO_MANY_ITERATIONS.code;
1331+
err.errorMessage = arangodb.errors.ERROR_GRAPH_TOO_MANY_ITERATIONS.message;
1332+
throw err;
1333+
}
1334+
1335+
var currentNode = heap.pop();
1336+
var i, n;
1337+
1338+
if (endVertex.hasOwnProperty(currentNode.vertex._id)) {
1339+
delete endVertex[currentNode.vertex._id];
1340+
config.visitor(config, result, currentNode, this.buildPath(currentNode));
1341+
if (isEmpty(endVertex)) {
1342+
return;
1343+
}
1344+
}
1345+
1346+
if (currentNode.visited) {
1347+
continue;
1348+
}
1349+
1350+
if (currentNode.dist === Infinity) {
1351+
break;
1352+
}
1353+
1354+
currentNode.visited = true;
1355+
1356+
var path = this.buildPath(currentNode);
1357+
var filterResult = parseFilterResult(config.filter(config, currentNode.vertex, path));
1358+
1359+
if (! filterResult.visit) {
1360+
currentNode.hide = true;
1361+
}
1362+
1363+
if (! filterResult.expand) {
1364+
continue;
1365+
}
1366+
1367+
var dist = currentNode.dist;
1368+
var connected = config.expander(config, currentNode.vertex, path);
1369+
n = connected.length;
1370+
1371+
for (i = 0; i < n; ++i) {
1372+
var neighbor = this.makeNode(connected[i].vertex);
1373+
1374+
if (neighbor.visited) {
1375+
continue;
1376+
}
1377+
1378+
var edge = connected[i].edge;
1379+
var weight = 1;
1380+
if (config.distance) {
1381+
weight = config.distance(config, currentNode.vertex, neighbor.vertex, edge);
1382+
}
1383+
else if (config.weight) {
1384+
if (typeof edge[config.weight] === "number") {
1385+
weight = edge[config.weight];
1386+
}
1387+
else if (config.defaultWeight) {
1388+
weight = config.defaultWeight;
1389+
}
1390+
else {
1391+
weight = Infinity;
1392+
}
1393+
}
1394+
1395+
var alt = dist + weight;
1396+
if (alt < neighbor.dist) {
1397+
neighbor.dist = alt;
1398+
neighbor.parent = currentNode;
1399+
neighbor.parentEdge = edge;
1400+
heap.push(neighbor);
1401+
}
1402+
}
1403+
}
1404+
}
1405+
};
1406+
}
1407+
12641408
////////////////////////////////////////////////////////////////////////////////
12651409
/// @brief implementation details for a* shortest path strategy
12661410
////////////////////////////////////////////////////////////////////////////////
@@ -1478,7 +1622,8 @@ ArangoTraverser = function (config) {
14781622
depthfirst: ArangoTraverser.DEPTH_FIRST,
14791623
breadthfirst: ArangoTraverser.BREADTH_FIRST,
14801624
astar: ArangoTraverser.ASTAR_SEARCH,
1481-
dijkstra: ArangoTraverser.DIJKSTRA_SEARCH
1625+
dijkstra: ArangoTraverser.DIJKSTRA_SEARCH,
1626+
dijkstramulti: ArangoTraverser.DIJKSTRA_SEARCH_MULTI
14821627
}, "strategy");
14831628

14841629
config.order = validate(config.order, {
@@ -1589,6 +1734,9 @@ ArangoTraverser.prototype.traverse = function (result, startVertex, endVertex) {
15891734
else if (this.config.strategy === ArangoTraverser.DIJKSTRA_SEARCH) {
15901735
strategy = dijkstraSearch();
15911736
}
1737+
else if (this.config.strategy === ArangoTraverser.DIJKSTRA_SEARCH_MULTI) {
1738+
strategy = dijkstraSearchMulti();
1739+
}
15921740
else if (this.config.strategy === ArangoTraverser.BREADTH_FIRST) {
15931741
strategy = breadthFirstSearch();
15941742
}
@@ -1675,6 +1823,12 @@ ArangoTraverser.ASTAR_SEARCH = 2;
16751823

16761824
ArangoTraverser.DIJKSTRA_SEARCH = 3;
16771825

1826+
////////////////////////////////////////////////////////////////////////////////
1827+
/// @brief dijkstra search with multiple end vertices
1828+
////////////////////////////////////////////////////////////////////////////////
1829+
1830+
ArangoTraverser.DIJKSTRA_SEARCH_MULTI = 4;
1831+
16781832
////////////////////////////////////////////////////////////////////////////////
16791833< 341A /td>
/// @brief pre-order traversal, visitor called before expander
16801834
////////////////////////////////////////////////////////////////////////////////

0 commit comments

Comments
 (0)
0