@mpppk/lib - npm Package Compare versions

Comparing version 0.0.14 to 0.0.16

dist/algorithm/dag-forest.d.ts

@@ -119,4 +119,9 @@ import { NonEmptyArray } from '../common.js';
     findPathByString(query: string, mapper: (n: Node) => string, resultNum: number | undefined, costF: CostFunction<Node, EdgeValue>): FindPathCandidate[];
+    findPathByString2(query: string, mapper: (n: Node) => string, costF: CostFunction<Node, EdgeValue>): Generator<FindPathCandidate, void, FindPartialPathOp | undefined>;
+    /**
+     * Dagごとの最小パスを返す
+     */
+    findMinCostPerDag(query: string, mapper: (n: Node) => string, costF: CostFunction<Node, EdgeValue>, minCost: number): Generator<FindPathCandidate>;
 }
 
 export { DagForest, type DagForestData, DagPriorityMap, type FindPartialPathMatcher, type FindPartialPathOp, type FindPathCandidate, type ForestFindWaypointsPathResult, VisitedForestPathMap, VisitedForestPathQueue };

dist/algorithm/dag-forest.js

@@ -614,12 +614,18 @@ "use strict";
     const { from, to } = options;
-    debug("first:findPath", { from, to: waypoints[0] });
-    generators.push(this.findPath({ ...options, from, to: waypoints[0] }));
+    debug("first:findShortestPath", { from, to: waypoints[0] });
+    generators.push(
+      this.findShortestPath({ ...options, from, to: waypoints[0] })
+    );
     for (let i = 1; i < waypoints.length; i++) {
       const [from2, to2] = [waypoints[i - 1], waypoints[i]];
-      debug("second:findPath", { from: from2, to: waypoints[0] });
-      generators.push(this.findPath({ ...options, from: from2, to: to2 }));
+      debug("second:findShortestPath", { from: from2, to: waypoints[0] });
+      generators.push(this.findShortestPath({ ...options, from: from2, to: to2 }));
     }
     const lastWaypoint = waypoints[waypoints.length - 1];
-    debug("last:findPath", { from: lastWaypoint, to });
-    generators.push(this.findPath({ ...options, from: lastWaypoint, to }));
+    if (!this.leafs.includes(lastWaypoint)) {
+      debug("last:findShortestPath", { from: lastWaypoint, to });
+      generators.push(
+        this.findShortestPath({ ...options, from: lastWaypoint, to })
+      );
+    }
     const f = function* (generators2) {
@@ -646,2 +652,71 @@ const generators3 = [...generators2];
   }
+  calcMinPathCost(from, costF) {
+    const queue = (() => {
+      const costs = /* @__PURE__ */ new Map();
+      const queue2 = PriorityQueue.newAsc(
+        (id) => costs.get(id)?.cost ?? Infinity,
+        newPriorityQueueDebugger(debug)
+      );
+      const get = (node) => {
+        return costs.get(node) ?? { cost: Infinity, minCostPrev: [] };
+      };
+      return {
+        enqueue: (node, cost, minCostPrev) => {
+          costs.set(node, { cost, minCostPrev });
+          queue2.push(node);
+        },
+        pop: () => {
+          const id = queue2.pop();
+          const children = this.edges.get(id)?.children ?? [];
+          return { ...get(id), children, id };
+        },
+        size: () => queue2.size(),
+        get,
+        getCosts: () => costs
+      };
+    })();
+    for (const f of from) {
+      queue.enqueue(f, 0, []);
+    }
+    while (queue.size() > 0) {
+      const { id, cost: fromCost, children } = queue.pop();
+      for (const child of children) {
+        const edgeCost = costF(child, this);
+        const toC = queue.get(child.to);
+        const newCost = fromCost + edgeCost;
+        if (toC === void 0 || toC.cost > fromCost + edgeCost) {
+          queue.enqueue(child.to, fromCost + edgeCost, [id]);
+        } else if (toC.cost === newCost) {
+          toC.minCostPrev.push(id);
+        }
+      }
+    }
+    return queue.getCosts();
+  }
+  *findShortestPath(options = defaultFindPathOptions()) {
+    const costs = this.calcMinPathCost(
+      options.from ? [options.from] : this.roots,
+      options.costF
+    );
+    function* dfs(path, prev) {
+      if (prev.length === 0) {
+        yield path;
+      }
+      for (const p of prev) {
+        yield* dfs([p, ...path], costs.get(p).minCostPrev);
+      }
+    }
+    const to = options.to === void 0 ? [...this.leafs] : [options.to];
+    to.sort(
+      (t1, t2) => (costs.get(t1)?.cost ?? Infinity) - (costs.get(t2)?.cost ?? Infinity)
+    );
+    for (const t of to) {
+      for (const p of dfs([t], costs.get(t).minCostPrev)) {
+        yield {
+          path: p,
+          cost: costs.get(t).cost + (options.defaultCost ?? 0)
+        };
+      }
+    }
+  }
   *findPath(options = defaultFindPathOptions()) {
@@ -945,3 +1020,6 @@ debug(`findPath:start from(${options.from}) to(${options.to})`);
     const finder = new StringFinder(mapper);
-    const visitedQueue = new VisitedForestPathQueue(this.dags.priorityMap, 5);
+    const visitedQueue = new VisitedForestPathQueue(
+      this.dags.priorityMap,
+      resultNum
+    );
     debug2("findPathByString", { query, resultNum });
@@ -959,2 +1037,41 @@ for (const partialPath of this.findPartialPath(finder.toMatcher(query))) {
   }
+  *findPathByString2(query, mapper, costF) {
+    const finder = new StringFinder(mapper);
+    debug2("findPathByString2", query);
+    const gen = this.findPartialPath(finder.toMatcher(query));
+    for (let [r, op] = [
+      gen.next(void 0),
+      void 0
+    ]; !r.done; r = gen.next(op)) {
+      const partialPath = r.value;
+      const dag = this.dags.get(partialPath.dagId);
+      const nep = NonEmptyArray.parse(partialPath.path);
+      for (const path of dag.findWaypointPath(nep, { costF })) {
+        op = yield { path, dagId: partialPath.dagId };
+        if (op === "next-dag") {
+          break;
+        }
+      }
+    }
+  }
+  /**
+   * Dagごとの最小パスを返す
+   */
+  *findMinCostPerDag(query, mapper, costF, minCost) {
+    const gen = this.findPathByString2(query, mapper, costF);
+    const costMap = /* @__PURE__ */ new Map();
+    for (let r = gen.next(void 0); !r.done; r = gen.next("next-dag")) {
+      const v = r.value;
+      if (v.path.cost <= minCost) {
+        yield v;
+      } else {
+        costMap.set(v.path.cost, [...costMap.get(v.path.cost) ?? [], v]);
+      }
+    }
+    for (const cost of [...costMap.keys()].sort()) {
+      for (const v of costMap.get(cost) ?? []) {
+        yield v;
+      }
+    }
+  }
 };
@@ -961,0 +1078,0 @@ // Annotate the CommonJS export names for ESM import in node:

dist/algorithm/dag.d.ts

@@ -88,2 +88,7 @@ import { NodeID } from './values.js';
     }>, void, unknown>;
+    private calcMinPathCost;
+    findShortestPath(options?: FindPathOptions<Node, EdgeValue>): Generator<{
+        path: NodeID[];
+        cost: number;
+    }, void, unknown>;
     findPath(options?: FindPathOptions<Node, EdgeValue>): Generator<Readonly<{
@@ -90,0 +95,0 @@ path: NodeID[];

dist/algorithm/dag.js

@@ -426,12 +426,18 @@ "use strict";
     const { from, to } = options;
-    debug("first:findPath", { from, to: waypoints[0] });
-    generators.push(this.findPath({ ...options, from, to: waypoints[0] }));
+    debug("first:findShortestPath", { from, to: waypoints[0] });
+    generators.push(
+      this.findShortestPath({ ...options, from, to: waypoints[0] })
+    );
     for (let i = 1; i < waypoints.length; i++) {
       const [from2, to2] = [waypoints[i - 1], waypoints[i]];
-      debug("second:findPath", { from: from2, to: waypoints[0] });
-      generators.push(this.findPath({ ...options, from: from2, to: to2 }));
+      debug("second:findShortestPath", { from: from2, to: waypoints[0] });
+      generators.push(this.findShortestPath({ ...options, from: from2, to: to2 }));
     }
     const lastWaypoint = waypoints[waypoints.length - 1];
-    debug("last:findPath", { from: lastWaypoint, to });
-    generators.push(this.findPath({ ...options, from: lastWaypoint, to }));
+    if (!this.leafs.includes(lastWaypoint)) {
+      debug("last:findShortestPath", { from: lastWaypoint, to });
+      generators.push(
+        this.findShortestPath({ ...options, from: lastWaypoint, to })
+      );
+    }
     const f = function* (generators2) {
@@ -458,2 +464,71 @@ const generators3 = [...generators2];
   }
+  calcMinPathCost(from, costF) {
+    const queue = (() => {
+      const costs = /* @__PURE__ */ new Map();
+      const queue2 = PriorityQueue.newAsc(
+        (id) => costs.get(id)?.cost ?? Infinity,
+        newPriorityQueueDebugger(debug)
+      );
+      const get = (node) => {
+        return costs.get(node) ?? { cost: Infinity, minCostPrev: [] };
+      };
+      return {
+        enqueue: (node, cost, minCostPrev) => {
+          costs.set(node, { cost, minCostPrev });
+          queue2.push(node);
+        },
+        pop: () => {
+          const id = queue2.pop();
+          const children = this.edges.get(id)?.children ?? [];
+          return { ...get(id), children, id };
+        },
+        size: () => queue2.size(),
+        get,
+        getCosts: () => costs
+      };
+    })();
+    for (const f of from) {
+      queue.enqueue(f, 0, []);
+    }
+    while (queue.size() > 0) {
+      const { id, cost: fromCost, children } = queue.pop();
+      for (const child of children) {
+        const edgeCost = costF(child, this);
+        const toC = queue.get(child.to);
+        const newCost = fromCost + edgeCost;
+        if (toC === void 0 || toC.cost > fromCost + edgeCost) {
+          queue.enqueue(child.to, fromCost + edgeCost, [id]);
+        } else if (toC.cost === newCost) {
+          toC.minCostPrev.push(id);
+        }
+      }
+    }
+    return queue.getCosts();
+  }
+  *findShortestPath(options = defaultFindPathOptions()) {
+    const costs = this.calcMinPathCost(
+      options.from ? [options.from] : this.roots,
+      options.costF
+    );
+    function* dfs(path, prev) {
+      if (prev.length === 0) {
+        yield path;
+      }
+      for (const p of prev) {
+        yield* dfs([p, ...path], costs.get(p).minCostPrev);
+      }
+    }
+    const to = options.to === void 0 ? [...this.leafs] : [options.to];
+    to.sort(
+      (t1, t2) => (costs.get(t1)?.cost ?? Infinity) - (costs.get(t2)?.cost ?? Infinity)
+    );
+    for (const t of to) {
+      for (const p of dfs([t], costs.get(t).minCostPrev)) {
+        yield {
+          path: p,
+          cost: costs.get(t).cost + (options.defaultCost ?? 0)
+        };
+      }
+    }
+  }
   *findPath(options = defaultFindPathOptions()) {
@@ -460,0 +535,0 @@ debug(`findPath:start from(${options.from}) to(${options.to})`);

dist/algorithm/index.js

@@ -451,12 +451,18 @@ "use strict";
     const { from, to } = options;
-    debug("first:findPath", { from, to: waypoints[0] });
-    generators.push(this.findPath({ ...options, from, to: waypoints[0] }));
+    debug("first:findShortestPath", { from, to: waypoints[0] });
+    generators.push(
+      this.findShortestPath({ ...options, from, to: waypoints[0] })
+    );
     for (let i = 1; i < waypoints.length; i++) {
       const [from2, to2] = [waypoints[i - 1], waypoints[i]];
-      debug("second:findPath", { from: from2, to: waypoints[0] });
-      generators.push(this.findPath({ ...options, from: from2, to: to2 }));
+      debug("second:findShortestPath", { from: from2, to: waypoints[0] });
+      generators.push(this.findShortestPath({ ...options, from: from2, to: to2 }));
     }
     const lastWaypoint = waypoints[waypoints.length - 1];
-    debug("last:findPath", { from: lastWaypoint, to });
-    generators.push(this.findPath({ ...options, from: lastWaypoint, to }));
+    if (!this.leafs.includes(lastWaypoint)) {
+      debug("last:findShortestPath", { from: lastWaypoint, to });
+      generators.push(
+        this.findShortestPath({ ...options, from: lastWaypoint, to })
+      );
+    }
     const f = function* (generators2) {
@@ -483,2 +489,71 @@ const generators3 = [...generators2];
   }
+  calcMinPathCost(from, costF) {
+    const queue = (() => {
+      const costs = /* @__PURE__ */ new Map();
+      const queue2 = PriorityQueue.newAsc(
+        (id) => costs.get(id)?.cost ?? Infinity,
+        newPriorityQueueDebugger(debug)
+      );
+      const get = (node) => {
+        return costs.get(node) ?? { cost: Infinity, minCostPrev: [] };
+      };
+      return {
+        enqueue: (node, cost, minCostPrev) => {
+          costs.set(node, { cost, minCostPrev });
+          queue2.push(node);
+        },
+        pop: () => {
+          const id = queue2.pop();
+          const children = this.edges.get(id)?.children ?? [];
+          return { ...get(id), children, id };
+        },
+        size: () => queue2.size(),
+        get,
+        getCosts: () => costs
+      };
+    })();
+    for (const f of from) {
+      queue.enqueue(f, 0, []);
+    }
+    while (queue.size() > 0) {
+      const { id, cost: fromCost, children } = queue.pop();
+      for (const child of children) {
+        const edgeCost = costF(child, this);
+        const toC = queue.get(child.to);
+        const newCost = fromCost + edgeCost;
+        if (toC === void 0 || toC.cost > fromCost + edgeCost) {
+          queue.enqueue(child.to, fromCost + edgeCost, [id]);
+        } else if (toC.cost === newCost) {
+          toC.minCostPrev.push(id);
+        }
+      }
+    }
+    return queue.getCosts();
+  }
+  *findShortestPath(options = defaultFindPathOptions()) {
+    const costs = this.calcMinPathCost(
+      options.from ? [options.from] : this.roots,
+      options.costF
+    );
+    function* dfs(path, prev) {
+      if (prev.length === 0) {
+        yield path;
+      }
+      for (const p of prev) {
+        yield* dfs([p, ...path], costs.get(p).minCostPrev);
+      }
+    }
+    const to = options.to === void 0 ? [...this.leafs] : [options.to];
+    to.sort(
+      (t1, t2) => (costs.get(t1)?.cost ?? Infinity) - (costs.get(t2)?.cost ?? Infinity)
+    );
+    for (const t of to) {
+      for (const p of dfs([t], costs.get(t).minCostPrev)) {
+        yield {
+          path: p,
+          cost: costs.get(t).cost + (options.defaultCost ?? 0)
+        };
+      }
+    }
+  }
   *findPath(options = defaultFindPathOptions()) {
@@ -961,3 +1036,6 @@ debug(`findPath:start from(${options.from}) to(${options.to})`);
     const finder = new StringFinder(mapper);
-    const visitedQueue = new VisitedForestPathQueue(this.dags.priorityMap, 5);
+    const visitedQueue = new VisitedForestPathQueue(
+      this.dags.priorityMap,
+      resultNum
+    );
     debug2("findPathByString", { query, resultNum });
@@ -975,2 +1053,41 @@ for (const partialPath of this.findPartialPath(finder.toMatcher(query))) {
   }
+  *findPathByString2(query, mapper, costF) {
+    const finder = new StringFinder(mapper);
+    debug2("findPathByString2", query);
+    const gen = this.findPartialPath(finder.toMatcher(query));
+    for (let [r, op] = [
+      gen.next(void 0),
+      void 0
+    ]; !r.done; r = gen.next(op)) {
+      const partialPath = r.value;
+      const dag = this.dags.get(partialPath.dagId);
+      const nep = NonEmptyArray.parse(partialPath.path);
+      for (const path of dag.findWaypointPath(nep, { costF })) {
+        op = yield { path, dagId: partialPath.dagId };
+        if (op === "next-dag") {
+          break;
+        }
+      }
+    }
+  }
+  /**
+   * Dagごとの最小パスを返す
+   */
+  *findMinCostPerDag(query, mapper, costF, minCost) {
+    const gen = this.findPathByString2(query, mapper, costF);
+    const costMap = /* @__PURE__ */ new Map();
+    for (let r = gen.next(void 0); !r.done; r = gen.next("next-dag")) {
+      const v = r.value;
+      if (v.path.cost <= minCost) {
+        yield v;
+      } else {
+        costMap.set(v.path.cost, [...costMap.get(v.path.cost) ?? [], v]);
+      }
+    }
+    for (const cost of [...costMap.keys()].sort()) {
+      for (const v of costMap.get(cost) ?? []) {
+        yield v;
+      }
+    }
+  }
 };
@@ -977,0 +1094,0 @@ // Annotate the CommonJS export names for ESM import in node:

dist/index.js

@@ -527,12 +527,18 @@ "use strict";
     const { from, to } = options;
-    debug("first:findPath", { from, to: waypoints[0] });
-    generators.push(this.findPath({ ...options, from, to: waypoints[0] }));
+    debug("first:findShortestPath", { from, to: waypoints[0] });
+    generators.push(
+      this.findShortestPath({ ...options, from, to: waypoints[0] })
+    );
     for (let i = 1; i < waypoints.length; i++) {
       const [from2, to2] = [waypoints[i - 1], waypoints[i]];
-      debug("second:findPath", { from: from2, to: waypoints[0] });
-      generators.push(this.findPath({ ...options, from: from2, to: to2 }));
+      debug("second:findShortestPath", { from: from2, to: waypoints[0] });
+      generators.push(this.findShortestPath({ ...options, from: from2, to: to2 }));
     }
     const lastWaypoint = waypoints[waypoints.length - 1];
-    debug("last:findPath", { from: lastWaypoint, to });
-    generators.push(this.findPath({ ...options, from: lastWaypoint, to }));
+    if (!this.leafs.includes(lastWaypoint)) {
+      debug("last:findShortestPath", { from: lastWaypoint, to });
+      generators.push(
+        this.findShortestPath({ ...options, from: lastWaypoint, to })
+      );
+    }
     const f = function* (generators2) {
@@ -559,2 +565,71 @@ const generators3 = [...generators2];
   }
+  calcMinPathCost(from, costF) {
+    const queue = (() => {
+      const costs = /* @__PURE__ */ new Map();
+      const queue2 = PriorityQueue.newAsc(
+        (id) => costs.get(id)?.cost ?? Infinity,
+        newPriorityQueueDebugger(debug)
+      );
+      const get = (node) => {
+        return costs.get(node) ?? { cost: Infinity, minCostPrev: [] };
+      };
+      return {
+        enqueue: (node, cost, minCostPrev) => {
+          costs.set(node, { cost, minCostPrev });
+          queue2.push(node);
+        },
+        pop: () => {
+          const id = queue2.pop();
+          const children = this.edges.get(id)?.children ?? [];
+          return { ...get(id), children, id };
+        },
+        size: () => queue2.size(),
+        get,
+        getCosts: () => costs
+      };
+    })();
+    for (const f of from) {
+      queue.enqueue(f, 0, []);
+    }
+    while (queue.size() > 0) {
+      const { id, cost: fromCost, children } = queue.pop();
+      for (const child of children) {
+        const edgeCost = costF(child, this);
+        const toC = queue.get(child.to);
+        const newCost = fromCost + edgeCost;
+        if (toC === void 0 || toC.cost > fromCost + edgeCost) {
+          queue.enqueue(child.to, fromCost + edgeCost, [id]);
+        } else if (toC.cost === newCost) {
+          toC.minCostPrev.push(id);
+        }
+      }
+    }
+    return queue.getCosts();
+  }
+  *findShortestPath(options = defaultFindPathOptions()) {
+    const costs = this.calcMinPathCost(
+      options.from ? [options.from] : this.roots,
+      options.costF
+    );
+    function* dfs(path, prev) {
+      if (prev.length === 0) {
+        yield path;
+      }
+      for (const p of prev) {
+        yield* dfs([p, ...path], costs.get(p).minCostPrev);
+      }
+    }
+    const to = options.to === void 0 ? [...this.leafs] : [options.to];
+    to.sort(
+      (t1, t2) => (costs.get(t1)?.cost ?? Infinity) - (costs.get(t2)?.cost ?? Infinity)
+    );
+    for (const t of to) {
+      for (const p of dfs([t], costs.get(t).minCostPrev)) {
+        yield {
+          path: p,
+          cost: costs.get(t).cost + (options.defaultCost ?? 0)
+        };
+      }
+    }
+  }
   *findPath(options = defaultFindPathOptions()) {
@@ -1001,3 +1076,6 @@ debug(`findPath:start from(${options.from}) to(${options.to})`);
     const finder = new StringFinder(mapper);
-    const visitedQueue = new VisitedForestPathQueue(this.dags.priorityMap, 5);
+    const visitedQueue = new VisitedForestPathQueue(
+      this.dags.priorityMap,
+      resultNum
+    );
     debug2("findPathByString", { query, resultNum });
@@ -1015,2 +1093,41 @@ for (const partialPath of this.findPartialPath(finder.toMatcher(query))) {
   }
+  *findPathByString2(query, mapper, costF) {
+    const finder = new StringFinder(mapper);
+    debug2("findPathByString2", query);
+    const gen = this.findPartialPath(finder.toMatcher(query));
+    for (let [r, op] = [
+      gen.next(void 0),
+      void 0
+    ]; !r.done; r = gen.next(op)) {
+      const partialPath = r.value;
+      const dag = this.dags.get(partialPath.dagId);
+      const nep = NonEmptyArray.parse(partialPath.path);
+      for (const path of dag.findWaypointPath(nep, { costF })) {
+        op = yield { path, dagId: partialPath.dagId };
+        if (op === "next-dag") {
+          break;
+        }
+      }
+    }
+  }
+  /**
+   * Dagごとの最小パスを返す
+   */
+  *findMinCostPerDag(query, mapper, costF, minCost) {
+    const gen = this.findPathByString2(query, mapper, costF);
+    const costMap = /* @__PURE__ */ new Map();
+    for (let r = gen.next(void 0); !r.done; r = gen.next("next-dag")) {
+      const v = r.value;
+      if (v.path.cost <= minCost) {
+        yield v;
+      } else {
+        costMap.set(v.path.cost, [...costMap.get(v.path.cost) ?? [], v]);
+      }
+    }
+    for (const cost of [...costMap.keys()].sort()) {
+      for (const v of costMap.get(cost) ?? []) {
+        yield v;
+      }
+    }
+  }
 };
@@ -1017,0 +1134,0 @@ // Annotate the CommonJS export names for ESM import in node:

package.json

 {
   "name": "@mpppk/lib",
-  "version": "0.0.14",
+  "version": "0.0.16",
   "scripts": {
@@ -5,0 +5,0 @@ "build": "tsup ./src",

No alert changes

Improved metrics

Total package byte prevSize

3613974

increased by1.01%

Lines of code

107595

increased by1.11%

No dependency changes