Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

graph-data-structure

Package Overview
Dependencies
Maintainers
1
Versions
36
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

graph-data-structure - npm Package Compare versions

Comparing version 1.9.0 to 1.10.0

670

graph-data-structure.js
(function(f){if(typeof exports==="object"&&typeof module!=="undefined"){module.exports=f()}else if(typeof define==="function"&&define.amd){define([],f)}else{var g;if(typeof window!=="undefined"){g=window}else if(typeof global!=="undefined"){g=global}else if(typeof self!=="undefined"){g=self}else{g=this}g.GraphDataStructure = f()}})(function(){var define,module,exports;return (function(){function r(e,n,t){function o(i,f){if(!n[i]){if(!e[i]){var c="function"==typeof require&&require;if(!f&&c)return c(i,!0);if(u)return u(i,!0);var a=new Error("Cannot find module '"+i+"'");throw a.code="MODULE_NOT_FOUND",a}var p=n[i]={exports:{}};e[i][0].call(p.exports,function(r){var n=e[i][1][r];return o(n||r)},p,p.exports,r,e,n,t)}return n[i].exports}for(var u="function"==typeof require&&require,i=0;i<t.length;i++)o(t[i]);return o}return r})()({1:[function(require,module,exports){
"use strict";
// A graph data structure with depth-first search and topological sort.
module.exports = function Graph(serialized){
// The returned graph instance.
var graph = {
addNode: addNode,
removeNode: removeNode,
nodes: nodes,
adjacent: adjacent,
addEdge: addEdge,
removeEdge: removeEdge,
setEdgeWeight: setEdgeWeight,
getEdgeWeight: getEdgeWeight,
indegree: indegree,
outdegree: outdegree,
depthFirstSearch: depthFirstSearch,
lowestCommonAncestors: lowestCommonAncestors,
topologicalSort: topologicalSort,
shortestPath: shortestPath,
serialize: serialize,
deserialize: deserialize
};
// The adjacency list of the graph.
// Keys are node ids.
// Values are adjacent node id arrays.
var edges = {};
// The weights of edges.
// Keys are string encodings of edges.
// Values are weights (numbers).
var edgeWeights = {};
// If a serialized graph was passed into the constructor, deserialize it.
if(serialized){
deserialize(serialized);
}
// Adds a node to the graph.
// If node was already added, this function does nothing.
// If node was not already added, this function sets up an empty adjacency list.
function addNode(node){
edges[node] = adjacent(node);
return graph;
}
// Removes a node from the graph.
// Also removes incoming and outgoing edges.
function removeNode(node){
// Remove incoming edges.
Object.keys(edges).forEach(function (u){
edges[u].forEach(function (v){
if(v === node){
removeEdge(u, v);
}
});
});
// Remove outgoing edges (and signal that the node no longer exists).
delete edges[node];
return graph;
}
// Gets the list of nodes that have been added to the graph.
function nodes(){
var nodeSet = {};
Object.keys(edges).forEach(function (u){
nodeSet[u] = true;
edges[u].forEach(function (v){
nodeSet[v] = true;
});
});
return Object.keys(nodeSet);
}
// Gets the adjacent node list for the given node.
// Returns an empty array for unknown nodes.
function adjacent(node){
return edges[node] || [];
}
// Computes a string encoding of an edge,
// for use as a key in an object.
function encodeEdge(u, v){
return u + "|" + v;
}
// Sets the weight of the given edge.
function setEdgeWeight(u, v, weight){
edgeWeights[encodeEdge(u, v)] = weight;
return graph;
}
// Gets the weight of the given edge.
// Returns 1 if no weight was previously set.
function getEdgeWeight(u, v){
var weight = edgeWeights[encodeEdge(u, v)];
return weight === undefined ? 1 : weight;
}
// Adds an edge from node u to node v.
// Implicitly adds the nodes if they were not already added.
function addEdge(u, v, weight){
addNode(u);
addNode(v);
adjacent(u).push(v);
if (weight !== undefined) {
setEdgeWeight(u, v, weight);
function Graph(serialized) {
// Returned graph instance
var graph = {
addNode: addNode,
removeNode: removeNode,
nodes: nodes,
adjacent: adjacent,
addEdge: addEdge,
removeEdge: removeEdge,
setEdgeWeight: setEdgeWeight,
getEdgeWeight: getEdgeWeight,
indegree: indegree,
outdegree: outdegree,
depthFirstSearch: depthFirstSearch,
lowestCommonAncestors: lowestCommonAncestors,
topologicalSort: topologicalSort,
shortestPath: shortestPath,
serialize: serialize,
deserialize: deserialize
};
// The adjacency list of the graph.
// Keys are node ids.
// Values are adjacent node id arrays.
var edges = {};
// The weights of edges.
// Keys are string encodings of edges.
// Values are weights (numbers).
var edgeWeights = {};
// If a serialized graph was passed into the constructor, deserialize it.
if (serialized) {
deserialize(serialized);
}
return graph;
}
// Removes the edge from node u to node v.
// Does not remove the nodes.
// Does nothing if the edge does not exist.
function removeEdge(u, v){
if(edges[u]){
edges[u] = adjacent(u).filter(function (_v){
return _v !== v;
});
// Adds a node to the graph.
// If node was already added, this function does nothing.
// If node was not already added, this function sets up an empty adjacency list.
function addNode(node) {
edges[node] = adjacent(node);
return graph;
}
return graph;
}
// Computes the indegree for the given node.
// Not very efficient, costs O(E) where E = number of edges.
function indegree(node){
var degree = 0;
function check(v){
if(v === node){
degree++;
}
// Removes a node from the graph.
// Also removes incoming and outgoing edges.
function removeNode(node) {
// Remove incoming edges.
Object.keys(edges).forEach(function (u) {
edges[u].forEach(function (v) {
if (v === node) {
removeEdge(u, v);
}
});
});
// Remove outgoing edges (and signal that the node no longer exists).
delete edges[node];
return graph;
}
Object.keys(edges).forEach(function (u){
edges[u].forEach(check);
});
return degree;
}
// Computes the outdegree for the given node.
function outdegree(node){
return node in edges ? edges[node].length : 0;
}
// Depth First Search algorithm, inspired by
// Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 604
// This variant includes an additional option
// `includeSourceNodes` to specify whether to include or
// exclude the source nodes from the result (true by default).
// If `sourceNodes` is not specified, all nodes in the graph
// are used as source nodes.
function depthFirstSearch(sourceNodes, includeSourceNodes){
if(!sourceNodes){
sourceNodes = nodes();
// Gets the list of nodes that have been added to the graph.
function nodes() {
// TODO: Better implementation with set data structure
var nodeSet = {};
Object.keys(edges).forEach(function (u) {
nodeSet[u] = true;
edges[u].forEach(function (v) {
nodeSet[v] = true;
});
});
return Object.keys(nodeSet);
}
if(typeof includeSourceNodes !== "boolean"){
includeSourceNodes = true;
// Gets the adjacent node list for the given node.
// Returns an empty array for unknown nodes.
function adjacent(node) {
return edges[node] || [];
}
var visited = {};
var nodeList = [];
function DFSVisit(node){
if(!visited[node]){
visited[node] = true;
adjacent(node).forEach(DFSVisit);
nodeList.push(node);
}
// Computes a string encoding of an edge,
// for use as a key in an object.
function encodeEdge(u, v) {
return u + "|" + v;
}
if(includeSourceNodes){
sourceNodes.forEach(DFSVisit);
} else {
sourceNodes.forEach(function (node){
visited[node] = true;
});
sourceNodes.forEach(function (node){
adjacent(node).forEach(DFSVisit);
});
// Sets the weight of the given edge.
function setEdgeWeight(u, v, weight) {
edgeWeights[encodeEdge(u, v)] = weight;
return graph;
}
return nodeList;
}
// Least Common Ancestors
// Inspired by https://github.com/relaxedws/lca/blob/master/src/LowestCommonAncestor.php code
// but uses depth search instead of breadth. Also uses some optimizations
function lowestCommonAncestors(node1, node2){
var node1Ancestors = [];
var lcas = [];
function CA1Visit(visited, node){
if(!visited[node]){
visited[node] = true;
node1Ancestors.push(node);
if (node == node2) {
lcas.push(node);
return false; // found - shortcut
// Gets the weight of the given edge.
// Returns 1 if no weight was previously set.
function getEdgeWeight(u, v) {
var weight = edgeWeights[encodeEdge(u, v)];
return weight === undefined ? 1 : weight;
}
// Adds an edge from node u to node v.
// Implicitly adds the nodes if they were not already added.
function addEdge(u, v, weight) {
addNode(u);
addNode(v);
adjacent(u).push(v);
if (weight !== undefined) {
setEdgeWeight(u, v, weight);
}
return adjacent(node).every(node => {
return CA1Visit(visited, node);
});
} else {
return true;
}
return graph;
}
function CA2Visit(visited, node){
if(!visited[node]){
visited[node] = true;
if (node1Ancestors.indexOf(node) >= 0) {
lcas.push(node);
} else if (lcas.length == 0) {
adjacent(node).forEach(node => {
CA2Visit(visited, node);
});
// Removes the edge from node u to node v.
// Does not remove the nodes.
// Does nothing if the edge does not exist.
function removeEdge(u, v) {
if (edges[u]) {
edges[u] = adjacent(u).filter(function (_v) {
return _v !== v;
});
}
}
return graph;
}
if (CA1Visit({}, node1)) { // No shortcut worked
CA2Visit({}, node2);
// Computes the indegree for the given node.
// Not very efficient, costs O(E) where E = number of edges.
function indegree(node) {
var degree = 0;
function check(v) {
if (v === node) {
degree++;
}
}
Object.keys(edges).forEach(function (u) {
edges[u].forEach(check);
});
return degree;
}
return lcas;
}
// The topological sort algorithm yields a list of visited nodes
// such that for each visited edge (u, v), u comes before v in the list.
// Amazingly, this comes from just reversing the result from depth first search.
// Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 613
function topologicalSort(sourceNodes, includeSourceNodes){
return depthFirstSearch(sourceNodes, includeSourceNodes).reverse();
}
// Dijkstra's Shortest Path Algorithm.
// Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 658
// Variable and function names correspond to names in the book.
function shortestPath(source, destination){
// Upper bounds for shortest path weights from source.
var d = {};
// Predecessors.
var p = {};
// Poor man's priority queue, keyed on d.
var q = {};
function initializeSingleSource(){
nodes().forEach(function (node){
d[node] = Infinity;
});
if (d[source] !== Infinity) {
throw new Error("Source node is not in the graph");
}
if (d[destination] !== Infinity) {
throw new Error("Destination node is not in the graph");
}
d[source] = 0;
// Computes the outdegree for the given node.
function outdegree(node) {
return node in edges ? edges[node].length : 0;
}
// Adds entries in q for all nodes.
function initializePriorityQueue(){
nodes().forEach(function (node){
q[node] = true;
});
// Depth First Search algorithm, inspired by
// Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 604
// This variant includes an additional option
// `includeSourceNodes` to specify whether to include or
// exclude the source nodes from the result (true by default).
// If `sourceNodes` is not specified, all nodes in the graph
// are used as source nodes.
function depthFirstSearch(sourceNodes, includeSourceNodes) {
if (includeSourceNodes === void 0) { includeSourceNodes = true; }
if (!sourceNodes) {
sourceNodes = nodes();
}
if (typeof includeSourceNodes !== "boolean") {
includeSourceNodes = true;
}
var visited = {};
var nodeList = [];
function DFSVisit(node) {
if (!visited[node]) {
visited[node] = true;
adjacent(node).forEach(DFSVisit);
nodeList.push(node);
}
}
if (includeSourceNodes) {
sourceNodes.forEach(DFSVisit);
}
else {
sourceNodes.forEach(function (node) {
visited[node] = true;
});
sourceNodes.forEach(function (node) {
adjacent(node).forEach(DFSVisit);
});
}
return nodeList;
}
// Returns true if q is empty.
function priorityQueueEmpty(){
return Object.keys(q).length === 0;
// Least Common Ancestors
// Inspired by https://github.com/relaxedws/lca/blob/master/src/LowestCommonAncestor.php code
// but uses depth search instead of breadth. Also uses some optimizations
function lowestCommonAncestors(node1, node2) {
var node1Ancestors = [];
var lcas = [];
function CA1Visit(visited, node) {
if (!visited[node]) {
visited[node] = true;
node1Ancestors.push(node);
if (node == node2) {
lcas.push(node);
return false; // found - shortcut
}
return adjacent(node).every(function (node) {
return CA1Visit(visited, node);
});
}
else {
return true;
}
}
function CA2Visit(visited, node) {
if (!visited[node]) {
visited[node] = true;
if (node1Ancestors.indexOf(node) >= 0) {
lcas.push(node);
}
else if (lcas.length == 0) {
adjacent(node).forEach(function (node) {
CA2Visit(visited, node);
});
}
}
}
if (CA1Visit({}, node1)) {
// No shortcut worked
CA2Visit({}, node2);
}
return lcas;
}
// Linear search to extract (find and remove) min from q.
function extractMin(){
var min = Infinity;
var minNode;
Object.keys(q).forEach(function(node){
if (d[node] < min) {
min = d[node];
minNode = node;
// The topological sort algorithm yields a list of visited nodes
// such that for each visited edge (u, v), u comes before v in the list.
// Amazingly, this comes from just reversing the result from depth first search.
// Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 613
function topologicalSort(sourceNodes, includeSourceNodes) {
if (includeSourceNodes === void 0) { includeSourceNodes = true; }
return depthFirstSearch(sourceNodes, includeSourceNodes).reverse();
}
// Dijkstra's Shortest Path Algorithm.
// Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 658
// Variable and function names correspond to names in the book.
function shortestPath(source, destination) {
// Upper bounds for shortest path weights from source.
var d = {};
// Predecessors.
var p = {};
// Poor man's priority queue, keyed on d.
var q = {};
function initializeSingleSource() {
nodes().forEach(function (node) {
d[node] = Infinity;
});
if (d[source] !== Infinity) {
throw new Error("Source node is not in the graph");
}
if (d[destination] !== Infinity) {
throw new Error("Destination node is not in the graph");
}
d[source] = 0;
}
});
if (minNode === undefined) {
// If we reach here, there's a disconnected subgraph, and we're done.
q = {};
return null;
}
delete q[minNode];
return minNode;
// Adds entries in q for all nodes.
function initializePriorityQueue() {
nodes().forEach(function (node) {
q[node] = true;
});
}
// Returns true if q is empty.
function priorityQueueEmpty() {
return Object.keys(q).length === 0;
}
// Linear search to extract (find and remove) min from q.
function extractMin() {
var min = Infinity;
var minNode;
Object.keys(q).forEach(function (node) {
if (d[node] < min) {
min = d[node];
minNode = node;
}
});
if (minNode === undefined) {
// If we reach here, there's a disconnected subgraph, and we're done.
q = {};
return null;
}
delete q[minNode];
return minNode;
}
function relax(u, v) {
var w = getEdgeWeight(u, v);
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
p[v] = u;
}
}
function dijkstra() {
initializeSingleSource();
initializePriorityQueue();
while (!priorityQueueEmpty()) {
var u = extractMin();
if (u === null)
return;
adjacent(u).forEach(function (v) {
relax(u, v);
});
}
}
// Assembles the shortest path by traversing the
// predecessor subgraph from destination to source.
function path() {
var nodeList = [];
var weight = 0;
var node = destination;
while (p[node]) {
nodeList.push(node);
weight += getEdgeWeight(p[node], node);
node = p[node];
}
if (node !== source) {
throw new Error("No path found");
}
nodeList.push(node);
nodeList.reverse();
nodeList.weight = weight;
return nodeList;
}
dijkstra();
return path();
}
function relax(u, v){
var w = getEdgeWeight(u, v);
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
p[v] = u;
}
// Serializes the graph.
function serialize() {
var serialized = {
nodes: nodes().map(function (id) {
return { id: id };
}),
links: []
};
serialized.nodes.forEach(function (node) {
var source = node.id;
adjacent(source).forEach(function (target) {
serialized.links.push({
source: source,
target: target,
weight: getEdgeWeight(source, target)
});
});
});
return serialized;
}
function dijkstra(){
initializeSingleSource();
initializePriorityQueue();
while(!priorityQueueEmpty()){
var u = extractMin();
adjacent(u).forEach(function (v){
relax(u, v);
// Deserializes the given serialized graph.
function deserialize(serialized) {
serialized.nodes.forEach(function (node) {
addNode(node.id);
});
}
serialized.links.forEach(function (link) {
addEdge(link.source, link.target, link.weight);
});
return graph;
}
// Assembles the shortest path by traversing the
// predecessor subgraph from destination to source.
function path(){
var nodeList = [];
var weight = 0;
var node = destination;
while(p[node]){
nodeList.push(node);
weight += getEdgeWeight(p[node], node);
node = p[node];
}
if (node !== source) {
throw new Error("No path found");
}
nodeList.push(node);
nodeList.reverse();
nodeList.weight = weight;
return nodeList;
}
dijkstra();
return path();
}
// Serializes the graph.
function serialize(){
var serialized = {
nodes: nodes().map(function (id){
return { id: id };
}),
links: []
};
serialized.nodes.forEach(function (node){
var source = node.id;
adjacent(source).forEach(function (target){
serialized.links.push({
source: source,
target: target,
weight: getEdgeWeight(source, target)
});
});
});
return serialized;
}
// Deserializes the given serialized graph.
function deserialize(serialized){
serialized.nodes.forEach(function (node){ addNode(node.id); });
serialized.links.forEach(function (link){ addEdge(link.source, link.target, link.weight); });
// The returned graph instance.
return graph;
}
return graph;
}
module.exports = Graph;
},{}]},{},[1])(1)
});

670

index.js

@@ -0,376 +1,340 @@

"use strict";
// A graph data structure with depth-first search and topological sort.
module.exports = function Graph(serialized){
// The returned graph instance.
var graph = {
addNode: addNode,
removeNode: removeNode,
nodes: nodes,
adjacent: adjacent,
addEdge: addEdge,
removeEdge: removeEdge,
setEdgeWeight: setEdgeWeight,
getEdgeWeight: getEdgeWeight,
indegree: indegree,
outdegree: outdegree,
depthFirstSearch: depthFirstSearch,
lowestCommonAncestors: lowestCommonAncestors,
topologicalSort: topologicalSort,
shortestPath: shortestPath,
serialize: serialize,
deserialize: deserialize
};
// The adjacency list of the graph.
// Keys are node ids.
// Values are adjacent node id arrays.
var edges = {};
// The weights of edges.
// Keys are string encodings of edges.
// Values are weights (numbers).
var edgeWeights = {};
// If a serialized graph was passed into the constructor, deserialize it.
if(serialized){
deserialize(serialized);
}
// Adds a node to the graph.
// If node was already added, this function does nothing.
// If node was not already added, this function sets up an empty adjacency list.
function addNode(node){
edges[node] = adjacent(node);
return graph;
}
// Removes a node from the graph.
// Also removes incoming and outgoing edges.
function removeNode(node){
// Remove incoming edges.
Object.keys(edges).forEach(function (u){
edges[u].forEach(function (v){
if(v === node){
removeEdge(u, v);
}
});
});
// Remove outgoing edges (and signal that the node no longer exists).
delete edges[node];
return graph;
}
// Gets the list of nodes that have been added to the graph.
function nodes(){
var nodeSet = {};
Object.keys(edges).forEach(function (u){
nodeSet[u] = true;
edges[u].forEach(function (v){
nodeSet[v] = true;
});
});
return Object.keys(nodeSet);
}
// Gets the adjacent node list for the given node.
// Returns an empty array for unknown nodes.
function adjacent(node){
return edges[node] || [];
}
// Computes a string encoding of an edge,
// for use as a key in an object.
function encodeEdge(u, v){
return u + "|" + v;
}
// Sets the weight of the given edge.
function setEdgeWeight(u, v, weight){
edgeWeights[encodeEdge(u, v)] = weight;
return graph;
}
// Gets the weight of the given edge.
// Returns 1 if no weight was previously set.
function getEdgeWeight(u, v){
var weight = edgeWeights[encodeEdge(u, v)];
return weight === undefined ? 1 : weight;
}
// Adds an edge from node u to node v.
// Implicitly adds the nodes if they were not already added.
function addEdge(u, v, weight){
addNode(u);
addNode(v);
adjacent(u).push(v);
if (weight !== undefined) {
setEdgeWeight(u, v, weight);
function Graph(serialized) {
// Returned graph instance
var graph = {
addNode: addNode,
removeNode: removeNode,
nodes: nodes,
adjacent: adjacent,
addEdge: addEdge,
removeEdge: removeEdge,
setEdgeWeight: setEdgeWeight,
getEdgeWeight: getEdgeWeight,
indegree: indegree,
outdegree: outdegree,
depthFirstSearch: depthFirstSearch,
lowestCommonAncestors: lowestCommonAncestors,
topologicalSort: topologicalSort,
shortestPath: shortestPath,
serialize: serialize,
deserialize: deserialize
};
// The adjacency list of the graph.
// Keys are node ids.
// Values are adjacent node id arrays.
var edges = {};
// The weights of edges.
// Keys are string encodings of edges.
// Values are weights (numbers).
var edgeWeights = {};
// If a serialized graph was passed into the constructor, deserialize it.
if (serialized) {
deserialize(serialized);
}
return graph;
}
// Removes the edge from node u to node v.
// Does not remove the nodes.
// Does nothing if the edge does not exist.
function removeEdge(u, v){
if(edges[u]){
edges[u] = adjacent(u).filter(function (_v){
return _v !== v;
});
// Adds a node to the graph.
// If node was already added, this function does nothing.
// If node was not already added, this function sets up an empty adjacency list.
function addNode(node) {
edges[node] = adjacent(node);
return graph;
}
return graph;
}
// Computes the indegree for the given node.
// Not very efficient, costs O(E) where E = number of edges.
function indegree(node){
var degree = 0;
function check(v){
if(v === node){
degree++;
}
// Removes a node from the graph.
// Also removes incoming and outgoing edges.
function removeNode(node) {
// Remove incoming edges.
Object.keys(edges).forEach(function (u) {
edges[u].forEach(function (v) {
if (v === node) {
removeEdge(u, v);
}
});
});
// Remove outgoing edges (and signal that the node no longer exists).
delete edges[node];
return graph;
}
Object.keys(edges).forEach(function (u){
edges[u].forEach(check);
});
return degree;
}
// Computes the outdegree for the given node.
function outdegree(node){
return node in edges ? edges[node].length : 0;
}
// Depth First Search algorithm, inspired by
// Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 604
// This variant includes an additional option
// `includeSourceNodes` to specify whether to include or
// exclude the source nodes from the result (true by default).
// If `sourceNodes` is not specified, all nodes in the graph
// are used as source nodes.
function depthFirstSearch(sourceNodes, includeSourceNodes){
if(!sourceNodes){
sourceNodes = nodes();
// Gets the list of nodes that have been added to the graph.
function nodes() {
// TODO: Better implementation with set data structure
var nodeSet = {};
Object.keys(edges).forEach(function (u) {
nodeSet[u] = true;
edges[u].forEach(function (v) {
nodeSet[v] = true;
});
});
return Object.keys(nodeSet);
}
if(typeof includeSourceNodes !== "boolean"){
includeSourceNodes = true;
// Gets the adjacent node list for the given node.
// Returns an empty array for unknown nodes.
function adjacent(node) {
return edges[node] || [];
}
var visited = {};
var nodeList = [];
function DFSVisit(node){
if(!visited[node]){
visited[node] = true;
adjacent(node).forEach(DFSVisit);
nodeList.push(node);
}
// Computes a string encoding of an edge,
// for use as a key in an object.
function encodeEdge(u, v) {
return u + "|" + v;
}
if(includeSourceNodes){
sourceNodes.forEach(DFSVisit);
} else {
sourceNodes.forEach(function (node){
visited[node] = true;
});
sourceNodes.forEach(function (node){
adjacent(node).forEach(DFSVisit);
});
// Sets the weight of the given edge.
function setEdgeWeight(u, v, weight) {
edgeWeights[encodeEdge(u, v)] = weight;
return graph;
}
return nodeList;
}
// Least Common Ancestors
// Inspired by https://github.com/relaxedws/lca/blob/master/src/LowestCommonAncestor.php code
// but uses depth search instead of breadth. Also uses some optimizations
function lowestCommonAncestors(node1, node2){
var node1Ancestors = [];
var lcas = [];
function CA1Visit(visited, node){
if(!visited[node]){
visited[node] = true;
node1Ancestors.push(node);
if (node == node2) {
lcas.push(node);
return false; // found - shortcut
// Gets the weight of the given edge.
// Returns 1 if no weight was previously set.
function getEdgeWeight(u, v) {
var weight = edgeWeights[encodeEdge(u, v)];
return weight === undefined ? 1 : weight;
}
// Adds an edge from node u to node v.
// Implicitly adds the nodes if they were not already added.
function addEdge(u, v, weight) {
addNode(u);
addNode(v);
adjacent(u).push(v);
if (weight !== undefined) {
setEdgeWeight(u, v, weight);
}
return adjacent(node).every(node => {
return CA1Visit(visited, node);
});
} else {
return true;
}
return graph;
}
function CA2Visit(visited, node){
if(!visited[node]){
visited[node] = true;
if (node1Ancestors.indexOf(node) >= 0) {
lcas.push(node);
} else if (lcas.length == 0) {
adjacent(node).forEach(node => {
CA2Visit(visited, node);
});
// Removes the edge from node u to node v.
// Does not remove the nodes.
// Does nothing if the edge does not exist.
function removeEdge(u, v) {
if (edges[u]) {
edges[u] = adjacent(u).filter(function (_v) {
return _v !== v;
});
}
}
return graph;
}
if (CA1Visit({}, node1)) { // No shortcut worked
CA2Visit({}, node2);
// Computes the indegree for the given node.
// Not very efficient, costs O(E) where E = number of edges.
function indegree(node) {
var degree = 0;
function check(v) {
if (v === node) {
degree++;
}
}
Object.keys(edges).forEach(function (u) {
edges[u].forEach(check);
});
return degree;
}
return lcas;
}
// The topological sort algorithm yields a list of visited nodes
// such that for each visited edge (u, v), u comes before v in the list.
// Amazingly, this comes from just reversing the result from depth first search.
// Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 613
function topologicalSort(sourceNodes, includeSourceNodes){
return depthFirstSearch(sourceNodes, includeSourceNodes).reverse();
}
// Dijkstra's Shortest Path Algorithm.
// Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 658
// Variable and function names correspond to names in the book.
function shortestPath(source, destination){
// Upper bounds for shortest path weights from source.
var d = {};
// Predecessors.
var p = {};
// Poor man's priority queue, keyed on d.
var q = {};
function initializeSingleSource(){
nodes().forEach(function (node){
d[node] = Infinity;
});
if (d[source] !== Infinity) {
throw new Error("Source node is not in the graph");
}
if (d[destination] !== Infinity) {
throw new Error("Destination node is not in the graph");
}
d[source] = 0;
// Computes the outdegree for the given node.
function outdegree(node) {
return node in edges ? edges[node].length : 0;
}
// Adds entries in q for all nodes.
function initializePriorityQueue(){
nodes().forEach(function (node){
q[node] = true;
});
// Depth First Search algorithm, inspired by
// Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 604
// This variant includes an additional option
// `includeSourceNodes` to specify whether to include or
// exclude the source nodes from the result (true by default).
// If `sourceNodes` is not specified, all nodes in the graph
// are used as source nodes.
function depthFirstSearch(sourceNodes, includeSourceNodes) {
if (includeSourceNodes === void 0) { includeSourceNodes = true; }
if (!sourceNodes) {
sourceNodes = nodes();
}
if (typeof includeSourceNodes !== "boolean") {
includeSourceNodes = true;
}
var visited = {};
var nodeList = [];
function DFSVisit(node) {
if (!visited[node]) {
visited[node] = true;
adjacent(node).forEach(DFSVisit);
nodeList.push(node);
}
}
if (includeSourceNodes) {
sourceNodes.forEach(DFSVisit);
}
else {
sourceNodes.forEach(function (node) {
visited[node] = true;
});
sourceNodes.forEach(function (node) {
adjacent(node).forEach(DFSVisit);
});
}
return nodeList;
}
// Returns true if q is empty.
function priorityQueueEmpty(){
return Object.keys(q).length === 0;
// Least Common Ancestors
// Inspired by https://github.com/relaxedws/lca/blob/master/src/LowestCommonAncestor.php code
// but uses depth search instead of breadth. Also uses some optimizations
function lowestCommonAncestors(node1, node2) {
var node1Ancestors = [];
var lcas = [];
function CA1Visit(visited, node) {
if (!visited[node]) {
visited[node] = true;
node1Ancestors.push(node);
if (node == node2) {
lcas.push(node);
return false; // found - shortcut
}
return adjacent(node).every(function (node) {
return CA1Visit(visited, node);
});
}
else {
return true;
}
}
function CA2Visit(visited, node) {
if (!visited[node]) {
visited[node] = true;
if (node1Ancestors.indexOf(node) >= 0) {
lcas.push(node);
}
else if (lcas.length == 0) {
adjacent(node).forEach(function (node) {
CA2Visit(visited, node);
});
}
}
}
if (CA1Visit({}, node1)) {
// No shortcut worked
CA2Visit({}, node2);
}
return lcas;
}
// Linear search to extract (find and remove) min from q.
function extractMin(){
var min = Infinity;
var minNode;
Object.keys(q).forEach(function(node){
if (d[node] < min) {
min = d[node];
minNode = node;
// The topological sort algorithm yields a list of visited nodes
// such that for each visited edge (u, v), u comes before v in the list.
// Amazingly, this comes from just reversing the result from depth first search.
// Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 613
function topologicalSort(sourceNodes, includeSourceNodes) {
if (includeSourceNodes === void 0) { includeSourceNodes = true; }
return depthFirstSearch(sourceNodes, includeSourceNodes).reverse();
}
// Dijkstra's Shortest Path Algorithm.
// Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 658
// Variable and function names correspond to names in the book.
function shortestPath(source, destination) {
// Upper bounds for shortest path weights from source.
var d = {};
// Predecessors.
var p = {};
// Poor man's priority queue, keyed on d.
var q = {};
function initializeSingleSource() {
nodes().forEach(function (node) {
d[node] = Infinity;
});
if (d[source] !== Infinity) {
throw new Error("Source node is not in the graph");
}
if (d[destination] !== Infinity) {
throw new Error("Destination node is not in the graph");
}
d[source] = 0;
}
});
if (minNode === undefined) {
// If we reach here, there's a disconnected subgraph, and we're done.
q = {};
return null;
}
delete q[minNode];
return minNode;
// Adds entries in q for all nodes.
function initializePriorityQueue() {
nodes().forEach(function (node) {
q[node] = true;
});
}
// Returns true if q is empty.
function priorityQueueEmpty() {
return Object.keys(q).length === 0;
}
// Linear search to extract (find and remove) min from q.
function extractMin() {
var min = Infinity;
var minNode;
Object.keys(q).forEach(function (node) {
if (d[node] < min) {
min = d[node];
minNode = node;
}
});
if (minNode === undefined) {
// If we reach here, there's a disconnected subgraph, and we're done.
q = {};
return null;
}
delete q[minNode];
return minNode;
}
function relax(u, v) {
var w = getEdgeWeight(u, v);
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
p[v] = u;
}
}
function dijkstra() {
initializeSingleSource();
initializePriorityQueue();
while (!priorityQueueEmpty()) {
var u = extractMin();
if (u === null)
return;
adjacent(u).forEach(function (v) {
relax(u, v);
});
}
}
// Assembles the shortest path by traversing the
// predecessor subgraph from destination to source.
function path() {
var nodeList = [];
var weight = 0;
var node = destination;
while (p[node]) {
nodeList.push(node);
weight += getEdgeWeight(p[node], node);
node = p[node];
}
if (node !== source) {
throw new Error("No path found");
}
nodeList.push(node);
nodeList.reverse();
nodeList.weight = weight;
return nodeList;
}
dijkstra();
return path();
}
function relax(u, v){
var w = getEdgeWeight(u, v);
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
p[v] = u;
}
// Serializes the graph.
function serialize() {
var serialized = {
nodes: nodes().map(function (id) {
return { id: id };
}),
links: []
};
serialized.nodes.forEach(function (node) {
var source = node.id;
adjacent(source).forEach(function (target) {
serialized.links.push({
source: source,
target: target,
weight: getEdgeWeight(source, target)
});
});
});
return serialized;
}
function dijkstra(){
initializeSingleSource();
initializePriorityQueue();
while(!priorityQueueEmpty()){
var u = extractMin();
adjacent(u).forEach(function (v){
relax(u, v);
// Deserializes the given serialized graph.
function deserialize(serialized) {
serialized.nodes.forEach(function (node) {
addNode(node.id);
});
}
serialized.links.forEach(function (link) {
addEdge(link.source, link.target, link.weight);
});
return graph;
}
// Assembles the shortest path by traversing the
// predecessor subgraph from destination to source.
function path(){
var nodeList = [];
var weight = 0;
var node = destination;
while(p[node]){
nodeList.push(node);
weight += getEdgeWeight(p[node], node);
node = p[node];
}
if (node !== source) {
throw new Error("No path found");
}
nodeList.push(node);
nodeList.reverse();
nodeList.weight = weight;
return nodeList;
}
dijkstra();
return path();
}
// Serializes the graph.
function serialize(){
var serialized = {
nodes: nodes().map(function (id){
return { id: id };
}),
links: []
};
serialized.nodes.forEach(function (node){
var source = node.id;
adjacent(source).forEach(function (target){
serialized.links.push({
source: source,
target: target,
weight: getEdgeWeight(source, target)
});
});
});
return serialized;
}
// Deserializes the given serialized graph.
function deserialize(serialized){
serialized.nodes.forEach(function (node){ addNode(node.id); });
serialized.links.forEach(function (link){ addEdge(link.source, link.target, link.weight); });
// The returned graph instance.
return graph;
}
return graph;
}
module.exports = Graph;

68

package.json
{
"name": "graph-data-structure",
"version": "1.9.0",
"description": "A graph data structure with topological sort.",
"main": "index.js",
"files": [
"graph-data-structure.js"
],
"scripts": {
"test": "mocha",
"prepublishOnly": "browserify index.js -s GraphDataStructure -o graph-data-structure.js"
},
"repository": {
"type": "git",
"url": "git+https://github.com/datavis-tech/graph-data-structure.git"
},
"keywords": [
"graph",
"data",
"structures",
"algorithms"
],
"author": "Curran Kelleher",
"license": "MIT",
"bugs": {
"url": "https://github.com/datavis-tech/graph-data-structure/issues"
},
"homepage": "https://github.com/datavis-tech/graph-data-structure#readme",
"devDependencies": {
"browserify": "^16.5.0",
"graph-diagrams": "^0.5.0",
"mocha": "^6.2.0"
}
"name": "graph-data-structure",
"version": "1.10.0",
"description": "A graph data structure with topological sort.",
"main": "index.js",
"files": [
"graph-data-structure.js"
],
"scripts": {
"build": "tsc",
"test": "npm run build && mocha",
"browserify": "browserify index.js -s GraphDataStructure -o graph-data-structure.js",
"prepublishOnly": "npm run build && npm run browserify"
},
"repository": {
"type": "git",
"url": "git+https://github.com/datavis-tech/graph-data-structure.git"
},
"keywords": [
"graph",
"data",
"structures",
"algorithms"
],
"author": "Curran Kelleher",
"license": "MIT",
"bugs": {
"url": "https://github.com/datavis-tech/graph-data-structure/issues"
},
"homepage": "https://github.com/datavis-tech/graph-data-structure#readme",
"devDependencies": {
"@types/node": "^13.9.5",
"browserify": "^16.5.1",
"graph-diagrams": "^0.5.0",
"mocha": "^7.1.1",
"typescript": "^3.8.3"
}
}
SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc