🚀 Big News: Socket Acquires Coana to Bring Reachability Analysis to Every Appsec Team.Learn more →
Socket
Book a DemoInstallSign in
Socket
Book a DemoInstallSign in

graphs-and-paths

Package Overview
Dependencies
Maintainers
1
Versions
12
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

graphs-and-paths - npm Package Compare versions

Comparing version

0.2.2
to
0.2.3

15

dist/graph.d.ts

@@ -108,4 +108,5 @@ import { Edge, EdgeId, EdgePoint, Location, Node, NodeId, Path, SimpleEdge, SimpleNode } from "./types";

* @returns The `Node` associated with the given ID, or `undefined` if none exists. Note that
* the type signature is a lie (it does not claim to be nullable), but this is
* consistent with other lookup methods such as keyed-indexing.
* the type signature is a lie (it claims to be non-nullable). This is for convenience.
* Lookup will usually be of known node IDs, and this is consistent with the typings
* for index lookup in objects.
*/

@@ -116,4 +117,5 @@ getNode(nodeId: NodeId): Node;

* @returns The `Edge` associated with the given ID, or `undefined` if none exists. Note that
* the type signature is a lie (it does not claim to be nullable), but this is
* consistent with other lookup methods such as keyed-indexing.
* the type signature is a lie (it claims to be non-nullable). This is for convenience.
* Lookup will usually be of known edge IDs, and this is consistent with the typings
* for index lookup in objects.
*/

@@ -189,4 +191,4 @@ getEdge(edgeId: EdgeId): Edge;

/**
* Does preprocessing to enable [[getClosestPoint]] by creating a spatial index for mesh of
* points along the graph.
* Does preprocessing to enable [[getClosestPoint]] by creating a spatial index of points along
* the graph.
*

@@ -233,3 +235,2 @@ * @param precision How fine the mesh should be. Lower precision is more accurate but takes

private getClosestPointWithMesh(location, mesh);
private getClosestPointWithoutMesh(location);
}

208

dist/graph.js

@@ -10,2 +10,3 @@ "use strict";

};
Object.defineProperty(exports, "__esModule", { value: true });
var Heap = require("heap");

@@ -149,3 +150,5 @@ var rbush = require("rbush");

var newStartPoint = Utils.getIntermediateLocation(segmentStart, segmentEnd, remainingDistance);
return [newStartPoint].concat(locations.slice(locationIndex + 1));
return [
newStartPoint
].concat(locations.slice(locationIndex + 1));
}

@@ -200,3 +203,6 @@ locationIndex++;

return {
start: { edgeId: newStartEdge.edge.id, distance: distanceDownEdge },
start: {
edgeId: newStartEdge.edge.id,
distance: distanceDownEdge,
},
end: end,

@@ -235,6 +241,6 @@ orientedEdges: orientedEdges.slice(edgeIndex),

var lastEdge = Utils.last(orientedEdges);
var firstEdgeIsTrivial = (firstEdge.isForward && start.distance >= firstEdge.edge.length)
|| (!firstEdge.isForward && start.distance <= 0);
var lastEdgeIsTrivial = (lastEdge.isForward && end.distance <= 0)
|| (!lastEdge.isForward && end.distance >= lastEdge.edge.length);
var firstEdgeIsTrivial = (firstEdge.isForward && start.distance >= firstEdge.edge.length) ||
(!firstEdge.isForward && start.distance <= 0);
var lastEdgeIsTrivial = (lastEdge.isForward && end.distance <= 0) ||
(!lastEdge.isForward && end.distance >= lastEdge.edge.length);
if (firstEdgeIsTrivial && lastEdgeIsTrivial && nodes.length === 1) {

@@ -249,3 +255,5 @@ return __assign({}, path, { start: end, end: end, nodes: [], orientedEdges: [Utils.last(orientedEdges)] });

edgeId: secondEdge.edge.id,
distance: secondEdge.isForward ? 0 : secondEdge.edge.length,
distance: secondEdge.isForward
? 0
: secondEdge.edge.length,
};

@@ -262,3 +270,5 @@ }

edgeId: secondLastEdge.edge.id,
distance: secondLastEdge.isForward ? secondLastEdge.edge.length : 0,
distance: secondLastEdge.isForward
? secondLastEdge.edge.length
: 0,
};

@@ -270,3 +280,5 @@ }

})();
var slice = function (xs) { return xs.slice(firstEdgeIsTrivial ? 1 : 0, lastEdgeIsTrivial ? xs.length - 1 : xs.length); };
var slice = function (xs) {
return xs.slice(firstEdgeIsTrivial ? 1 : 0, lastEdgeIsTrivial ? xs.length - 1 : xs.length);
};
return __assign({}, path, { start: newStart, end: newEnd, orientedEdges: slice(orientedEdges), nodes: slice(nodes) });

@@ -295,4 +307,5 @@ }

* @returns The `Node` associated with the given ID, or `undefined` if none exists. Note that
* the type signature is a lie (it does not claim to be nullable), but this is
* consistent with other lookup methods such as keyed-indexing.
* the type signature is a lie (it claims to be non-nullable). This is for convenience.
* Lookup will usually be of known node IDs, and this is consistent with the typings
* for index lookup in objects.
*/

@@ -305,4 +318,5 @@ Graph.prototype.getNode = function (nodeId) {

* @returns The `Edge` associated with the given ID, or `undefined` if none exists. Note that
* the type signature is a lie (it does not claim to be nullable), but this is
* consistent with other lookup methods such as keyed-indexing.
* the type signature is a lie (it claims to be non-nullable). This is for convenience.
* Lookup will usually be of known edge IDs, and this is consistent with the typings
* for index lookup in objects.
*/

@@ -318,3 +332,5 @@ Graph.prototype.getEdge = function (edgeId) {

var _this = this;
return this.getNodeOrThrow(nodeId).edgeIds.map(function (edgeId) { return _this.getEdgeOrThrow(edgeId); });
return this.getNodeOrThrow(nodeId).edgeIds.map(function (edgeId) {
return _this.getEdgeOrThrow(edgeId);
});
};

@@ -327,3 +343,6 @@ /**

var _a = this.getEdgeOrThrow(edgeId), startNodeId = _a.startNodeId, endNodeId = _a.endNodeId;
return [this.getNodeOrThrow(startNodeId), this.getNodeOrThrow(endNodeId)];
return [
this.getNodeOrThrow(startNodeId),
this.getNodeOrThrow(endNodeId),
];
};

@@ -356,4 +375,5 @@ /**

var _this = this;
return this.getNodeOrThrow(nodeId).edgeIds
.map(function (edgeId) { return _this.getOtherEndpoint(edgeId, nodeId); });
return this.getNodeOrThrow(nodeId).edgeIds.map(function (edgeId) {
return _this.getOtherEndpoint(edgeId, nodeId);
});
};

@@ -410,8 +430,14 @@ /**

var lastEdge = Utils.last(path);
var startNodeId_1 = firstEdge.isForward ? firstEdge.edge.startNodeId : firstEdge.edge.endNodeId;
var endNodeId_1 = lastEdge.isForward ? lastEdge.edge.endNodeId : lastEdge.edge.startNodeId;
var startNodeId_1 = firstEdge.isForward
? firstEdge.edge.startNodeId
: firstEdge.edge.endNodeId;
var endNodeId_1 = lastEdge.isForward
? lastEdge.edge.endNodeId
: lastEdge.edge.startNodeId;
var minEdgeId = Utils.min(path.map(function (pathEdge) { return pathEdge.edge.id; }), Utils.compareIds);
var allLocations = Utils.dedupeLocations(Utils.flatMap(path, function (pathEdge) {
var locations = pathEdge.edge.locations, isForward = pathEdge.isForward;
return isForward ? locations : locations.slice().reverse();
return isForward
? locations
: locations.slice().reverse();
}));

@@ -425,3 +451,6 @@ var innerLocations = allLocations.slice(1, allLocations.length - 1);

};
var nodeIdsToDelete = Utils.flatMap(path, function (pathEdge) { return [pathEdge.edge.startNodeId, pathEdge.edge.endNodeId]; }).filter(function (nodeId) { return nodeId !== startNodeId_1 && nodeId !== endNodeId_1; });
var nodeIdsToDelete = Utils.flatMap(path, function (pathEdge) { return [
pathEdge.edge.startNodeId,
pathEdge.edge.endNodeId,
]; }).filter(function (nodeId) { return nodeId !== startNodeId_1 && nodeId !== endNodeId_1; });
var edgesSeen = path.map(function (pathEdge) { return pathEdge.edge; });

@@ -431,3 +460,5 @@ // Maps allow deletion during iteration. Deleted entries are not iterated over,

nodeIdsToDelete.forEach(function (nodeId) { return newNodesById.delete(nodeId); });
edgesSeen.forEach(function (seenEdge) { return remainingEdgesById.delete(seenEdge.id); });
edgesSeen.forEach(function (seenEdge) {
return remainingEdgesById.delete(seenEdge.id);
});
newEdges.push(newEdge);

@@ -466,3 +497,4 @@ }

while (pending.length > 0) {
var currentNode = pending.pop(); // Not undefined because we just checked the length.
// Not undefined because we just checked the length.
var currentNode = pending.pop();
currentNode.edgeIds.forEach(function (edgeId) { return edgeIds.add(edgeId); });

@@ -498,6 +530,9 @@ this.getNeighbors(currentNode.id).forEach(function (neighbor) {

var endLocation = this.getLocation(end);
var addNodeToPending = function (node) { return pendingNodes.push({
nodeId: node.id,
cost: distancesFromStart.get(node.id) + Utils.distanceBetween(node.location, endLocation),
}); };
var addNodeToPending = function (node) {
return pendingNodes.push({
nodeId: node.id,
cost: distancesFromStart.get(node.id) +
Utils.distanceBetween(node.location, endLocation),
});
};
var cameFrom = new Map();

@@ -521,3 +556,4 @@ var endEdgeIsForward = true;

var newDistance = currentNodeDistance_1 + edge.length;
if (currentDistance == null || newDistance < currentDistance) {
if (currentDistance == null ||
newDistance < currentDistance) {
distancesFromStart.set(neighbor.id, newDistance);

@@ -530,3 +566,5 @@ cameFrom.set(neighbor.id, edge);

var handleEndpointOfGoal = function (isGoalStartNode) {
var addedDistance = isGoalStartNode ? end.distance : endEdge.length - end.distance;
var addedDistance = isGoalStartNode
? end.distance
: endEdge.length - end.distance;
var newDistance = currentNodeDistance_1 + addedDistance;

@@ -536,3 +574,6 @@ if (newDistance < endDistanceFromStart) {

endEdgeIsForward = isGoalStartNode;
pendingNodes.push({ nodeId: null, cost: endDistanceFromStart });
pendingNodes.push({
nodeId: null,
cost: endDistanceFromStart,
});
}

@@ -557,4 +598,4 @@ };

/**
* Does preprocessing to enable [[getClosestPoint]] by creating a spatial index for mesh of
* points along the graph.
* Does preprocessing to enable [[getClosestPoint]] by creating a spatial index of points along
* the graph.
*

@@ -574,3 +615,5 @@ * @param precision How fine the mesh should be. Lower precision is more accurate but takes

var _b = _this.getEdge(edgeIds[0]), edgeId = _b.id, startNodeId = _b.startNodeId, locations = _b.locations;
var locationIndex = startNodeId === node.id ? 0 : locations.length - 2;
var locationIndex = startNodeId === node.id
? 0
: locations.length - 2;
meshPoints.push({ x: x, y: y, edgeId: edgeId, locationIndex: locationIndex });

@@ -590,4 +633,3 @@ }

});
var tree = rbush(9, [".x", ".y", ".x", ".y"])
.load(meshPoints);
var tree = rbush(9, [".x", ".y", ".x", ".y"]).load(meshPoints);
return new Graph(this.nodesById, this.edgesById, tree);

@@ -609,5 +651,5 @@ };

else {
console.warn("getClosestPoint() called on Graph without precomputed mesh. For improved performance, call"
+ " .withClosestPointMesh() to get a new optimized graph.");
return this.getClosestPointWithoutMesh(location);
throw new Error("getClosestPoint() called on a Graph without a precomputed" +
" mesh. To prepare the graph, call .withClosestPointMesh()" +
" first.");
}

@@ -639,4 +681,8 @@ };

Graph.prototype.getOnlyPath = function (edge) {
var forwardPath = this.getOnlyPathInDirection({ edge: edge, isForward: true });
if (forwardPath.length > 1 && forwardPath[0] === Utils.last(forwardPath)) {
var forwardPath = this.getOnlyPathInDirection({
edge: edge,
isForward: true,
});
if (forwardPath.length > 1 &&
forwardPath[0] === Utils.last(forwardPath)) {
// We are in a loop.

@@ -646,3 +692,6 @@ return forwardPath.slice(0, forwardPath.length - 1);

else {
var backwardsPath = this.getOnlyPathInDirection({ edge: edge, isForward: false });
var backwardsPath = this.getOnlyPathInDirection({
edge: edge,
isForward: false,
});
return Utils.reversePath(backwardsPath.slice(1)).concat(forwardPath);

@@ -663,3 +712,5 @@ }

path.push(currentEdge);
var nextNodeId = currentEdge.isForward ? currentEdge.edge.endNodeId : currentEdge.edge.startNodeId;
var nextNodeId = currentEdge.isForward
? currentEdge.edge.endNodeId
: currentEdge.edge.startNodeId;
var nextNode = this.getNodeOrThrow(nextNodeId);

@@ -671,3 +722,5 @@ if (nextNode.edgeIds.length !== 2) {

var _a = nextNode.edgeIds, edgeId1 = _a[0], edgeId2 = _a[1];
var nextEdgeId = currentEdge.edge.id === edgeId1 ? edgeId2 : edgeId1;
var nextEdgeId = currentEdge.edge.id === edgeId1
? edgeId2
: edgeId1;
if (nextEdgeId === startEdge.edge.id) {

@@ -684,3 +737,4 @@ path.push(startEdge);

Graph.prototype.reconstructPath = function (start, end, cameFrom, endEdgeIsForward, length) {
if (start.edgeId === end.edgeId && Math.abs(start.distance - end.distance) <= length) {
if (start.edgeId === end.edgeId &&
Math.abs(start.distance - end.distance) <= length) {
// Handle special case of start and end on same edge.

@@ -692,9 +746,13 @@ return this.getShortestPathOnSameEdge(start, end);

// Build nodes, oriented edge, and location lists starting from end, then reverse.
var orientedEdges = [{
var orientedEdges = [
{
edge: endEdge,
isForward: endEdgeIsForward,
}];
},
];
var nodes = [];
var locations = this.getLocationsOnEdgeInterval(end.edgeId, end.distance, endEdgeIsForward ? 0 : this.getEdgeOrThrow(end.edgeId).length);
var currentNodeId_1 = endEdgeIsForward ? endEdge.startNodeId : endEdge.endNodeId;
var currentNodeId_1 = endEdgeIsForward
? endEdge.startNodeId
: endEdge.endNodeId;
while (true) {

@@ -709,3 +767,5 @@ nodes.push(this.getNodeOrThrow(currentNodeId_1));

orientedEdges.push({ edge: currentEdge, isForward: isForward });
var newLocations = isForward ? currentEdge.locations.slice().reverse() : currentEdge.locations;
var newLocations = isForward
? currentEdge.locations.slice().reverse()
: currentEdge.locations;
Utils.pushAll(locations, newLocations);

@@ -724,4 +784,9 @@ currentNodeId_1 = this.getOtherEndpoint(currentEdge.id, currentNodeId_1).id;

})();
orientedEdges.push({ edge: startEdge_1, isForward: startEdgeIsForward });
Utils.pushAll(locations, this.getLocationsOnEdgeInterval(start.edgeId, startEdgeIsForward ? this.getEdgeOrThrow(start.edgeId).length : 0, start.distance));
orientedEdges.push({
edge: startEdge_1,
isForward: startEdgeIsForward,
});
Utils.pushAll(locations, this.getLocationsOnEdgeInterval(start.edgeId, startEdgeIsForward
? this.getEdgeOrThrow(start.edgeId).length
: 0, start.distance));
return {

@@ -761,4 +826,10 @@ start: start,

var maxLocationIndex = Utils.findFloorIndex(locationDistances, maxDistance);
var startLocation = this.getLocation({ edgeId: edgeId, distance: startDistance });
var endLocation = this.getLocation({ edgeId: edgeId, distance: endDistance });
var startLocation = this.getLocation({
edgeId: edgeId,
distance: startDistance,
});
var endLocation = this.getLocation({
edgeId: edgeId,
distance: endDistance,
});
var intermediateLocations = locations.slice(minLocationIndex + 1, maxLocationIndex + 1);

@@ -768,3 +839,7 @@ if (endDistance < startDistance) {

}
return Utils.dedupeLocations([startLocation].concat(intermediateLocations, [endLocation]));
return Utils.dedupeLocations([
startLocation
].concat(intermediateLocations, [
endLocation,
]));
}

@@ -777,29 +852,10 @@ };

var distanceDownSegment = Utils.closestPointOnSegment(location, locations[locationIndex], locations[locationIndex + 1]).distanceDownSegment;
return { edgeId: edgeId, distance: locationDistances[locationIndex] + distanceDownSegment };
return {
edgeId: edgeId,
distance: locationDistances[locationIndex] + distanceDownSegment,
};
};
Graph.prototype.getClosestPointWithoutMesh = function (location) {
var bestPoint = null;
var bestDistance = Number.POSITIVE_INFINITY;
this.getAllEdges().forEach(function (edge) {
var locations = edge.locations, locationDistances = edge.locationDistances;
for (var i = 0, limit = locations.length - 1; i < limit; i++) {
var _a = Utils.closestPointOnSegment(location, locations[i], locations[i + 1]), distanceDownSegment = _a.distanceDownSegment, distanceFromLocation = _a.distanceFromLocation;
if (distanceFromLocation < bestDistance) {
bestDistance = distanceFromLocation;
bestPoint = {
edgeId: edge.id,
distance: locationDistances[i] + distanceDownSegment,
};
}
}
});
if (bestPoint == null) {
throw new Error("Cannot find closest edge point on graph with no edges");
}
return bestPoint;
};
return Graph;
}());
Object.defineProperty(exports, "__esModule", { value: true });
exports.default = Graph;
//# sourceMappingURL=graph.js.map

2

dist/index.js
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
require("es6-shim");
var graph_1 = require("./graph");
Object.defineProperty(exports, "__esModule", { value: true });
exports.default = graph_1.default;
//# sourceMappingURL=index.js.map

1

dist/types.js
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
//# sourceMappingURL=types.js.map

7

dist/utils.js
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
/** @hidden */

@@ -45,3 +46,3 @@ function last(ts) {

while (minIndex < maxIndex - 1) {
var guessIndex = (minIndex + maxIndex) / 2 | 0;
var guessIndex = ((minIndex + maxIndex) / 2) | 0;
var guess = xs[guessIndex];

@@ -124,3 +125,3 @@ if (guess < x) {

}
return array.reduce(function (a, b) { return comparator(a, b) < 0 ? a : b; });
return array.reduce(function (a, b) { return (comparator(a, b) < 0 ? a : b); });
}

@@ -163,3 +164,3 @@ exports.min = min;

function dedupe(ts, equals) {
if (equals === void 0) { equals = (function (t1, t2) { return t1 === t2; }); }
if (equals === void 0) { equals = function (t1, t2) { return t1 === t2; }; }
var result = [];

@@ -166,0 +167,0 @@ ts.forEach(function (t) {

37

package.json
{
"name": "graphs-and-paths",
"version": "0.2.2",
"version": "0.2.3",
"description": "Tools for graphs representing 2-D spatial points and links between them.",

@@ -12,11 +12,21 @@ "main": "dist/index.js",

"clean": "rm -rf dist",
"build": "npm run clean && tsc",
"build": "yarn run clean && tsc",
"buildDocs": "typedoc --out docs --mode file --name 'Graphs and Paths' --readme none --module commonjs --target es5 --theme minimal --excludePrivate",
"format": "yarn run format-glob -- \"'src/**/*.{ts,tsx}'\"",
"format-glob": "prettier --tab-width 4 --trailing-comma all --write",
"jest": "jest --config jest.json",
"jest-watch": "npm run jest -- --watch",
"jest-watch": "yarn run jest -- --watch",
"lint": "tslint --project .",
"prepublish": "npm run build",
"test": "npm run lint && npm run jest",
"watch": "npm run clean && tsc --watch"
"precommit": "lint-staged",
"prepublish": "yarn run build",
"test": "yarn run lint && yarn run jest",
"watch": "yarn run clean && tsc --watch"
},
"lint-staged": {
"*.{ts,tsx}": [
"format-glob",
"yarn run lint -- --fix",
"git add"
]
},
"repository": {

@@ -45,10 +55,13 @@ "type": "git",

"@types/rbush": "^2.0.2",
"jest": "^18.0.0",
"tslint": "^4.3.1",
"typedoc": "^0.5.3",
"typedoc-default-themes": "0.4.0",
"typescript": "^2.1.4"
"husky": "^0.13.4",
"jest": "^20.0.4",
"lint-staged": "^3.6.0",
"prettier": "^1.4.2",
"tslint": "^5.4.2",
"typedoc": "^0.7.1",
"typedoc-default-themes": "^0.5.0",
"typescript": "^2.3.4"
},
"dependencies": {
"es6-shim": "^0.35.2",
"es6-shim": "^0.35.3",
"heap": "^0.2.6",

@@ -55,0 +68,0 @@ "rbush": "^2.0.1",

dist/graph.js.map

Sorry, the diff of this file is not supported yet

dist/index.js.map

Sorry, the diff of this file is not supported yet

dist/utils.js.map

Sorry, the diff of this file is not supported yet