New Research: Supply Chain Attack on Axios Pulls Malicious Dependency from npm.Details → →
Socket
Book a DemoSign in
Socket
Book a DemoSign in

create-paths

Package Overview
Dependencies
Maintainers
1
Versions
5
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

create-paths - npm Package Compare versions

Comparing version
1.0.2
 to
1.1.0
+87
-5
index.js

@@ -1,11 +0,93 @@

var createRoad = require('./lib/road');
var dijkstra = require('node-dijkstra');
var clone = require('clone');
module.exports = function(roads) {
road = createRoad(roads);
var costs = getCostsLookup(roads);
return function(from, to) {
return road.getPath(from, to);
var graph;
var path;
var cost;
var betweenStart;
var betweenEnd;
var betweenLocation;
var tempName;
// is a basic lookup
if(typeof from === 'string') {
graph = new dijkstra(costs);
path = from !== to ? graph.shortestPath(from, to) : [ from ];
if(path) {
cost = getPathCost(path, costs);
}
// is an inbetween lookup
} else {
betweenStart = from.from;
betweenEnd = from.to;
betweenLocation = from.location;
tempName = from.from + '_' + from.to;
costs[ tempName ] = {};
costs[ tempName ][ betweenStart ] = betweenLocation;
costs[ tempName ][ betweenEnd ] = costs[ betweenStart ][ betweenEnd ] - betweenLocation;
graph = new dijkstra(costs);
path = from !== to ? graph.shortestPath(tempName, to) : [ from ];
if(path) {
cost = getPathCost(path, costs);
}
path.shift();
delete costs[ tempName ];
}
if(path) {
return {
duration: cost,
path: path
};
} else {
return null;
}
};
};
};
function getCostsLookup(roads) {
var costs = {};
roads.forEach(function(road) {
road.forEach( function(node, i) {
// i < 2 because the last index is cost/duration
if(i < 2 && !costs[ node ]) {
costs[ node ] = {};
}
});
costs[ road[ 0 ] ][ road[ 1 ] ] = road[ 2 ];
});
return costs;
}
function getPathCost(path, costs) {
var total = 0;
for(var i = 1; i < path.length; i++) {
total += costs[ path[ i - 1 ] ][ path[ i ] ];
}
return total;
}
+5
-2
package.json
{
"name": "create-paths",
"version": "1.0.2",
"version": "1.1.0",
"description": "Create a graph like structure with nodes and edges and calculate the duration between positions along the graph",

@@ -12,3 +12,6 @@ "main": "index.js",

},
"dependencies": {},
"dependencies": {
"clone": "^1.0.2",
"node-dijkstra": "^1.1.3"
},
"devDependencies": {

@@ -15,0 +18,0 @@ "tape": "^4.0.1"

-48
lib/node.js
module.exports = function(name) {
var children = [];
return {
add: function(child) {
children.push(child);
},
traverse: function(to, path, visited) {
var paths = [];
if(path === undefined) {
path = [];
visited = [];
} else {
path = path.slice();
}
if(visited.indexOf(name) === -1) {
var childPath;
visited.push(name);
path.push(name);
// if this is the node we want to go to
// simply return a path with this node
if(name === to) {
paths.push(path);
} else {
children.forEach( function(child) {
childPath = child.traverse(to, path, visited);
if(childPath.length) {
paths = paths.concat(childPath);
}
});
}
}
return paths;
}
};
};
-135
lib/road.js
var node = require('./node');
module.exports = function(road) {
var durations = {};
var nodes = {};
road.forEach(function(path) {
add.apply(undefined, path);
});
return {
add: add,
getPath: function(from, to) {
var paths = [];
var durationOffsets = [];
var fromNode;
var segmentStart;
var segmentEnd;
var segmentLocation;
var segmentDuration;
// if this is a simple path
if(typeof from === 'string') {
fromNode = getNode(from);
if(fromNode) {
paths = fromNode.traverse(to);
durationOffsets = paths.map(Number.bind(undefined, 0));
}
// this is a complex location and we should create a temporary node
// for this location
} else {
fromNode = getTempNode(from);
if(fromNode) {
segmentStart = from.from;
segmentEnd = from.to;
segmentLocation = from.location;
segmentDuration = getDuration(segmentStart, segmentEnd);
paths = fromNode.traverse(to);
// remove the temp path from each
paths = paths.map( function(path, idx) {
path.shift();
if(path[ 0 ] === segmentStart) {
durationOffsets[ idx ] = segmentLocation;
} else if(path[ 0 ] === segmentEnd) {
durationOffsets[ idx ] = segmentDuration - segmentLocation;
}
return path;
});
}
}
return evaluatePaths(paths, durationOffsets);
}
};
function getTempNode(location) {
var from = location.from;
var to = location.to;
var fromNode = getNode(from);
var toNode = getNode(to);
var tempNode;
if(fromNode && toNode) {
tempNode = node(from + '_' + to);
tempNode.add(fromNode);
tempNode.add(toNode);
}
return tempNode;
}
function evaluatePaths(paths, durationOffsets) {
var shortestPathIdx;
var shortestPathDuration;
paths.forEach(function(path, idx) {
var pathDuration = 0;
for( var i = 1; i < path.length; i++ ) {
pathDuration += getDuration(path[ i - 1 ], path[ i ]);
}
// this is here to handle when you're inbetween states
pathDuration += durationOffsets[ idx ];
if(shortestPathDuration === undefined || pathDuration < shortestPathDuration) {
shortestPathDuration = pathDuration;
shortestPathIdx = idx;
}
});
if(shortestPathIdx !== undefined) {
return {
duration: shortestPathDuration,
path: paths[ shortestPathIdx ]
};
} else {
return null;
}
}
function getNode(name) {
return nodes[ name ] || ( nodes[ name ] = node(name) );
}
function getDuration(from, to) {
return durations[ from + '_' + to ];
}
function setDuration(from, to, duration) {
durations[ from + '_' + to ] = duration;
}
function add(from, to, duration) {
var fromNode = getNode(from);
var toNode = getNode(to);
setDuration(from, to, duration);
fromNode.add(toNode);
}
};