data-footstone - npm Package Compare versions

Comparing version 0.1.13 to 0.1.14

dist_cjs/index.js

@@ -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

dist_esm/index.js

@@ -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

package.json

 {
   "name": "data-footstone",
-  "version": "0.1.13",
+  "version": "0.1.14",
   "description": "data structure",
@@ -75,3 +75,3 @@ "author": "feigebaobei <[e-mail]>",
   },
-  "gitHead": "9a8b00dcbc961707886c7d03db1a0541fea137d4"
+  "gitHead": "c9a99b1ecf5ea5846245c036de8f4c7909dcabb6"
 }

tscDist/src/graph.js

 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, };

tscDist/src/index.js

@@ -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, };

No alert changes

Improved metrics

Total package byte prevSize

463770

13.71%

Number of package files

78

13.04%

Lines of code

7022

9.8%

No dependency changes