1
0
Fork 0
arangodb/tests/js/common/shell/shell-graph-traversal.js

2060 lines
63 KiB
JavaScript

/*jshint globalstrict:false, strict:false */
/*global assertEqual */
////////////////////////////////////////////////////////////////////////////////
/// @brief test the graph traversal class
///
/// @file
///
/// DISCLAIMER
///
/// Copyright 2010-2012 triagens GmbH, Cologne, Germany
///
/// Licensed under the Apache License, Version 2.0 (the "License");
/// you may not use this file except in compliance with the License.
/// You may obtain a copy of the License at
///
/// http://www.apache.org/licenses/LICENSE-2.0
///
/// Unless required by applicable law or agreed to in writing, software
/// distributed under the License is distributed on an "AS IS" BASIS,
/// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
/// See the License for the specific language governing permissions and
/// limitations under the License.
///
/// Copyright holder is triAGENS GmbH, Cologne, Germany
///
/// @author Jan Steemann
/// @author Copyright 2012, triAGENS GmbH, Cologne, Germany
////////////////////////////////////////////////////////////////////////////////
var jsunity = require("jsunity");
var arangodb = require("@arangodb");
var traversal = require("@arangodb/graph/traversal");
var generalGraph = require("@arangodb/general-graph");
var db = arangodb.db;
var Traverser = traversal.Traverser;
////////////////////////////////////////////////////////////////////////////////
/// @brief create in-memory data-source
////////////////////////////////////////////////////////////////////////////////
function memoryDatasource (nodes, connections) {
'use strict';
var vertices = { };
var inEdges = { };
var outEdges = { };
// create vertices
nodes.forEach(function (key) {
vertices["vertices/" + key] = {
_id: "vertices/" + key,
_key: key,
name: key
};
});
// create connections
var connect = function (from, to, label) {
var key = from + "x" + to;
var edge = {
_id : "edges/" + key,
_key : key,
_from : "vertices/" + from,
_to : "vertices/" + to,
what : from + "->" + to
};
if (typeof label !== "undefined") {
edge.label = label;
}
if (outEdges[edge._from] === undefined) {
outEdges[edge._from] = [];
}
outEdges[edge._from].push(edge);
if (inEdges[edge._to] === undefined) {
inEdges[edge._to] = [];
}
inEdges[edge._to].push(edge);
};
connections.forEach(function (c) {
connect(c[0], c[1], c[2]);
});
// return the datasource
return {
inEdges: inEdges,
outEdges: outEdges,
vertices: vertices,
getVertexId: function (vertex) {
return vertex._id;
},
getPeerVertex: function (edge, vertex) {
if (edge._from === vertex._id) {
return this.getInVertex(edge);
}
if (edge._to === vertex._id) {
return this.getOutVertex(edge);
}
return null;
},
getInVertex: function (edge) {
return this.vertices[edge._to];
},
getOutVertex: function (edge) {
return this.vertices[edge._from];
},
getEdgeId: function (edge) {
return edge._id;
},
getLabel: function (edge) {
return edge.label;
},
getAllEdges: function (vertex) {
return this.inEdges[vertex._id].concat(outEdges[vertex._id]);
},
getInEdges: function (vertex) {
return this.inEdges[vertex._id];
},
getOutEdges: function (vertex) {
return this.outEdges[vertex._id];
}
};
}
////////////////////////////////////////////////////////////////////////////////
/// @brief test: in-memory graph traversal
////////////////////////////////////////////////////////////////////////////////
function MemoryTraversalSuite () {
'use strict';
var datasourceWorld;
var datasourcePeople;
var setUpSourceWorld = function () {
var nodes = [
"World", "Nothing", "Europe", "Asia", "America", "Australia", "Antarctica",
"Africa", "Blackhole", "DE", "FR", "GB", "IE", "CN", "JP", "TW", "US",
"MX", "AU", "EG", "ZA", "AN", "London", "Paris", "Lyon", "Cologne",
"Dusseldorf", "Beijing", "Shanghai", "Tokyo", "Kyoto", "Taipeh", "Perth",
"Sydney"
];
var connections = [
["World", "Europe"],
["World", "Asia"],
["World", "America"],
["World", "Australia"],
["World", "Africa"],
["World", "Antarctica"],
["Europe", "DE"],
["Europe", "FR"],
["Europe", "GB"],
["Europe", "IE"],
["Asia", "CN"],
["Asia", "JP"],
["Asia", "TW"],
["America", "US"],
["America", "MX"],
["Australia", "AU"],
["Antarctica", "AN"]
];
datasourceWorld = memoryDatasource(nodes, connections);
};
var setUpSourcePeople = function () {
var nodes = [
"Alice", "Bob", "Charly", "Diana", "Eric", "Frank"
];
var connections = [
["Alice", "Bob", "likes"],
["Bob", "Alice", "likes"],
["Alice", "Diana", "hates"],
["Alice", "Eric", "hates"],
["Eric", "Alice","hates"],
["Bob", "Charly", "likes"],
["Charly", "Diana", "hates"],
["Diana", "Charly", "hates"],
["Diana", "Alice", "likes"],
["Diana", "Eric", "likes"],
["Alice", "Frank", "l"],
["Frank", "Bob", "likes"]
];
datasourcePeople = memoryDatasource(nodes, connections);
};
var visitor = traversal.trackingVisitor;
var filter = function (config, vertex) {
var r = [ ];
if (config.noVisit && config.noVisit[vertex._id]) {
r.push(Traverser.EXCLUDE);
}
if (config.noExpand && config.noExpand[vertex._id]) {
r.push(Traverser.PRUNE);
}
return r;
};
var expander = function (config, vertex) {
var r = [ ];
var edgesList = config.datasource.getOutEdges(vertex);
var i;
if (edgesList !== undefined) {
for (i = 0; i < edgesList.length; ++i) {
r.push({ edge: edgesList[i], vertex: config.datasource.vertices[edgesList[i]._to] });
}
}
return r;
};
var getIds = function (data) {
var r = [ ];
data.forEach(function (item) {
r.push(item._id);
});
return r;
};
var getVisitedPaths = function (data) {
var r = [ ];
data.forEach(function (item) {
r.push(getIds(item.vertices));
});
return r;
};
var getResult = function () {
return {
visited: {
vertices: [ ],
paths: [ ]
}
};
};
var getConfig = function () {
return {
uniqueness: {
vertices: Traverser.UNIQUE_NONE,
edges: Traverser.UNIQUE_NONE
},
visitor: visitor,
filter: filter,
expander: expander,
datasource: datasourceWorld,
noVisit: {
"vertices/Antarctica" : true,
"vertices/IE": true
},
noExpand: {
"vertices/Africa": true
}
};
};
return {
////////////////////////////////////////////////////////////////////////////////
/// @brief set up
////////////////////////////////////////////////////////////////////////////////
setUp : function () {
setUpSourceWorld();
setUpSourcePeople();
},
////////////////////////////////////////////////////////////////////////////////
/// @brief tear down
////////////////////////////////////////////////////////////////////////////////
tearDown : function () {
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test depth-first pre-order forward visitation
////////////////////////////////////////////////////////////////////////////////
testDepthFirstPreOrderForward : function () {
var config = getConfig();
config.strategy = Traverser.DEPTH_FIRST;
config.order = Traverser.PRE_ORDER;
config.itemOrder = Traverser.FORWARD;
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/World"]);
var expectedVisits = [
"vertices/World",
"vertices/Europe",
"vertices/DE",
"vertices/FR",
"vertices/GB",
"vertices/Asia",
"vertices/CN",
"vertices/JP",
"vertices/TW",
"vertices/America",
"vertices/US",
"vertices/MX",
"vertices/Australia",
"vertices/AU",
"vertices/Africa",
"vertices/AN"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
var expectedPaths = [
[ "vertices/World" ],
[ "vertices/World", "vertices/Europe" ],
[ "vertices/World", "vertices/Europe", "vertices/DE" ],
[ "vertices/World", "vertices/Europe", "vertices/FR" ],
[ "vertices/World", "vertices/Europe", "vertices/GB" ],
[ "vertices/World", "vertices/Asia" ],
[ "vertices/World", "vertices/Asia", "vertices/CN" ],
[ "vertices/World", "vertices/Asia", "vertices/JP" ],
[ "vertices/World", "vertices/Asia", "vertices/TW" ],
[ "vertices/World", "vertices/America" ],
[ "vertices/World", "vertices/America", "vertices/US" ],
[ "vertices/World", "vertices/America", "vertices/MX" ],
[ "vertices/World", "vertices/Australia" ],
[ "vertices/World", "vertices/Australia", "vertices/AU" ],
[ "vertices/World", "vertices/Africa" ],
[ "vertices/World", "vertices/Antarctica", "vertices/AN" ]
];
assertEqual(expectedPaths, getVisitedPaths(result.visited.paths));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test depth-first pre-order backward visitation
////////////////////////////////////////////////////////////////////////////////
testDepthFirstPreOrderBackward : function () {
var config = getConfig();
config.strategy = Traverser.DEPTH_FIRST;
config.order = Traverser.PRE_ORDER;
config.itemOrder = Traverser.BACKWARD;
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/World"]);
var expectedVisits = [
"vertices/World",
"vertices/AN",
"vertices/Africa",
"vertices/Australia",
"vertices/AU",
"vertices/America",
"vertices/MX",
"vertices/US",
"vertices/Asia",
"vertices/TW",
"vertices/JP",
"vertices/CN",
"vertices/Europe",
"vertices/GB",
"vertices/FR",
"vertices/DE"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
var expectedPaths = [
[ "vertices/World" ],
[ "vertices/World", "vertices/Antarctica", "vertices/AN" ],
[ "vertices/World", "vertices/Africa" ],
[ "vertices/World", "vertices/Australia" ],
[ "vertices/World", "vertices/Australia", "vertices/AU" ],
[ "vertices/World", "vertices/America" ],
[ "vertices/World", "vertices/America", "vertices/MX" ],
[ "vertices/World", "vertices/America", "vertices/US" ],
[ "vertices/World", "vertices/Asia" ],
[ "vertices/World", "vertices/Asia", "vertices/TW" ],
[ "vertices/World", "vertices/Asia", "vertices/JP" ],
[ "vertices/World", "vertices/Asia", "vertices/CN" ],
[ "vertices/World", "vertices/Europe" ],
[ "vertices/World", "vertices/Europe", "vertices/GB" ],
[ "vertices/World", "vertices/Europe", "vertices/FR" ],
[ "vertices/World", "vertices/Europe", "vertices/DE" ]
];
assertEqual(expectedPaths, getVisitedPaths(result.visited.paths));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test depth-first post-order forward visitation
////////////////////////////////////////////////////////////////////////////////
testDepthFirstPostOrderForward : function () {
var config = getConfig();
config.strategy = Traverser.DEPTH_FIRST;
config.order = Traverser.POST_ORDER;
config.itemOrder = Traverser.FORWARD;
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/World"]);
var expectedVisits = [
"vertices/DE",
"vertices/FR",
"vertices/GB",
"vertices/Europe",
"vertices/CN",
"vertices/JP",
"vertices/TW",
"vertices/Asia",
"vertices/US",
"vertices/MX",
"vertices/America",
"vertices/AU",
"vertices/Australia",
"vertices/Africa",
"vertices/AN",
"vertices/World"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
var expectedPaths = [
[ "vertices/World", "vertices/Europe", "vertices/DE" ],
[ "vertices/World", "vertices/Europe", "vertices/FR" ],
[ "vertices/World", "vertices/Europe", "vertices/GB" ],
[ "vertices/World", "vertices/Europe" ],
[ "vertices/World", "vertices/Asia", "vertices/CN" ],
[ "vertices/World", "vertices/Asia", "vertices/JP" ],
[ "vertices/World", "vertices/Asia", "vertices/TW" ],
[ "vertices/World", "vertices/Asia" ],
[ "vertices/World", "vertices/America", "vertices/US" ],
[ "vertices/World", "vertices/America", "vertices/MX" ],
[ "vertices/World", "vertices/America" ],
[ "vertices/World", "vertices/Australia", "vertices/AU" ],
[ "vertices/World", "vertices/Australia" ],
[ "vertices/World", "vertices/Africa" ],
[ "vertices/World", "vertices/Antarctica", "vertices/AN" ],
[ "vertices/World" ]
];
assertEqual(expectedPaths, getVisitedPaths(result.visited.paths));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test depth-first post-order backward visitation
////////////////////////////////////////////////////////////////////////////////
testDepthFirstPostOrderBackward : function () {
var config = getConfig();
config.strategy = Traverser.DEPTH_FIRST;
config.order = Traverser.POST_ORDER;
config.itemOrder = Traverser.BACKWARD;
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/World"]);
var expectedVisits = [
"vertices/AN",
"vertices/Africa",
"vertices/AU",
"vertices/Australia",
"vertices/MX",
"vertices/US",
"vertices/America",
"vertices/TW",
"vertices/JP",
"vertices/CN",
"vertices/Asia",
"vertices/GB",
"vertices/FR",
"vertices/DE",
"vertices/Europe",
"vertices/World"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
var expectedPaths = [
[ "vertices/World", "vertices/Antarctica", "vertices/AN" ],
[ "vertices/World", "vertices/Africa" ],
[ "vertices/World", "vertices/Australia", "vertices/AU" ],
[ "vertices/World", "vertices/Australia" ],
[ "vertices/World", "vertices/America", "vertices/MX" ],
[ "vertices/World", "vertices/America", "vertices/US" ],
[ "vertices/World", "vertices/America" ],
[ "vertices/World", "vertices/Asia", "vertices/TW" ],
[ "vertices/World", "vertices/Asia", "vertices/JP" ],
[ "vertices/World", "vertices/Asia", "vertices/CN" ],
[ "vertices/World", "vertices/Asia" ],
[ "vertices/World", "vertices/Europe", "vertices/GB" ],
[ "vertices/World", "vertices/Europe", "vertices/FR" ],
[ "vertices/World", "vertices/Europe", "vertices/DE" ],
[ "vertices/World", "vertices/Europe" ],
[ "vertices/World" ]
];
assertEqual(expectedPaths, getVisitedPaths(result.visited.paths));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test breadth-first pre-order forward visitation
////////////////////////////////////////////////////////////////////////////////
testBreadthFirstPreOrderForward : function () {
var config = getConfig();
config.strategy = Traverser.BREADTH_FIRST;
config.order = Traverser.PRE_ORDER;
config.itemOrder = Traverser.FORWARD;
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/World"]);
var expectedVisits = [
"vertices/World",
"vertices/Europe",
"vertices/Asia",
"vertices/America",
"vertices/Australia",
"vertices/Africa",
"vertices/DE",
"vertices/FR",
"vertices/GB",
"vertices/CN",
"vertices/JP",
"vertices/TW",
"vertices/US",
"vertices/MX",
"vertices/AU",
"vertices/AN"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
var expectedPaths = [
[ "vertices/World" ],
[ "vertices/World", "vertices/Europe" ],
[ "vertices/World", "vertices/Asia" ],
[ "vertices/World", "vertices/America" ],
[ "vertices/World", "vertices/Australia" ],
[ "vertices/World", "vertices/Africa" ],
[ "vertices/World", "vertices/Europe", "vertices/DE" ],
[ "vertices/World", "vertices/Europe", "vertices/FR" ],
[ "vertices/World", "vertices/Europe", "vertices/GB" ],
[ "vertices/World", "vertices/Asia", "vertices/CN" ],
[ "vertices/World", "vertices/Asia", "vertices/JP" ],
[ "vertices/World", "vertices/Asia", "vertices/TW" ],
[ "vertices/World", "vertices/America", "vertices/US" ],
[ "vertices/World", "vertices/America", "vertices/MX" ],
[ "vertices/World", "vertices/Australia", "vertices/AU" ],
[ "vertices/World", "vertices/Antarctica", "vertices/AN" ]
];
assertEqual(expectedPaths, getVisitedPaths(result.visited.paths));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test breadth-first pre-order backward visitation
////////////////////////////////////////////////////////////////////////////////
testBreadthFirstPreOrderBackward : function () {
var config = getConfig();
config.strategy = Traverser.BREADTH_FIRST;
config.order = Traverser.PRE_ORDER;
config.itemOrder = Traverser.BACKWARD;
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/World"]);
var expectedVisits = [
"vertices/World",
"vertices/Africa",
"vertices/Australia",
"vertices/America",
"vertices/Asia",
"vertices/Europe",
"vertices/AN",
"vertices/AU",
"vertices/MX",
"vertices/US",
"vertices/TW",
"vertices/JP",
"vertices/CN",
"vertices/GB",
"vertices/FR",
"vertices/DE"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
var expectedPaths = [
[ "vertices/World" ],
[ "vertices/World", "vertices/Africa" ],
[ "vertices/World", "vertices/Australia" ],
[ "vertices/World", "vertices/America" ],
[ "vertices/World", "vertices/Asia" ],
[ "vertices/World", "vertices/Europe" ],
[ "vertices/World", "vertices/Antarctica", "vertices/AN" ],
[ "vertices/World", "vertices/Australia", "vertices/AU" ],
[ "vertices/World", "vertices/America", "vertices/MX" ],
[ "vertices/World", "vertices/America", "vertices/US" ],
[ "vertices/World", "vertices/Asia", "vertices/TW" ],
[ "vertices/World", "vertices/Asia", "vertices/JP" ],
[ "vertices/World", "vertices/Asia", "vertices/CN" ],
[ "vertices/World", "vertices/Europe", "vertices/GB" ],
[ "vertices/World", "vertices/Europe", "vertices/FR" ],
[ "vertices/World", "vertices/Europe", "vertices/DE" ]
];
assertEqual(expectedPaths, getVisitedPaths(result.visited.paths));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test breadth-first post-order forward visitation
////////////////////////////////////////////////////////////////////////////////
testBreadthFirstPostOrderForward : function () {
var config = getConfig();
config.strategy = Traverser.BREADTH_FIRST;
config.order = Traverser.POST_ORDER;
config.itemOrder = Traverser.FORWARD;
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/World"]);
var expectedVisits = [
"vertices/DE",
"vertices/FR",
"vertices/GB",
"vertices/CN",
"vertices/JP",
"vertices/TW",
"vertices/US",
"vertices/MX",
"vertices/AU",
"vertices/AN",
"vertices/Europe",
"vertices/Asia",
"vertices/America",
"vertices/Australia",
"vertices/Africa",
"vertices/World"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
var expectedPaths = [
[ "vertices/World", "vertices/Europe", "vertices/DE" ],
[ "vertices/World", "vertices/Europe", "vertices/FR" ],
[ "vertices/World", "vertices/Europe", "vertices/GB" ],
[ "vertices/World", "vertices/Asia", "vertices/CN" ],
[ "vertices/World", "vertices/Asia", "vertices/JP" ],
[ "vertices/World", "vertices/Asia", "vertices/TW" ],
[ "vertices/World", "vertices/America", "vertices/US" ],
[ "vertices/World", "vertices/America", "vertices/MX" ],
[ "vertices/World", "vertices/Australia", "vertices/AU" ],
[ "vertices/World", "vertices/Antarctica", "vertices/AN" ],
[ "vertices/World", "vertices/Europe" ],
[ "vertices/World", "vertices/Asia" ],
[ "vertices/World", "vertices/America" ],
[ "vertices/World", "vertices/Australia" ],
[ "vertices/World", "vertices/Africa" ],
[ "vertices/World" ]
];
assertEqual(expectedPaths, getVisitedPaths(result.visited.paths));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test breadth-first post-order backward visitation
////////////////////////////////////////////////////////////////////////////////
testBreadthFirstPostOrderBackward : function () {
var config = getConfig();
config.strategy = Traverser.BREADTH_FIRST;
config.order = Traverser.POST_ORDER;
config.itemOrder = Traverser.BACKWARD;
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/World"]);
var expectedVisits = [
"vertices/AN",
"vertices/AU",
"vertices/MX",
"vertices/US",
"vertices/TW",
"vertices/JP",
"vertices/CN",
"vertices/GB",
"vertices/FR",
"vertices/DE",
"vertices/Africa",
"vertices/Australia",
"vertices/America",
"vertices/Asia",
"vertices/Europe",
"vertices/World"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
var expectedPaths = [
[ "vertices/World", "vertices/Antarctica", "vertices/AN" ],
[ "vertices/World", "vertices/Australia", "vertices/AU" ],
[ "vertices/World", "vertices/America", "vertices/MX" ],
[ "vertices/World", "vertices/America", "vertices/US" ],
[ "vertices/World", "vertices/Asia", "vertices/TW" ],
[ "vertices/World", "vertices/Asia", "vertices/JP" ],
[ "vertices/World", "vertices/Asia", "vertices/CN" ],
[ "vertices/World", "vertices/Europe", "vertices/GB" ],
[ "vertices/World", "vertices/Europe", "vertices/FR" ],
[ "vertices/World", "vertices/Europe", "vertices/DE" ],
[ "vertices/World", "vertices/Africa" ],
[ "vertices/World", "vertices/Australia" ],
[ "vertices/World", "vertices/America" ],
[ "vertices/World", "vertices/Asia" ],
[ "vertices/World", "vertices/Europe" ],
[ "vertices/World" ]
];
assertEqual(expectedPaths, getVisitedPaths(result.visited.paths));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test minimal depth filter with depth 0
////////////////////////////////////////////////////////////////////////////////
testMinDepthFilterWithDepth0 : function () {
var config = {
datasource: datasourceWorld,
expander: expander,
filter: traversal.minDepthFilter,
minDepth: 0
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/World"]);
var expectedVisits = [
"vertices/World",
"vertices/Europe",
"vertices/DE",
"vertices/FR",
"vertices/GB",
"vertices/IE",
"vertices/Asia",
"vertices/CN",
"vertices/JP",
"vertices/TW",
"vertices/America",
"vertices/US",
"vertices/MX",
"vertices/Australia",
"vertices/AU",
"vertices/Africa",
"vertices/Antarctica",
"vertices/AN"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
var expectedPaths = [
[ "vertices/World"],
[ "vertices/World", "vertices/Europe" ],
[ "vertices/World", "vertices/Europe", "vertices/DE" ],
[ "vertices/World", "vertices/Europe", "vertices/FR" ],
[ "vertices/World", "vertices/Europe", "vertices/GB" ],
[ "vertices/World", "vertices/Europe", "vertices/IE" ],
[ "vertices/World", "vertices/Asia" ],
[ "vertices/World", "vertices/Asia", "vertices/CN" ],
[ "vertices/World", "vertices/Asia", "vertices/JP" ],
[ "vertices/World", "vertices/Asia", "vertices/TW" ],
[ "vertices/World", "vertices/America" ],
[ "vertices/World", "vertices/America", "vertices/US" ],
[ "vertices/World", "vertices/America", "vertices/MX" ],
[ "vertices/World", "vertices/Australia" ],
[ "vertices/World", "vertices/Australia", "vertices/AU" ],
[ "vertices/World", "vertices/Africa" ],
[ "vertices/World", "vertices/Antarctica"],
[ "vertices/World", "vertices/Antarctica", "vertices/AN" ]
];
assertEqual(expectedPaths, getVisitedPaths(result.visited.paths));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test minimal depth filter with depth 1
////////////////////////////////////////////////////////////////////////////////
testMinDepthFilterWithDepth1 : function () {
var config = {
datasource: datasourceWorld,
expander: expander,
filter: traversal.minDepthFilter,
minDepth: 1
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/World"]);
var expectedVisits = [
"vertices/Europe",
"vertices/DE",
"vertices/FR",
"vertices/GB",
"vertices/IE",
"vertices/Asia",
"vertices/CN",
"vertices/JP",
"vertices/TW",
"vertices/America",
"vertices/US",
"vertices/MX",
"vertices/Australia",
"vertices/AU",
"vertices/Africa",
"vertices/Antarctica",
"vertices/AN"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
var expectedPaths = [
[ "vertices/World", "vertices/Europe" ],
[ "vertices/World", "vertices/Europe", "vertices/DE" ],
[ "vertices/World", "vertices/Europe", "vertices/FR" ],
[ "vertices/World", "vertices/Europe", "vertices/GB" ],
[ "vertices/World", "vertices/Europe", "vertices/IE" ],
[ "vertices/World", "vertices/Asia" ],
[ "vertices/World", "vertices/Asia", "vertices/CN" ],
[ "vertices/World", "vertices/Asia", "vertices/JP" ],
[ "vertices/World", "vertices/Asia", "vertices/TW" ],
[ "vertices/World", "vertices/America" ],
[ "vertices/World", "vertices/America", "vertices/US" ],
[ "vertices/World", "vertices/America", "vertices/MX" ],
[ "vertices/World", "vertices/Australia" ],
[ "vertices/World", "vertices/Australia", "vertices/AU" ],
[ "vertices/World", "vertices/Africa" ],
[ "vertices/World", "vertices/Antarctica"],
[ "vertices/World", "vertices/Antarctica", "vertices/AN" ]
];
assertEqual(expectedPaths, getVisitedPaths(result.visited.paths));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test minimal depth filter with depth 2
////////////////////////////////////////////////////////////////////////////////
testMinDepthFilterWithDepth2 : function () {
var config = {
datasource: datasourceWorld,
expander: expander,
filter: traversal.minDepthFilter,
minDepth: 2
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/World"]);
var expectedVisits = [
"vertices/DE",
"vertices/FR",
"vertices/GB",
"vertices/IE",
"vertices/CN",
"vertices/JP",
"vertices/TW",
"vertices/US",
"vertices/MX",
"vertices/AU",
"vertices/AN"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
var expectedPaths = [
[ "vertices/World", "vertices/Europe", "vertices/DE" ],
[ "vertices/World", "vertices/Europe", "vertices/FR" ],
[ "vertices/World", "vertices/Europe", "vertices/GB" ],
[ "vertices/World", "vertices/Europe", "vertices/IE" ],
[ "vertices/World", "vertices/Asia", "vertices/CN" ],
[ "vertices/World", "vertices/Asia", "vertices/JP" ],
[ "vertices/World", "vertices/Asia", "vertices/TW" ],
[ "vertices/World", "vertices/America", "vertices/US" ],
[ "vertices/World", "vertices/America", "vertices/MX" ],
[ "vertices/World", "vertices/Australia", "vertices/AU" ],
[ "vertices/World", "vertices/Antarctica", "vertices/AN" ]
];
assertEqual(expectedPaths, getVisitedPaths(result.visited.paths));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test maximal depth filter with depth 0
////////////////////////////////////////////////////////////////////////////////
testMaxDepthFilterWithDepth0 : function () {
var config = {
datasource: datasourceWorld,
expander: expander,
filter: traversal.maxDepthFilter,
maxDepth: 0
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/World"]);
var expectedVisits = [
"vertices/World"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
var expectedPaths = [
[ "vertices/World" ]
];
assertEqual(expectedPaths, getVisitedPaths(result.visited.paths));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test maximal depth filter with depth 1
////////////////////////////////////////////////////////////////////////////////
testMaxDepthFilterWithDepth1 : function () {
var config = {
datasource: datasourceWorld,
expander: expander,
filter: traversal.maxDepthFilter,
maxDepth: 1
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/World"]);
var expectedVisits = [
"vertices/World",
"vertices/Europe",
"vertices/Asia",
"vertices/America",
"vertices/Australia",
"vertices/Africa",
"vertices/Antarctica"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
var expectedPaths = [
[ "vertices/World"],
[ "vertices/World", "vertices/Europe" ],
[ "vertices/World", "vertices/Asia" ],
[ "vertices/World", "vertices/America" ],
[ "vertices/World", "vertices/Australia" ],
[ "vertices/World", "vertices/Africa" ],
[ "vertices/World", "vertices/Antarctica"]
];
assertEqual(expectedPaths, getVisitedPaths(result.visited.paths));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test maximal depth filter with depth 2
////////////////////////////////////////////////////////////////////////////////
testMaxDepthFilterWithDepth2 : function () {
var config = {
datasource: datasourceWorld,
expander: expander,
filter: traversal.maxDepthFilter,
maxDepth: 2
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/World"]);
var expectedVisits = [
"vertices/World",
"vertices/Europe",
"vertices/DE",
"vertices/FR",
"vertices/GB",
"vertices/IE",
"vertices/Asia",
"vertices/CN",
"vertices/JP",
"vertices/TW",
"vertices/America",
"vertices/US",
"vertices/MX",
"vertices/Australia",
"vertices/AU",
"vertices/Africa",
"vertices/Antarctica",
"vertices/AN"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
var expectedPaths = [
[ "vertices/World"],
[ "vertices/World", "vertices/Europe" ],
[ "vertices/World", "vertices/Europe", "vertices/DE" ],
[ "vertices/World", "vertices/Europe", "vertices/FR" ],
[ "vertices/World", "vertices/Europe", "vertices/GB" ],
[ "vertices/World", "vertices/Europe", "vertices/IE" ],
[ "vertices/World", "vertices/Asia" ],
[ "vertices/World", "vertices/Asia", "vertices/CN" ],
[ "vertices/World", "vertices/Asia", "vertices/JP" ],
[ "vertices/World", "vertices/Asia", "vertices/TW" ],
[ "vertices/World", "vertices/America" ],
[ "vertices/World", "vertices/America", "vertices/US" ],
[ "vertices/World", "vertices/America", "vertices/MX" ],
[ "vertices/World", "vertices/Australia" ],
[ "vertices/World", "vertices/Australia", "vertices/AU" ],
[ "vertices/World", "vertices/Africa" ],
[ "vertices/World", "vertices/Antarctica"],
[ "vertices/World", "vertices/Antarctica", "vertices/AN" ]
];
assertEqual(expectedPaths, getVisitedPaths(result.visited.paths));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test filter by given key value pairs
////////////////////////////////////////////////////////////////////////////////
testIncludeMatchingAttributesFilter : function () {
// Can be removed as soon as all expanders use datasource
var anyExp = function (config, vertex) {
var result = [ ];
var edgesList = config.datasource.getAllEdges(vertex);
if (edgesList !== undefined) {
var i;
for (i = 0; i < edgesList.length; ++i) {
result.push({ edge: edgesList[i], vertex: config.datasource.vertices[edgesList[i]._to] });
}
}
return result;
};
var config = {
uniqueness: {
vertices: Traverser.UNIQUE_GLOBAL,
edges: Traverser.UNIQUE_NONE
},
matchingAttributes: [{"name": "Alice"},
{"name": "Frank"},
{"name": "Diana", "key": "FAIL"},
{"_id": "vertices/Bob"}],
visitor: visitor,
expander: anyExp,
filter: traversal.includeMatchingAttributesFilter,
datasource: datasourcePeople
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/Alice"]);
var expectedVisits = [
"vertices/Alice",
"vertices/Bob",
"vertices/Frank"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test combination of filters
////////////////////////////////////////////////////////////////////////////////
testCombineFilters : function () {
var excluder1 = function(config, vertex) {
if (vertex.name && vertex.name === config.exclude1) { return "exclude"; }
};
var excluder2 = function(config, vertex) {
if (vertex.name && vertex.name === config.exclude2) { return "exclude"; }
};
var excluder3 = function(config, vertex) {
if (vertex.name && vertex.name === config.exclude3) { return "exclude"; }
};
var pruner1 = function(config, vertex) {
if (vertex.name && vertex.name === config.prune1) { return "prune"; }
};
var pruner2 = function(config, vertex) {
if (vertex.name && vertex.name === config.prune2) { return "prune"; }
};
var config = {
expander: expander,
filter: [
excluder1,
pruner1,
excluder2,
pruner2,
excluder3
],
exclude1: "Europe",
exclude2: "AU",
exclude3: "World",
prune1: "Asia",
prune2: "Europe",
datasource: datasourceWorld
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/World"]);
var expectedVisits = [
"vertices/Asia",
"vertices/America",
"vertices/US",
"vertices/MX",
"vertices/Australia",
"vertices/Africa",
"vertices/Antarctica",
"vertices/AN"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
var expectedPaths = [
[ "vertices/World", "vertices/Asia" ],
[ "vertices/World", "vertices/America" ],
[ "vertices/World", "vertices/America", "vertices/US" ],
[ "vertices/World", "vertices/America", "vertices/MX" ],
[ "vertices/World", "vertices/Australia" ],
[ "vertices/World", "vertices/Africa" ],
[ "vertices/World", "vertices/Antarctica"],
[ "vertices/World", "vertices/Antarctica", "vertices/AN" ]
];
assertEqual(expectedPaths, getVisitedPaths(result.visited.paths));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test if exclude or prune can be overridden in combined filters
////////////////////////////////////////////////////////////////////////////////
testOverrideExcludeAndPruneOfCombinedFilters : function () {
var excludeAndPrune = function(config, vertex) {
if (vertex.name && vertex.name === config.excludeAndPrune) { return ["prune", "exclude"]; }
};
var config = {
expander: expander,
filter: [
excludeAndPrune,
traversal.visitAllFilter
],
excludeAndPrune: "World",
datasource: datasourceWorld
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/World"]);
var expectedVisits = [];
assertEqual(expectedVisits, getIds(result.visited.vertices));
var expectedPaths = [];
assertEqual(expectedPaths, getVisitedPaths(result.visited.paths));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test if all edges with one label are followed
////////////////////////////////////////////////////////////////////////////////
testFollowEdgesWithLabels : function () {
var config = {
uniqueness: {
vertices: Traverser.UNIQUE_GLOBAL,
edges: Traverser.UNIQUE_NONE
},
labels: "likes",
visitor: visitor,
expander: traversal.expandEdgesWithLabels,
datasource: datasourcePeople
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/Alice"]);
var expectedVisits = [
"vertices/Alice",
"vertices/Bob",
"vertices/Frank",
"vertices/Charly",
"vertices/Diana",
"vertices/Eric"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
var expectedPaths = [
[ "vertices/Alice"],
[ "vertices/Alice", "vertices/Bob" ],
[ "vertices/Alice", "vertices/Bob", "vertices/Frank" ],
[ "vertices/Alice", "vertices/Bob", "vertices/Charly" ],
[ "vertices/Alice", "vertices/Diana" ],
[ "vertices/Alice", "vertices/Diana", "vertices/Eric" ]
];
assertEqual(expectedPaths, getVisitedPaths(result.visited.paths));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test if all and only inbound edges with one label are followed
////////////////////////////////////////////////////////////////////////////////
testFollowInEdgesWithLabels : function () {
var config = {
uniqueness: {
vertices: Traverser.UNIQUE_GLOBAL,
edges: Traverser.UNIQUE_NONE
},
labels: "likes",
visitor: visitor,
expander: traversal.expandInEdgesWithLabels,
datasource: datasourcePeople
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/Alice"]);
var expectedVisits = [
"vertices/Alice",
"vertices/Bob",
"vertices/Frank",
"vertices/Diana"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
var expectedPaths = [
[ "vertices/Alice"],
[ "vertices/Alice", "vertices/Bob" ],
[ "vertices/Alice", "vertices/Bob", "vertices/Frank" ],
[ "vertices/Alice", "vertices/Diana" ]
];
assertEqual(expectedPaths, getVisitedPaths(result.visited.paths));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test if all and only outbound edges with one label are followed
////////////////////////////////////////////////////////////////////////////////
testFollowOutEdgesWithLabels : function () {
var config = {
uniqueness: {
vertices: Traverser.UNIQUE_GLOBAL,
edges: Traverser.UNIQUE_NONE
},
labels: "likes",
visitor: visitor,
expander: traversal.expandOutEdgesWithLabels,
datasource: datasourcePeople
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, config.datasource.vertices["vertices/Alice"]);
var expectedVisits = [
"vertices/Alice",
"vertices/Bob",
"vertices/Charly"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
var expectedPaths = [
[ "vertices/Alice"],
[ "vertices/Alice", "vertices/Bob" ],
[ "vertices/Alice", "vertices/Bob", "vertices/Charly" ]
];
assertEqual(expectedPaths, getVisitedPaths(result.visited.paths));
}
};
}
////////////////////////////////////////////////////////////////////////////////
/// @brief test: collection-based graph traversal
////////////////////////////////////////////////////////////////////////////////
function CollectionTraversalSuite () {
'use strict';
var vn = "UnitTestsVertices";
var en = "UnitTestsEdges";
var vertexCollection;
var edgeCollection;
var getResult = function () {
return {
visited: {
vertices: [ ],
paths: [ ]
}
};
};
var getIds = function (data) {
var r = [ ];
data.forEach(function (item) {
r.push(item._id);
});
return r;
};
return {
////////////////////////////////////////////////////////////////////////////////
/// @brief set up
////////////////////////////////////////////////////////////////////////////////
setUp : function () {
db._drop(vn);
db._drop(en);
vertexCollection = db._create(vn);
edgeCollection = db._createEdgeCollection(en);
[ "A", "B", "C", "D", "E", "F", "G", "H", "I" ].forEach(function (item) {
vertexCollection.save({ _key: item, name: item });
});
[ [ "A", "B" ],
[ "B", "C" ],
[ "C", "D" ],
[ "A", "D" ],
[ "D", "E" ],
[ "D", "F" ],
[ "B", "G" ],
[ "B", "I" ],
[ "G", "H" ],
[ "I", "H"] ].forEach(function (item) {
var l = item[0];
var r = item[1];
edgeCollection.save(vn + "/" + l, vn + "/" + r, { _key: l + r, what : l + "->" + r });
});
},
////////////////////////////////////////////////////////////////////////////////
/// @brief tear down
////////////////////////////////////////////////////////////////////////////////
tearDown : function () {
db._drop(vn);
db._drop(en);
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test outbound expander
////////////////////////////////////////////////////////////////////////////////
testOutboundExpander : function () {
var config = {
sort: function (l, r) { return l._key < r._key ? -1 : 1; },
datasource: traversal.collectionDatasourceFactory(edgeCollection)
};
var expander = traversal.outboundExpander;
var connected;
connected = [ ];
expander(config, vertexCollection.document(vn + "/A")).forEach(function(item) {
connected.push(item.vertex._key);
});
assertEqual([ "B", "D" ], connected);
connected = [ ];
expander(config, vertexCollection.document(vn + "/D")).forEach(function(item) {
connected.push(item.vertex._key);
});
assertEqual([ "E", "F" ], connected);
connected = [ ];
expander(config, vertexCollection.document(vn + "/H")).forEach(function(item) {
connected.push(item.vertex._key);
});
assertEqual([ ], connected);
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test inbound expander
////////////////////////////////////////////////////////////////////////////////
testInboundExpander : function () {
var config = {
sort: function (l, r) { return l._key < r._key ? -1 : 1; },
datasource: traversal.collectionDatasourceFactory(edgeCollection)
};
var expander = traversal.inboundExpander;
var connected;
connected = [ ];
expander(config, vertexCollection.document(vn + "/D")).forEach(function(item) {
connected.push(item.vertex._key);
});
assertEqual([ "A", "C" ], connected);
connected = [ ];
expander(config, vertexCollection.document(vn + "/H")).forEach(function(item) {
connected.push(item.vertex._key);
});
assertEqual([ "G", "I" ], connected);
connected = [ ];
expander(config, vertexCollection.document(vn + "/A")).forEach(function(item) {
connected.push(item.vertex._key);
});
assertEqual([ ], connected);
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test iteration
////////////////////////////////////////////////////////////////////////////////
testIterateFullOutbound : function () {
var config = {
datasource: traversal.collectionDatasourceFactory(db._collection(en)),
strategy: Traverser.DEPTH_FIRST,
order: Traverser.PRE_ORDER,
itemOrder: Traverser.FORWARD,
filter: traversal.visitAllFilter,
expander: traversal.outboundExpander,
sort: function (l, r) { return l._key < r._key ? -1 : 1; }
};
var traverser = new Traverser(config);
var result = getResult();
traverser.traverse(result, vertexCollection.document(vn + "/A"));
var expectedVisits = [
vn + "/A",
vn + "/B",
vn + "/C",
vn + "/D",
vn + "/E",
vn + "/F",
vn + "/G",
vn + "/H",
vn + "/I",
vn + "/H",
vn + "/D",
vn + "/E",
vn + "/F"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test iteration
////////////////////////////////////////////////////////////////////////////////
testIterateInbound : function () {
var config = {
datasource: traversal.collectionDatasourceFactory(db._collection(en)),
strategy: Traverser.DEPTH_FIRST,
order: Traverser.PRE_ORDER,
itemOrder: Traverser.FORWARD,
filter: traversal.visitAllFilter,
expander: traversal.inboundExpander,
sort: function (l, r) { return l._key < r._key ? -1 : 1; }
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, vertexCollection.document(vn + "/F"));
var expectedVisits = [
vn + "/F",
vn + "/D",
vn + "/A",
vn + "/C",
vn + "/B",
vn + "/A"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test iteration
////////////////////////////////////////////////////////////////////////////////
testIterateUniqueGlobalVertices : function () {
var config = {
datasource: traversal.collectionDatasourceFactory(db._collection(en)),
strategy: Traverser.DEPTH_FIRST,
order: Traverser.PRE_ORDER,
itemOrder: Traverser.FORWARD,
uniqueness: {
vertices: Traverser.UNIQUE_GLOBAL,
edges: Traverser.UNIQUE_NONE
},
filter: traversal.visitAllFilter,
expander: traversal.outboundExpander,
sort: function (l, r) { return l._key < r._key ? -1 : 1; }
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, vertexCollection.document(vn + "/A"));
var expectedVisits = [
vn + "/A",
vn + "/B",
vn + "/C",
vn + "/D",
vn + "/E",
vn + "/F",
vn + "/G",
vn + "/H",
vn + "/I"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test iteration
////////////////////////////////////////////////////////////////////////////////
testIterateUniquePathVertices : function () {
var config = {
datasource: traversal.collectionDatasourceFactory(db._collection(en)),
strategy: Traverser.DEPTH_FIRST,
order: Traverser.PRE_ORDER,
itemOrder: Traverser.FORWARD,
uniqueness: {
vertices: Traverser.UNIQUE_PATH,
edges: Traverser.UNIQUE_NONE
},
filter: traversal.visitAllFilter,
expander: traversal.outboundExpander,
sort: function (l, r) { return l._key < r._key ? -1 : 1; }
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, vertexCollection.document(vn + "/A"));
var expectedVisits = [
vn + "/A",
vn + "/B",
vn + "/C",
vn + "/D",
vn + "/E",
vn + "/F",
vn + "/G",
vn + "/H",
vn + "/I",
vn + "/H",
vn + "/D",
vn + "/E",
vn + "/F"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test iteration
////////////////////////////////////////////////////////////////////////////////
testIterateUniqueEdges : function () {
var config = {
datasource: traversal.collectionDatasourceFactory(db._collection(en)),
strategy: Traverser.DEPTH_FIRST,
order: Traverser.PRE_ORDER,
itemOrder: Traverser.FORWARD,
uniqueness: {
vertices: Traverser.UNIQUE_NONE,
edges: Traverser.UNIQUE_GLOBAL
},
filter: traversal.visitAllFilter,
expander: traversal.outboundExpander,
sort: function (l, r) { return l._key < r._key ? -1 : 1; }
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, vertexCollection.document(vn + "/A"));
var expectedVisits = [
vn + "/A",
vn + "/B",
vn + "/C",
vn + "/D",
vn + "/E",
vn + "/F",
vn + "/G",
vn + "/H",
vn + "/I",
vn + "/H",
vn + "/D"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
}
};
}
////////////////////////////////////////////////////////////////////////////////
/// @brief test: general-graph-based graph traversal
////////////////////////////////////////////////////////////////////////////////
function GeneralGraphTraversalSuite () {
'use strict';
// Definition of the edges: A -> BDEH <-> CFGI
var vnA = "UnitTestsVertices1";
var enDir = "UnitTestsEdges1";
var vnBDH = "UnitTestsVertices2";
var enUndir = "UnitTestsEdges2";
var vnCEFGI = "UnitTestsVertices3";
var gn = "UnitTestsGraph";
var g;
var getResult = function () {
return {
visited: {
vertices: [ ],
paths: [ ]
}
};
};
var getIds = function (data) {
var r = [ ];
data.forEach(function (item) {
r.push(item._id);
});
return r;
};
var saveVertex = function(colName, key) {
g[colName].save({ _key: key, name: key });
};
var saveEdge = function(edgeCol, fromCol, toCol, nodePair) {
var l = nodePair[0];
var r = nodePair[1];
g[edgeCol].save(fromCol + "/" + l, toCol + "/" + r, {_key: l + r, what: l + "->" + r });
};
var cleanUp = function() {
db._drop(vnA);
db._drop(vnBDH);
db._drop(vnCEFGI);
db._drop(enDir);
db._drop(enUndir);
if (db._graphs.exists(gn)) {
db._graphs.remove(gn);
}
};
return {
////////////////////////////////////////////////////////////////////////////////
/// @brief set up
////////////////////////////////////////////////////////////////////////////////
setUp : function () {
cleanUp();
var edgeDef = [];
edgeDef.push(generalGraph._relation(enDir, vnA, vnBDH));
edgeDef.push(generalGraph._relation(enUndir, [vnBDH, vnCEFGI], [vnBDH, vnCEFGI]));
g = generalGraph._create(gn, edgeDef);
saveVertex(vnA, "A");
[ "B", "D", "H" ].forEach(function (item) {
saveVertex(vnBDH, item);
});
[ "C", "E", "F", "G", "I" ].forEach(function (item) {
saveVertex(vnCEFGI, item);
});
[ [ "A", "B" ], [ "A", "D" ] ].forEach(function (item) {
saveEdge(enDir, vnA, vnBDH, item);
});
[ [ "B", "C" ], [ "D", "E" ], [ "D", "F" ], [ "B", "G" ], [ "B", "I" ] ].forEach(function (item) {
saveEdge(enUndir, vnBDH, vnCEFGI, item);
});
[ [ "C", "D" ], [ "G", "H" ], [ "I", "H"] ].forEach(function (item) {
saveEdge(enUndir, vnCEFGI, vnBDH, item);
});
},
////////////////////////////////////////////////////////////////////////////////
/// @brief tear down
////////////////////////////////////////////////////////////////////////////////
tearDown : function () {
cleanUp();
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test outbound expander
////////////////////////////////////////////////////////////////////////////////
testGGOutboundExpander : function () {
var config = {
sort: function (l, r) { return l._key < r._key ? -1 : 1; },
datasource: traversal.generalGraphDatasourceFactory(gn)
};
var expander = traversal.outboundExpander;
var connected;
connected = [ ];
expander(config, g[vnA].document("A")).forEach(function(item) {
connected.push(item.vertex._key);
});
assertEqual([ "B", "D" ], connected);
connected = [ ];
expander(config, g[vnBDH].document("D")).forEach(function(item) {
connected.push(item.vertex._key);
});
assertEqual([ "E", "F" ], connected);
connected = [ ];
expander(config, g[vnBDH].document("H")).forEach(function(item) {
connected.push(item.vertex._key);
});
assertEqual([ ], connected);
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test inbound expander
////////////////////////////////////////////////////////////////////////////////
testGGInboundExpander : function () {
var config = {
sort: function (l, r) { return l._key < r._key ? -1 : 1; },
datasource: traversal.generalGraphDatasourceFactory(gn)
};
var expander = traversal.inboundExpander;
var connected;
connected = [ ];
expander(config, g[vnBDH].document("D")).forEach(function(item) {
connected.push(item.vertex._key);
});
assertEqual([ "A", "C" ], connected);
connected = [ ];
expander(config, g[vnBDH].document("H")).forEach(function(item) {
connected.push(item.vertex._key);
});
assertEqual([ "G", "I" ], connected);
connected = [ ];
expander(config, g[vnA].document("A")).forEach(function(item) {
connected.push(item.vertex._key);
});
assertEqual([ ], connected);
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test iteration
////////////////////////////////////////////////////////////////////////////////
testGGIterateFullOutbound : function () {
var config = {
datasource: traversal.generalGraphDatasourceFactory(gn),
strategy: Traverser.DEPTH_FIRST,
order: Traverser.PRE_ORDER,
itemOrder: Traverser.FORWARD,
filter: traversal.visitAllFilter,
expander: traversal.outboundExpander,
sort: function (l, r) { return l._key < r._key ? -1 : 1; }
};
var traverser = new Traverser(config);
var result = getResult();
traverser.traverse(result, g[vnA].document("A"));
var expectedVisits = [
vnA + "/A",
vnBDH + "/B",
vnCEFGI + "/C",
vnBDH + "/D",
vnCEFGI + "/E",
vnCEFGI + "/F",
vnCEFGI + "/G",
vnBDH + "/H",
vnCEFGI + "/I",
vnBDH + "/H",
vnBDH + "/D",
vnCEFGI + "/E",
vnCEFGI + "/F"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test iteration
////////////////////////////////////////////////////////////////////////////////
testGGIterateInbound : function () {
var config = {
datasource: traversal.generalGraphDatasourceFactory(gn),
strategy: Traverser.DEPTH_FIRST,
order: Traverser.PRE_ORDER,
itemOrder: Traverser.FORWARD,
filter: traversal.visitAllFilter,
expander: traversal.inboundExpander,
sort: function (l, r) { return l._key < r._key ? -1 : 1; }
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, g[vnCEFGI].document("F"));
var expectedVisits = [
vnCEFGI + "/F",
vnBDH + "/D",
vnA + "/A",
vnCEFGI + "/C",
vnBDH + "/B",
vnA + "/A"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test iteration
////////////////////////////////////////////////////////////////////////////////
testGGIterateUniqueGlobalVertices : function () {
var config = {
datasource: traversal.generalGraphDatasourceFactory(gn),
strategy: Traverser.DEPTH_FIRST,
order: Traverser.PRE_ORDER,
itemOrder: Traverser.FORWARD,
uniqueness: {
vertices: Traverser.UNIQUE_GLOBAL,
edges: Traverser.UNIQUE_NONE
},
filter: traversal.visitAllFilter,
expander: traversal.outboundExpander,
sort: function (l, r) { return l._key < r._key ? -1 : 1; }
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, g[vnA].document("A"));
var expectedVisits = [
vnA + "/A",
vnBDH + "/B",
vnCEFGI + "/C",
vnBDH + "/D",
vnCEFGI + "/E",
vnCEFGI + "/F",
vnCEFGI + "/G",
vnBDH + "/H",
vnCEFGI + "/I"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test iteration
////////////////////////////////////////////////////////////////////////////////
testGGIterateUniquePathVertices : function () {
var config = {
datasource: traversal.generalGraphDatasourceFactory(gn),
strategy: Traverser.DEPTH_FIRST,
order: Traverser.PRE_ORDER,
itemOrder: Traverser.FORWARD,
uniqueness: {
vertices: Traverser.UNIQUE_PATH,
edges: Traverser.UNIQUE_NONE
},
filter: traversal.visitAllFilter,
expander: traversal.outboundExpander,
sort: function (l, r) { return l._key < r._key ? -1 : 1; }
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, g[vnA].document("A"));
var expectedVisits = [
vnA + "/A",
vnBDH + "/B",
vnCEFGI + "/C",
vnBDH + "/D",
vnCEFGI + "/E",
vnCEFGI + "/F",
vnCEFGI + "/G",
vnBDH + "/H",
vnCEFGI + "/I",
vnBDH + "/H",
vnBDH + "/D",
vnCEFGI + "/E",
vnCEFGI + "/F"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
},
////////////////////////////////////////////////////////////////////////////////
/// @brief test iteration
////////////////////////////////////////////////////////////////////////////////
testGGIterateUniqueEdges : function () {
var config = {
datasource: traversal.generalGraphDatasourceFactory(gn),
strategy: Traverser.DEPTH_FIRST,
order: Traverser.PRE_ORDER,
itemOrder: Traverser.FORWARD,
uniqueness: {
vertices: Traverser.UNIQUE_NONE,
edges: Traverser.UNIQUE_GLOBAL
},
filter: traversal.visitAllFilter,
expander: traversal.outboundExpander,
sort: function (l, r) { return l._key < r._key ? -1 : 1; }
};
var result = getResult();
var traverser = new Traverser(config);
traverser.traverse(result, g[vnA].document("A"));
var expectedVisits = [
vnA + "/A",
vnBDH + "/B",
vnCEFGI + "/C",
vnBDH + "/D",
vnCEFGI + "/E",
vnCEFGI + "/F",
vnCEFGI + "/G",
vnBDH + "/H",
vnCEFGI + "/I",
vnBDH + "/H",
vnBDH + "/D"
];
assertEqual(expectedVisits, getIds(result.visited.vertices));
}
};
}
////////////////////////////////////////////////////////////////////////////////
/// @brief executes the test suites
////////////////////////////////////////////////////////////////////////////////
jsunity.run(MemoryTraversalSuite);
jsunity.run(CollectionTraversalSuite);
jsunity.run(GeneralGraphTraversalSuite);
return jsunity.done();