Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
data-footstone
Advanced tools
data-footstone - npm Package Compare versions
Comparing version 0.1.13 to 0.1.14
@@ -10,2 +10,3 @@ 'use strict'; | ||
| var store = require('./store.js'); | ||
| var graph = require('./graph.js'); | ||
@@ -29,2 +30,4 @@ | ||
| exports.Lru = store.Lru; | ||
| exports.DirectionGraph = graph.DirectionGraph; | ||
| exports.UndirectionGraph = graph.UndirectionGraph; | ||
| //# sourceMappingURL=index.js.map |
@@ -9,2 +9,3 @@ export { Stack } from './stack.js'; | ||
| export { Fifo, Lfu, Lru } from './store.js'; | ||
| export { DirectionGraph, UndirectionGraph } from './graph.js'; | ||
| //# sourceMappingURL=index.js.map |
| { | ||
| "name": "data-footstone", | ||
| "version": "0.1.13", | ||
| "version": "0.1.14", | ||
| "description": "data structure", | ||
@@ -75,3 +75,3 @@ "author": "feigebaobei <18515195415@163.com>", | ||
| }, | ||
| "gitHead": "9a8b00dcbc961707886c7d03db1a0541fea137d4" | ||
| "gitHead": "c9a99b1ecf5ea5846245c036de8f4c7909dcabb6" | ||
| } |
| import { Queue } from './queue'; | ||
| import { af, NPF } from './helper'; | ||
| class Graph { | ||
| // static vertices: any | ||
| // direction: G<T>['direction'] | ||
| constructor() { | ||
| this.vertices = []; | ||
| this.adjList = new Map(); | ||
| this.vertexMap = new Map(); | ||
| this.adjMatrix = new Map(); // 保存边的信息 | ||
| this.adjTable = new Map(); // 保存点的信息 | ||
| // 不可改变 | ||
| // Object.defineProperty(this, 'direction', { | ||
| // value: direction, | ||
| // writable: false | ||
| // }) | ||
| } | ||
| addVertex(v) { | ||
| this.vertices.push(v); | ||
| this.adjList.set(v, []); | ||
| createVertex(v) { | ||
| return { | ||
| data: v, | ||
| inDegree: 0, | ||
| outDegree: 0, | ||
| status: 'cover', | ||
| dTime: new Date(), | ||
| fTime: new Date(), | ||
| }; | ||
| } | ||
| addEdge(v, w) { | ||
| this.adjList.get(v).push(w); | ||
| this.adjList.get(w).push(v); | ||
| createEdge(a, b) { | ||
| return { | ||
| data: '', | ||
| start: this.vertexMap.get(a), | ||
| end: this.vertexMap.get(b), | ||
| weight: 0, | ||
| status: '' | ||
| }; | ||
| } | ||
| initColor() { | ||
| let color = new Map(); | ||
| this.vertices.forEach((item) => { | ||
| color.set(item, 'white'); | ||
| }); | ||
| return color; | ||
| putVertex(v) { | ||
| this.vertexMap.set(v, this.createVertex(v)); | ||
| for (let a of this.adjMatrix.values()) { | ||
| a.set(v, null); | ||
| } | ||
| this.adjMatrix.set(v, new Map(Array.from(this.vertexMap.keys()).map((v) => [v, null]))); | ||
| this.adjTable.set(v, new Set()); | ||
| } | ||
| bfs(index = 0, cb) { | ||
| let v = this.vertices[index]; | ||
| if (v !== undefined) { | ||
| let color = this.initColor(); | ||
| let queue = new Queue(); | ||
| queue.enqueue(v); | ||
| color.set(v, 'grey'); | ||
| while (queue.size()) { | ||
| let u = queue.dequeue(); | ||
| let neibors = this.adjList.get(u); | ||
| neibors.forEach((item) => { | ||
| if (color.get(item) === 'white') { | ||
| queue.enqueue(item); | ||
| color.set(item, 'grey'); | ||
| } | ||
| }); | ||
| cb && cb(u); | ||
| color.set(u, 'black'); | ||
| // putEdge(a: T, b: T) { | ||
| // if (this.direction) { // 有方向，需要添加1个边 | ||
| // this.adjMatrix.get(a).set(b, this.createEdge(a, b)) | ||
| // this.adjTable.get(a).add(this.vertexMap.get(b)) | ||
| // } else { // 无方向，需要添加2个边。 | ||
| // this.adjMatrix.get(a).set(b, this.createEdge(a, b)) // 添加 a->b | ||
| // this.adjMatrix.get(b).set(a, this.createEdge(b, a)) // 添加 b->a | ||
| // this.adjTable.get(a).add(this.vertexMap.get(b)) | ||
| // this.adjTable.get(b).add(this.vertexMap.get(a)) | ||
| // } | ||
| // } | ||
| edgeList() { | ||
| return Array.from(this.adjMatrix.values()).reduce((r, c) => { | ||
| for (let edge of c.values()) { | ||
| edge && r.push(edge); | ||
| } | ||
| return r; | ||
| }, []); | ||
| } | ||
| removeVertex(p) { | ||
| let vertex = this.vertexMap.get(p); | ||
| if (vertex) { | ||
| this.vertexMap.delete(vertex.data); // 删除map中的点 | ||
| this.adjMatrix.delete(vertex.data); // 删除矩阵中的点 | ||
| af(this.adjMatrix.values()).forEach(map => map.delete(vertex.data)); | ||
| this.adjTable.delete(vertex.data); | ||
| af(this.adjTable.values()).forEach(set => set.delete(vertex)); | ||
| } | ||
| return vertex; | ||
| } | ||
| _dfs(v, color, cb) { | ||
| cb && cb(v); | ||
| color.set(v, 'grey'); | ||
| let neibors = this.adjList.get(v); | ||
| for (let i = 0; i < neibors.length; i++) { | ||
| let w = neibors[i]; | ||
| if (color.get(w) === 'white') { | ||
| this._dfs(w, color, cb); | ||
| } | ||
| // removeEdge(a: T, b: T) { | ||
| // let res = [] | ||
| // if (this.direction) { // 有方向，应该删除1个边 | ||
| // let t = this.adjMatrix.get(a) | ||
| // res.push(t.get(b)) | ||
| // t.delete(b) | ||
| // this.adjTable.get(a).delete(this.vertexMap.get(b)) | ||
| // } else { // 无方向，应该删除2个边 | ||
| // let t = this.adjMatrix.get(a) | ||
| // res.push(t.get(b)) | ||
| // t.delete(b) | ||
| // t = this.adjMatrix.get(b) | ||
| // res.push(t.get(a)) | ||
| // t.delete(a) | ||
| // this.adjTable.get(a).delete(this.vertexMap.get(b)) | ||
| // this.adjTable.get(b).delete(this.vertexMap.get(a)) | ||
| // } | ||
| // return res | ||
| // } | ||
| reset() { | ||
| for (let vertex of this.vertexMap.values()) { | ||
| vertex.status = 'discovery'; | ||
| } | ||
| color.set(v, 'black'); | ||
| } | ||
| dfs(index = 0, cb) { | ||
| let v = this.vertices[index]; | ||
| if (v !== undefined) { | ||
| let color = this.initColor(); | ||
| this._dfs(v, color, cb); | ||
| // 只能遍历连通的顶点 | ||
| _bfs(vertex, cb) { | ||
| let vertexQueue = new Queue(); | ||
| vertexQueue.enqueue(vertex); | ||
| vertex.status = 'discovery'; | ||
| while (!vertexQueue.isEmpty()) { | ||
| let uVertex = vertexQueue.dequeue(); | ||
| let arr = this.adjTable.get(uVertex.data); | ||
| arr.forEach((neiborVertex) => { | ||
| if (neiborVertex.status === 'cover') { | ||
| vertexQueue.enqueue(neiborVertex); | ||
| neiborVertex.status = 'discovery'; | ||
| } | ||
| }); | ||
| cb(uVertex); | ||
| uVertex.status = 'visited'; | ||
| } | ||
| } | ||
| shortestPath(index = 0) { | ||
| bfs(data, cb) { | ||
| let vertex = this.vertexMap.get(data); | ||
| if (vertex) { | ||
| do { | ||
| if (vertex.status === 'cover') { | ||
| this._bfs(vertex, cb); | ||
| } | ||
| } while (vertex = af(this.vertexMap.values()).find(vertex => vertex.status === 'cover')); | ||
| this.reset(); | ||
| } | ||
| } | ||
| _dfs(vertex, cb) { | ||
| cb(vertex); | ||
| vertex.status = 'visited'; | ||
| let arr = this.adjTable.get(vertex.data); | ||
| arr.forEach((neiborVertex) => { | ||
| if (neiborVertex.status === 'cover') { | ||
| neiborVertex.status = 'discovery'; | ||
| this._dfs(neiborVertex, cb); | ||
| } | ||
| }); | ||
| } | ||
| dfs(data, cb) { | ||
| let vertex = this.vertexMap.get(data); | ||
| if (vertex) { | ||
| do { | ||
| if (vertex.status === 'cover') { | ||
| vertex.status = 'discovery'; | ||
| this._dfs(vertex, cb); | ||
| } | ||
| } while (vertex = af(this.vertexMap.values()).find(vertex => vertex.status === 'cover')); | ||
| this.reset(); | ||
| } | ||
| } | ||
| shortestPath(data) { | ||
| let distance = new Map(); | ||
| let predecessors = new Map(); | ||
| let v = this.vertices[index]; | ||
| if (v) { | ||
| let color = this.initColor(); | ||
| let queue = new Queue(); | ||
| queue.enqueue(v); | ||
| color.set(v, 'grey'); | ||
| let vertex = this.vertexMap.get(data); | ||
| // calc | ||
| if (vertex) { | ||
| // init | ||
| this.vertices.forEach((item) => { | ||
| distance.set(item, 0); | ||
| predecessors.set(item, null); | ||
| af(this.vertexMap.keys()).forEach(data => { | ||
| distance.set(data, NPF); // 所有距离设置为正无穷大 | ||
| predecessors.set(data, null); // 所有前置节点设置为null | ||
| }); | ||
| while (!queue.size()) { | ||
| let u = queue.dequeue(); | ||
| let neibors = this.adjList.get(u); | ||
| neibors.forEach((item) => { | ||
| if (color.get(item) === 'white') { | ||
| queue.enqueue(item); | ||
| color.set(item, 'grey'); | ||
| distance.set(item, distance.get(u) + 1); | ||
| predecessors.set(item, u); | ||
| let dataQueue = new Queue(); | ||
| distance.set(data, 0); | ||
| dataQueue.enqueue(data); | ||
| vertex.status = 'discovery'; | ||
| while (!dataQueue.isEmpty()) { | ||
| let curData = dataQueue.dequeue(); | ||
| let arr = this.adjTable.get(curData); | ||
| arr.forEach(vt => { | ||
| if (vt.status === 'cover') { | ||
| distance.set(vt.data, distance.get(curData) + 1); | ||
| predecessors.set(vt.data, curData); | ||
| dataQueue.enqueue(vt.data); | ||
| vt.status = 'discovery'; | ||
| } | ||
| }); | ||
| color.set(u, 'black'); | ||
| this.vertexMap.get(curData).status = 'visited'; | ||
| } | ||
| } | ||
| return { | ||
| distance, | ||
| predecessors, | ||
| }; | ||
| return { distance, predecessors }; | ||
| } | ||
| getPath(fromIndex, toIndex) { | ||
| let queue = new Queue(); | ||
| let to = this.vertices[toIndex]; | ||
| let from = this.vertices[fromIndex]; | ||
| if (to && from) { | ||
| let { predecessors } = this.shortestPath(fromIndex); | ||
| let cur = to; | ||
| while (cur) { | ||
| queue.enqueue(cur); | ||
| cur = predecessors.get(cur); | ||
| } | ||
| getPath(from, to) { | ||
| let arr = []; | ||
| let cur = to; | ||
| let { predecessors } = this.shortestPath(from); | ||
| while (cur) { | ||
| arr.unshift(cur); | ||
| cur = predecessors.get(cur); | ||
| } | ||
| queue.reverse(); | ||
| return queue; | ||
| // 检查 | ||
| if (arr[0] === from && arr[arr.length - 1] === to) { | ||
| return arr; | ||
| } | ||
| else { | ||
| return []; | ||
| } | ||
| } | ||
| } | ||
| export { Graph }; | ||
| class DirectionGraph extends Graph { | ||
| constructor() { | ||
| super(); | ||
| // this.direction = true | ||
| } | ||
| putEdge(a, b) { | ||
| this.adjMatrix.get(a).set(b, this.createEdge(a, b)); | ||
| this.adjTable.get(a).add(this.vertexMap.get(b)); | ||
| } | ||
| removeEdge(a, b) { | ||
| let temp = this.adjMatrix.get(a); | ||
| let edge = temp.get(b); | ||
| temp.delete(b); | ||
| this.adjTable.get(a).delete(this.vertexMap.get(b)); | ||
| return edge; | ||
| } | ||
| } | ||
| class UndirectionGraph extends Graph { | ||
| constructor() { | ||
| super(); | ||
| } | ||
| putEdge(a, b) { | ||
| this.adjMatrix.get(a).set(b, this.createEdge(a, b)); | ||
| this.adjMatrix.get(b).set(a, this.createEdge(b, a)); | ||
| this.adjTable.get(a).add(this.vertexMap.get(b)); | ||
| this.adjTable.get(b).add(this.vertexMap.get(a)); | ||
| } | ||
| removeEdge(a, b) { | ||
| let edge = []; | ||
| let temp = this.adjMatrix.get(a); | ||
| edge.push(temp.get(b)); | ||
| temp.delete(b); | ||
| temp = this.adjMatrix.get(b); | ||
| edge.push(temp.get(a)); | ||
| temp.delete(a); | ||
| this.adjTable.get(a).delete(this.vertexMap.get(b)); | ||
| this.adjTable.get(b).delete(this.vertexMap.get(a)); | ||
| return edge; | ||
| } | ||
| } | ||
| export { | ||
| // Graph | ||
| DirectionGraph, UndirectionGraph, }; |
@@ -17,2 +17,3 @@ import { Stack } from './stack'; | ||
| import { Lru, Fifo, Lfu } from './store'; | ||
| import { DirectionGraph, UndirectionGraph } from './graph'; | ||
| export { Stack, Queue, PriorityQueue, SingleChain, DoublyChain, SingleCircleChain, DoublyCircleChain, | ||
@@ -26,2 +27,2 @@ // PSet, | ||
| // RedBackTree, | ||
| order, Lru, Fifo, Lfu, }; | ||
| order, Lru, Fifo, Lfu, DirectionGraph, UndirectionGraph, }; |
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
New alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Fixed alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Improved metrics
- Total package byte prevSize
- increased by13.71%
463770
- Number of package files
- increased by13.04%
78
- Lines of code
- increased by9.8%
7022
No dependency changes