Spaces:
Build error
Build error
| import * as _ from 'lodash-es'; | |
| import { PriorityQueue } from '../data/priority-queue.js'; | |
| import { Graph } from '../graph.js'; | |
| export { prim }; | |
| function prim(g, weightFunc) { | |
| var result = new Graph(); | |
| var parents = {}; | |
| var pq = new PriorityQueue(); | |
| var v; | |
| function updateNeighbors(edge) { | |
| var w = edge.v === v ? edge.w : edge.v; | |
| var pri = pq.priority(w); | |
| if (pri !== undefined) { | |
| var edgeWeight = weightFunc(edge); | |
| if (edgeWeight < pri) { | |
| parents[w] = v; | |
| pq.decrease(w, edgeWeight); | |
| } | |
| } | |
| } | |
| if (g.nodeCount() === 0) { | |
| return result; | |
| } | |
| _.each(g.nodes(), function (v) { | |
| pq.add(v, Number.POSITIVE_INFINITY); | |
| result.setNode(v); | |
| }); | |
| // Start from an arbitrary node | |
| pq.decrease(g.nodes()[0], 0); | |
| var init = false; | |
| while (pq.size() > 0) { | |
| v = pq.removeMin(); | |
| if (_.has(parents, v)) { | |
| result.setEdge(v, parents[v]); | |
| } else if (init) { | |
| throw new Error('Input graph is not connected: ' + g); | |
| } else { | |
| init = true; | |
| } | |
| g.nodeEdges(v).forEach(updateNeighbors); | |
| } | |
| return result; | |
| } | |