{
  "version": 3,
  "sources": ["../index.ts", "../lib/graph.ts", "../lib/version.ts", "../lib/json.ts", "../lib/alg/index.ts", "../lib/alg/bellman-ford.ts", "../lib/alg/components.ts", "../lib/data/priority-queue.ts", "../lib/alg/dijkstra.ts", "../lib/alg/dijkstra-all.ts", "../lib/alg/tarjan.ts", "../lib/alg/find-cycles.ts", "../lib/alg/floyd-warshall.ts", "../lib/alg/topsort.ts", "../lib/alg/is-acyclic.ts", "../lib/alg/reduce.ts", "../lib/alg/dfs.ts", "../lib/alg/postorder.ts", "../lib/alg/preorder.ts", "../lib/alg/prim.ts", "../lib/alg/shortest-paths.ts"],
  "sourcesContent": ["/**\n * Copyright (c) 2014, Chris Pettitt\n * All rights reserved.\n *\n * Redistribution and use in source and binary forms, with or without\n * modification, are permitted provided that the following conditions are met:\n *\n * 1. Redistributions of source code must retain the above copyright notice, this\n * list of conditions and the following disclaimer.\n *\n * 2. Redistributions in binary form must reproduce the above copyright notice,\n * this list of conditions and the following disclaimer in the documentation\n * and/or other materials provided with the distribution.\n *\n * 3. Neither the name of the copyright holder nor the names of its contributors\n * may be used to endorse or promote products derived from this software without\n * specific prior written permission.\n *\n * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS \"AS IS\" AND\n * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED\n * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE\n * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE\n * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL\n * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR\n * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER\n * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,\n * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE\n * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n */\n\nexport {Graph} from './lib/graph';\nexport {version} from './lib/version';\nexport * as json from './lib/json';\nexport * as alg from './lib/alg/index';\n\nexport type {GraphOptions, Edge, Path, WeightFunction, EdgeFunction, Label} from './lib/types.js';\n", "import type {Edge, EdgeLabelFactory, GraphOptions, Label, NodeLabelFactory} from './types';\n\nconst DEFAULT_EDGE_NAME = \"\\x00\";\nconst GRAPH_NODE = \"\\x00\";\nconst EDGE_KEY_DELIM = \"\\x01\";\n\n// Implementation notes:\n//\n//  * Node id query functions should return string ids for the nodes\n//  * Edge id query functions should return an \"edgeObj\", edge object, that is\n//    composed of enough information to uniquely identify an edge: {v, w, name}.\n//  * Internally we use an \"edgeId\", a stringified form of the edgeObj, to\n//    reference edges. This is because we need a performant way to look these\n//    edges up and, object properties, which have string keys, are the closest\n//    we're going to get to a performant hashtable in JavaScript.\n\nexport class Graph<GraphLabel = Label, NodeLabel = Label, EdgeLabel = Label> {\n    private _isDirected: boolean = true;\n    private _isMultigraph: boolean = false;\n    private _isCompound: boolean = false;\n\n    // Label for the graph itself\n    private _label!: GraphLabel;\n    // v -> label\n    private _nodes: Record<string, NodeLabel> = {};\n    // v -> edgeObj\n    private _in: Record<string, Record<string, Edge>> = {};\n    // u -> v -> Number\n    private _preds: Record<string, Record<string, number>> = {};\n    // v -> edgeObj\n    private _out: Record<string, Record<string, Edge>> = {};\n    // v -> w -> Number\n    private _sucs: Record<string, Record<string, number>> = {};\n    // e -> edgeObj\n    private _edgeObjs: Record<string, Edge> = {};\n    // e -> label\n    private _edgeLabels: Record<string, EdgeLabel> = {};\n    /* Number of nodes in the graph. Should only be changed by the implementation. */\n    private _nodeCount: number = 0;\n    /* Number of edges in the graph. Should only be changed by the implementation. */\n    private _edgeCount: number = 0;\n    private _parent?: Record<string, string>;\n    private _children?: Record<string, Record<string, boolean>>;\n\n    constructor(opts?: GraphOptions) {\n        if (opts) {\n            this._isDirected = \"directed\" in opts ? opts.directed! : true;\n            this._isMultigraph = \"multigraph\" in opts ? opts.multigraph! : false;\n            this._isCompound = \"compound\" in opts ? opts.compound! : false;\n        }\n\n        if (this._isCompound) {\n            // v -> parent\n            this._parent = {};\n\n            // v -> children\n            this._children = {};\n            this._children[GRAPH_NODE] = {};\n        }\n    }\n\n    /**\n     * Whether graph was created with 'directed' flag set to true or not.\n     *\n     * @returns whether the graph edges have an orientation.\n     */\n    isDirected(): boolean {\n        return this._isDirected;\n    }\n\n    /**\n     * Whether graph was created with 'multigraph' flag set to true or not.\n     *\n     * @returns whether the pair of nodes of the graph can have multiple edges.\n     */\n    isMultigraph(): boolean {\n        return this._isMultigraph;\n    }\n\n    /* === Graph functions ========= */\n\n    /**\n     * Whether graph was created with 'compound' flag set to true or not.\n     *\n     * @returns whether a node of the graph can have subnodes.\n     */\n    isCompound(): boolean {\n        return this._isCompound;\n    }\n\n    /**\n     * Sets the label of the graph.\n     *\n     * @param label - label value.\n     * @returns the graph, allowing this to be chained with other functions.\n     */\n    setGraph(label: GraphLabel): this {\n        this._label = label;\n        return this;\n    }\n\n    /**\n     * Gets the graph label.\n     *\n     * @returns currently assigned label for the graph or undefined if no label assigned.\n     */\n    graph(): GraphLabel {\n        // TODO: This should return undefined if no label was assigned, but that would be a breaking change.\n        return this._label;\n    }\n\n    /**\n     * Sets the default node label. This label will be assigned as default label\n     * in case if no label was specified while setting a node.\n     * Complexity: O(1).\n     *\n     * @param labelOrFn - default node label or label factory function.\n     * @returns the graph, allowing this to be chained with other functions.\n     */\n    setDefaultNodeLabel(labelOrFn: NodeLabel | NodeLabelFactory<NodeLabel>): this {\n        if (typeof labelOrFn !== 'function') {\n            this._defaultNodeLabelFn = () => labelOrFn;\n        } else {\n            this._defaultNodeLabelFn = labelOrFn as NodeLabelFactory<NodeLabel>;\n        }\n\n        return this;\n    }\n\n    /**\n     * Gets the number of nodes in the graph.\n     * Complexity: O(1).\n     *\n     * @returns nodes count.\n     */\n    nodeCount(): number {\n        return this._nodeCount;\n    }\n\n\n    /* === Node functions ========== */\n\n    /**\n     * Gets all nodes of the graph. Note, the in case of compound graph subnodes are\n     * not included in list.\n     * Complexity: O(1).\n     *\n     * @returns list of graph nodes.\n     */\n    nodes(): string[] {\n        return Object.keys(this._nodes);\n    }\n\n    /**\n     * Gets list of nodes without in-edges.\n     * Complexity: O(|V|).\n     *\n     * @returns the graph source nodes.\n     */\n    sources(): string[] {\n        return this.nodes().filter(v => Object.keys(this._in[v]!).length === 0);\n    }\n\n    /**\n     * Gets list of nodes without out-edges.\n     * Complexity: O(|V|).\n     *\n     * @returns the graph sink nodes.\n     */\n    sinks(): string[] {\n        return this.nodes().filter(v => Object.keys(this._out[v]!).length === 0);\n    }\n\n    /**\n     * Invokes setNode method for each node in names list.\n     * Complexity: O(|names|).\n     *\n     * @param names - list of nodes names to be set.\n     * @param label - value to set for each node in list.\n     * @returns the graph, allowing this to be chained with other functions.\n     */\n    setNodes(names: string[], label?: NodeLabel): this {\n        names.forEach((v) => {\n            if (label !== undefined) {\n                this.setNode(v, label);\n            } else {\n                this.setNode(v);\n            }\n        });\n        return this;\n    }\n\n    /**\n     * Creates or updates the value for the node v in the graph. If label is supplied\n     * it is set as the value for the node. If label is not supplied and the node was\n     * created by this call then the default node label will be assigned.\n     * Complexity: O(1).\n     *\n     * @param name - node name.\n     * @param label - value to set for node.\n     * @returns the graph, allowing this to be chained with other functions.\n     */\n    setNode(name: string, label?: NodeLabel): this {\n        if (name in this._nodes) {\n            if (arguments.length > 1) {\n                this._nodes[name] = label!;\n            }\n            return this;\n        }\n\n        this._nodes[name] = arguments.length > 1 ? label! : this._defaultNodeLabelFn(name);\n        if (this._isCompound) {\n            this._parent![name] = GRAPH_NODE;\n            this._children![name] = {};\n            this._children![GRAPH_NODE]![name] = true;\n        }\n        this._in[name] = {};\n        this._preds[name] = {};\n        this._out[name] = {};\n        this._sucs[name] = {};\n        ++this._nodeCount;\n        return this;\n    }\n\n    /**\n     * Gets the label of node with specified name.\n     * Complexity: O(|V|).\n     *\n     * @param name - node name.\n     * @returns label value of the node.\n     */\n    node(name: string): NodeLabel {\n        // TODO: This should return undefined if the node doesn't exist, but that would be a breaking change.\n        return this._nodes[name]!;\n    }\n\n    /**\n     * Detects whether graph has a node with specified name or not.\n     *\n     * @param name - name of the node.\n     * @returns true if graph has node with specified name, false - otherwise.\n     */\n    hasNode(name: string): boolean {\n        return name in this._nodes;\n    }\n\n    /**\n     * Remove the node with the name from the graph or do nothing if the node is not in\n     * the graph. If the node was removed this function also removes any incident\n     * edges.\n     * Complexity: O(1).\n     *\n     * @param name - name of the node.\n     * @returns the graph, allowing this to be chained with other functions.\n     */\n    removeNode(name: string): this {\n        if (name in this._nodes) {\n            const removeEdge = (e: string) => this.removeEdge(this._edgeObjs[e]!);\n            delete this._nodes[name];\n            if (this._isCompound) {\n                this._removeFromParentsChildList(name);\n                delete this._parent![name];\n                this.children(name).forEach((child) => {\n                    this.setParent(child);\n                });\n                delete this._children![name];\n            }\n            Object.keys(this._in[name]!).forEach(removeEdge);\n            delete this._in[name];\n            delete this._preds[name];\n            Object.keys(this._out[name]!).forEach(removeEdge);\n            delete this._out[name];\n            delete this._sucs[name];\n            --this._nodeCount;\n        }\n        return this;\n    }\n\n    /**\n     * Sets node parent for node v if it is defined, or removes the\n     * parent for v if p is undefined. Method throws an exception in case of\n     * invoking it in context of noncompound graph.\n     * Average-case complexity: O(1).\n     *\n     * @param v - node to be child for p.\n     * @param parent - node to be parent for v.\n     * @returns the graph, allowing this to be chained with other functions.\n     */\n    setParent(v: string, parent?: string): this {\n        if (!this._isCompound) {\n            throw new Error(\"Cannot set parent in a non-compound graph\");\n        }\n\n        if (parent === undefined) {\n            parent = GRAPH_NODE;\n        } else {\n            // Coerce parent to string\n            parent += \"\";\n            for (let ancestor: string | undefined = parent; ancestor !== undefined; ancestor = this.parent(ancestor)) {\n                if (ancestor === v) {\n                    throw new Error(\"Setting \" + parent + \" as parent of \" + v +\n                        \" would create a cycle\");\n                }\n            }\n\n            this.setNode(parent);\n        }\n\n        this.setNode(v);\n        this._removeFromParentsChildList(v);\n        this._parent![v] = parent;\n        this._children![parent]![v] = true;\n        return this;\n    }\n\n    /**\n     * Gets parent node for node v.\n     * Complexity: O(1).\n     *\n     * @param v - node to get parent of.\n     * @returns parent node name or void if v has no parent.\n     */\n    parent(v: string): string | undefined {\n        if (this._isCompound) {\n            const parent = this._parent![v];\n            if (parent !== GRAPH_NODE) {\n                return parent;\n            }\n        }\n        return undefined;\n    }\n\n    /**\n     * Gets list of direct children of node v.\n     * Complexity: O(1).\n     *\n     * @param v - node to get children of.\n     * @returns children nodes names list.\n     */\n    children(v: string = GRAPH_NODE): string[] {\n        if (this._isCompound) {\n            const children = this._children![v];\n            if (children) {\n                return Object.keys(children);\n            }\n        } else if (v === GRAPH_NODE) {\n            return this.nodes();\n        } else if (this.hasNode(v)) {\n            return [];\n        }\n        return [];\n    }\n\n    /**\n     * Return all nodes that are predecessors of the specified node or undefined if node v is not in\n     * the graph. Behavior is undefined for undirected graphs - use neighbors instead.\n     * Complexity: O(|V|).\n     *\n     * @param v - node identifier.\n     * @returns node identifiers list or undefined if v is not in the graph.\n     */\n    predecessors(v: string): string[] | undefined {\n        const predsV = this._preds[v];\n        if (predsV) {\n            return Object.keys(predsV);\n        }\n        return undefined;\n    }\n\n    /**\n     * Return all nodes that are successors of the specified node or undefined if node v is not in\n     * the graph. Behavior is undefined for undirected graphs - use neighbors instead.\n     * Complexity: O(|V|).\n     *\n     * @param v - node identifier.\n     * @returns node identifiers list or undefined if v is not in the graph.\n     */\n    successors(v: string): string[] | undefined {\n        const sucsV = this._sucs[v];\n        if (sucsV) {\n            return Object.keys(sucsV);\n        }\n        return undefined;\n    }\n\n    /**\n     * Return all nodes that are predecessors or successors of the specified node or undefined if\n     * node v is not in the graph.\n     * Complexity: O(|V|).\n     *\n     * @param v - node identifier.\n     * @returns node identifiers list or undefined if v is not in the graph.\n     */\n    neighbors(v: string): string[] | undefined {\n        const preds = this.predecessors(v);\n        if (preds) {\n            const union = new Set(preds);\n            const sucs = this.successors(v);\n            if (sucs) {\n                for (const succ of sucs) {\n                    union.add(succ);\n                }\n            }\n\n            return Array.from(union.values());\n        }\n        return undefined;\n    }\n\n    isLeaf(v: string): boolean {\n        let neighbors: string[] | undefined;\n        if (this.isDirected()) {\n            neighbors = this.successors(v);\n        } else {\n            neighbors = this.neighbors(v);\n        }\n        return (neighbors?.length ?? 0) === 0;\n    }\n\n    /**\n     * Creates new graph with nodes filtered via filter. Edges incident to rejected node\n     * are also removed. In case of compound graph, if parent is rejected by filter,\n     * than all its children are rejected too.\n     * Average-case complexity: O(|E|+|V|).\n     *\n     * @param filter - filtration function detecting whether the node should stay or not.\n     * @returns new graph made from current and nodes filtered.\n     */\n    filterNodes(filter: (v: string) => boolean): this {\n        const copy = new (this.constructor as typeof Graph<GraphLabel, NodeLabel, EdgeLabel>)({\n            directed: this._isDirected,\n            multigraph: this._isMultigraph,\n            compound: this._isCompound\n        });\n\n        copy.setGraph(this.graph()!);\n\n        Object.entries(this._nodes).forEach(([v, value]) => {\n            if (filter(v)) {\n                copy.setNode(v, value);\n            }\n        });\n\n        Object.values(this._edgeObjs).forEach((e) => {\n            if (copy.hasNode(e.v) && copy.hasNode(e.w)) {\n                copy.setEdge(e, this.edge(e));\n            }\n        });\n\n        const parents: Record<string, string | undefined> = {};\n        const findParent = (v: string): string | undefined => {\n            const parent = this.parent(v);\n            if (!parent || copy.hasNode(parent)) {\n                parents[v] = parent;\n                return parent;\n            } else if (parent in parents) {\n                return parents[parent];\n            } else {\n                return findParent(parent);\n            }\n        };\n\n        if (this._isCompound) {\n            copy.nodes().forEach(v => copy.setParent(v, findParent(v)));\n        }\n\n        return copy as this;\n    }\n\n    /**\n     * Sets the default edge label. This label will be assigned as default label\n     * in case if no label was specified while setting an edge.\n     * Complexity: O(1).\n     *\n     * @param labelOrFn - default edge label or label factory function.\n     * @returns the graph, allowing this to be chained with other functions.\n     */\n    setDefaultEdgeLabel(labelOrFn: EdgeLabel | EdgeLabelFactory<EdgeLabel>): this {\n        if (typeof labelOrFn !== 'function') {\n            this._defaultEdgeLabelFn = () => labelOrFn;\n        } else {\n            this._defaultEdgeLabelFn = labelOrFn as EdgeLabelFactory<EdgeLabel>;\n        }\n\n        return this;\n    }\n\n    /**\n     * Gets the number of edges in the graph.\n     * Complexity: O(1).\n     *\n     * @returns edges count.\n     */\n    edgeCount(): number {\n        return this._edgeCount;\n    }\n\n    /**\n     * Gets edges of the graph. In case of compound graph subgraphs are not considered.\n     * Complexity: O(|E|).\n     *\n     * @returns graph edges list.\n     */\n    edges(): Edge[] {\n        return Object.values(this._edgeObjs);\n    }\n\n    /* === Edge functions ========== */\n\n    /**\n     * Establish an edges path over the nodes in nodes list. If some edge is already\n     * exists, it will update its label, otherwise it will create an edge between pair\n     * of nodes with label provided or default label if no label provided.\n     * Complexity: O(|nodes|).\n     *\n     * @param nodes - list of nodes to be connected in series.\n     * @param label - value to set for each edge between pairs of nodes.\n     * @returns the graph, allowing this to be chained with other functions.\n     */\n    setPath(nodes: string[], label?: EdgeLabel): this {\n        nodes.reduce((v, w) => {\n            if (label !== undefined) {\n                this.setEdge(v, w, label);\n            } else {\n                this.setEdge(v, w);\n            }\n            return w;\n        });\n        return this;\n    }\n\n    /**\n     * Creates or updates the label for the edge (v, w) with the optionally supplied\n     * name. If label is supplied it is set as the value for the edge. If label is not\n     * supplied and the edge was created by this call then the default edge label will\n     * be assigned. The name parameter is only useful with multigraphs.\n     * Complexity: O(1).\n     *\n     * @param v - edge source node.\n     * @param w - edge sink node.\n     * @param label - value to associate with the edge.\n     * @param name - unique name of the edge in order to identify it in multigraph.\n     * @returns the graph, allowing this to be chained with other functions.\n     */\n    setEdge(v: string, w: string, label?: EdgeLabel, name?: string): this;\n\n    /**\n     * Creates or updates the label for the specified edge. If label is supplied it is\n     * set as the value for the edge. If label is not supplied and the edge was created\n     * by this call then the default edge label will be assigned. The name parameter is\n     * only useful with multigraphs.\n     * Complexity: O(1).\n     *\n     * @param edge - edge descriptor.\n     * @param label - value to associate with the edge.\n     * @returns the graph, allowing this to be chained with other functions.\n     */\n    setEdge(edge: Edge, label?: EdgeLabel): this;\n\n    setEdge(v: string | Edge, w?: string | EdgeLabel, value?: EdgeLabel, name?: string): this {\n        let vStr: string;\n        let wStr: string;\n        let nameStr: string | undefined;\n        let edgeValue: EdgeLabel | undefined;\n        let valueSpecified = false;\n\n        if (typeof v === \"object\" && v !== null && \"v\" in v) {\n            vStr = v.v;\n            wStr = v.w;\n            nameStr = v.name;\n            if (arguments.length === 2) {\n                edgeValue = w as EdgeLabel;\n                valueSpecified = true;\n            }\n        } else {\n            vStr = v;\n            wStr = w as string;\n            nameStr = name;\n            if (arguments.length > 2) {\n                edgeValue = value;\n                valueSpecified = true;\n            }\n        }\n\n        vStr = \"\" + vStr;\n        wStr = \"\" + wStr;\n        if (nameStr !== undefined) {\n            nameStr = \"\" + nameStr;\n        }\n\n        const e = edgeArgsToId(this._isDirected, vStr, wStr, nameStr);\n        if (e in this._edgeLabels) {\n            if (valueSpecified) {\n                this._edgeLabels[e] = edgeValue!;\n            }\n            return this;\n        }\n\n        if (nameStr !== undefined && !this._isMultigraph) {\n            throw new Error(\"Cannot set a named edge when isMultigraph = false\");\n        }\n\n        // It didn't exist, so we need to create it.\n        // First ensure the nodes exist.\n        this.setNode(vStr);\n        this.setNode(wStr);\n\n        this._edgeLabels[e] = valueSpecified ? edgeValue! : this._defaultEdgeLabelFn(vStr, wStr, nameStr);\n\n        // Ensure we add undirected edges in a consistent way.\n        const edgeObj = edgeArgsToObj(this._isDirected, vStr, wStr, nameStr);\n\n        vStr = edgeObj.v;\n        wStr = edgeObj.w;\n\n        Object.freeze(edgeObj);\n        this._edgeObjs[e] = edgeObj;\n        incrementOrInitEntry(this._preds[wStr]!, vStr);\n        incrementOrInitEntry(this._sucs[vStr]!, wStr);\n        this._in[wStr]![e] = edgeObj;\n        this._out[vStr]![e] = edgeObj;\n        this._edgeCount++;\n        return this;\n    }\n\n    /**\n     * Gets the label for the specified edge.\n     * Complexity: O(1).\n     *\n     * @param v - edge source node.\n     * @param w - edge sink node.\n     * @param name - name of the edge (actual for multigraph).\n     * @returns value associated with specified edge.\n     */\n    edge(v: string, w: string, name?: string): EdgeLabel;\n\n    /**\n     * Gets the label for the specified edge.\n     * Complexity: O(1).\n     *\n     * @param edge - edge descriptor.\n     * @returns value associated with specified edge.\n     */\n    edge(edge: Edge): EdgeLabel;\n\n    edge(v: string | Edge, w?: string, name?: string): EdgeLabel {\n        // TODO: This should return undefined if the edge doesn't exist, but that would be a breaking change.\n        const e = (arguments.length === 1\n            ? edgeObjToId(this._isDirected, v as Edge)\n            : edgeArgsToId(this._isDirected, v as string, w!, name));\n        return this._edgeLabels[e]!;\n    }\n\n    /**\n     * Gets the label for the specified edge and converts it to an object.\n     * Complexity: O(1).\n     *\n     * @param v - edge source node.\n     * @param w - edge sink node.\n     * @param name - name of the edge (actual for multigraph).\n     * @returns value associated with specified edge.\n     */\n    edgeAsObj(v: string, w: string, name?: string): { label: EdgeLabel };\n\n    /**\n     * Gets the label for the specified edge and converts it to an object.\n     * Complexity: O(1).\n     *\n     * @param edge - edge descriptor.\n     * @returns value associated with specified edge.\n     */\n    edgeAsObj(edge: Edge): { label: EdgeLabel };\n\n    edgeAsObj(v: string | Edge, w?: string, name?: string): { label: EdgeLabel } {\n        const edgeLabel = arguments.length === 1\n            ? this.edge(v as Edge)\n            : this.edge(v as string, w!, name);\n\n        if (typeof edgeLabel !== \"object\" || edgeLabel === null) {\n            return {label: edgeLabel as EdgeLabel};\n        }\n\n        return edgeLabel as unknown as { label: EdgeLabel };\n    }\n\n    /**\n     * Detects whether the graph contains specified edge or not. No subgraphs are considered.\n     * Complexity: O(1).\n     *\n     * @param v - edge source node.\n     * @param w - edge sink node.\n     * @param name - name of the edge (actual for multigraph).\n     * @returns whether the graph contains the specified edge or not.\n     */\n    hasEdge(v: string, w: string, name?: string): boolean;\n\n    /**\n     * Detects whether the graph contains specified edge or not. No subgraphs are considered.\n     * Complexity: O(1).\n     *\n     * @param edge - edge descriptor.\n     * @returns whether the graph contains the specified edge or not.\n     */\n    hasEdge(edge: Edge): boolean;\n\n    hasEdge(v: string | Edge, w?: string, name?: string): boolean {\n        const e = (arguments.length === 1\n            ? edgeObjToId(this._isDirected, v as Edge)\n            : edgeArgsToId(this._isDirected, v as string, w!, name));\n        return e in this._edgeLabels;\n    }\n\n    /**\n     * Removes the specified edge from the graph. No subgraphs are considered.\n     * Complexity: O(1).\n     *\n     * @param v - edge source node.\n     * @param w - edge sink node.\n     * @param name - name of the edge (actual for multigraph).\n     * @returns the graph, allowing this to be chained with other functions.\n     */\n    removeEdge(v: string, w: string, name?: string): this;\n\n    /**\n     * Removes the specified edge from the graph. No subgraphs are considered.\n     * Complexity: O(1).\n     *\n     * @param edge - edge descriptor.\n     * @returns the graph, allowing this to be chained with other functions.\n     */\n    removeEdge(edge: Edge): this;\n\n    removeEdge(v: string | Edge, w?: string, name?: string): this {\n        const e = (arguments.length === 1\n            ? edgeObjToId(this._isDirected, v as Edge)\n            : edgeArgsToId(this._isDirected, v as string, w!, name));\n        const edge = this._edgeObjs[e];\n        if (edge) {\n            const vStr = edge.v;\n            const wStr = edge.w;\n            delete this._edgeLabels[e];\n            delete this._edgeObjs[e];\n            decrementOrRemoveEntry(this._preds[wStr]!, vStr);\n            decrementOrRemoveEntry(this._sucs[vStr]!, wStr);\n            delete this._in[wStr]![e];\n            delete this._out[vStr]![e];\n            this._edgeCount--;\n        }\n        return this;\n    }\n\n    /**\n     * Return all edges that point to the node v. Optionally filters those edges down to just those\n     * coming from node u. Behavior is void for undirected graphs - use nodeEdges instead.\n     * Complexity: O(|E|).\n     *\n     * @param v - edge sink node.\n     * @param w - edge source node.\n     * @returns edges descriptors list if v is in the graph, or void otherwise.\n     */\n    inEdges(v: string, w?: string): Edge[] | undefined {\n        if (this.isDirected()) {\n            return this.filterEdges(this._in[v], v, w);\n        }\n        return this.nodeEdges(v, w);\n    }\n\n    /**\n     * Return all edges that are pointed at by node v. Optionally filters those edges down to just\n     * those point to w. Behavior is void for undirected graphs - use nodeEdges instead.\n     * Complexity: O(|E|).\n     *\n     * @param v - edge source node.\n     * @param w - edge sink node.\n     * @returns edges descriptors list if v is in the graph, or void otherwise.\n     */\n    outEdges(v: string, w?: string): Edge[] | undefined {\n        if (this.isDirected()) {\n            return this.filterEdges(this._out[v], v, w);\n        }\n        return this.nodeEdges(v, w);\n    }\n\n    /**\n     * Returns all edges to or from node v regardless of direction. Optionally filters those edges\n     * down to just those between nodes v and w regardless of direction.\n     * Complexity: O(|E|).\n     *\n     * @param v - edge adjacent node.\n     * @param w - edge adjacent node.\n     * @returns edges descriptors list if v is in the graph, or void otherwise.\n     */\n    nodeEdges(v: string, w?: string): Edge[] | undefined {\n        if (v in this._nodes) {\n            return this.filterEdges({...this._in[v]!, ...this._out[v]!}, v, w);\n        }\n        return undefined;\n    }\n\n    // Defaults to be set when creating a new node\n    private _defaultNodeLabelFn: NodeLabelFactory<NodeLabel> = () => undefined as NodeLabel;\n\n    // Defaults to be set when creating a new edge\n    private _defaultEdgeLabelFn: EdgeLabelFactory<EdgeLabel> = () => undefined as EdgeLabel;\n\n    private _removeFromParentsChildList(v: string): void {\n        delete this._children![this._parent![v]!]![v];\n    }\n\n    private filterEdges(setV: Record<string, Edge> | undefined, localEdge: string, remoteEdge?: string): Edge[] | undefined {\n        if (!setV) {\n            return;\n        }\n        const edges = Object.values(setV);\n        if (!remoteEdge) {\n            return edges;\n        }\n        return edges.filter((edge) => {\n            return edge.v === localEdge && edge.w === remoteEdge\n                || edge.v === remoteEdge && edge.w === localEdge;\n        });\n    }\n}\n\n\nfunction incrementOrInitEntry(map: Record<string, number>, k: string): void {\n    if (map[k]) {\n        map[k]++;\n    } else {\n        map[k] = 1;\n    }\n}\n\nfunction decrementOrRemoveEntry(map: Record<string, number>, k: string): void {\n    if (map[k] !== undefined && !--map[k]) {\n        delete map[k];\n    }\n}\n\nfunction edgeArgsToId(isDirected: boolean, v_: string, w_: string, name?: string): string {\n    let v = \"\" + v_;\n    let w = \"\" + w_;\n    if (!isDirected && v > w) {\n        const tmp = v;\n        v = w;\n        w = tmp;\n    }\n    return v + EDGE_KEY_DELIM + w + EDGE_KEY_DELIM +\n        (name === undefined ? DEFAULT_EDGE_NAME : name);\n}\n\nfunction edgeArgsToObj(isDirected: boolean, v_: string, w_: string, name?: string): Edge {\n    let v = \"\" + v_;\n    let w = \"\" + w_;\n    if (!isDirected && v > w) {\n        const tmp = v;\n        v = w;\n        w = tmp;\n    }\n    const edgeObj: Edge = {v: v, w: w};\n    if (name) {\n        edgeObj.name = name;\n    }\n    return edgeObj;\n}\n\nfunction edgeObjToId(isDirected: boolean, edgeObj: Edge): string {\n    return edgeArgsToId(isDirected, edgeObj.v, edgeObj.w, edgeObj.name);\n}\n", "export const version = '4.0.5';\n", "import {Graph} from './graph';\nimport type {GraphOptions, Label} from './types';\n\ninterface JsonGraph {\n    options: GraphOptions;\n    nodes: JsonNode[];\n    edges: JsonEdge[];\n    value?: unknown;\n}\n\ninterface JsonNode {\n    v: string;\n    value?: unknown;\n    parent?: string;\n}\n\ninterface JsonEdge {\n    v: string;\n    w: string;\n    name?: string;\n    value?: unknown;\n}\n\n/**\n * Creates a JSON representation of the graph that can be serialized to a string with\n * JSON.stringify. The graph can later be restored using json.read.\n *\n * @param graph - target to create JSON representation of.\n * @returns JSON serializable graph representation\n */\nexport function write(graph: Graph): JsonGraph {\n    const json: JsonGraph = {\n        options: {\n            directed: graph.isDirected(),\n            multigraph: graph.isMultigraph(),\n            compound: graph.isCompound()\n        },\n        nodes: writeNodes(graph),\n        edges: writeEdges(graph)\n    };\n\n    const graphLabel = graph.graph();\n    if (graphLabel !== undefined) {\n        json.value = structuredClone(graphLabel);\n    }\n\n    return json;\n}\n\nfunction writeNodes(g: Graph): JsonNode[] {\n    return g.nodes().map(v => {\n        const nodeValue = g.node(v);\n        const parent = g.parent(v);\n        const node: JsonNode = {v};\n\n        if (nodeValue !== undefined) {\n            node.value = nodeValue;\n        }\n        if (parent !== undefined) {\n            node.parent = parent;\n        }\n\n        return node;\n    });\n}\n\nfunction writeEdges(g: Graph): JsonEdge[] {\n    return g.edges().map(e => {\n        const edgeValue = g.edge(e);\n        const edge: JsonEdge = {v: e.v, w: e.w};\n\n        if (e.name !== undefined) {\n            edge.name = e.name;\n        }\n        if (edgeValue !== undefined) {\n            edge.value = edgeValue;\n        }\n\n        return edge;\n    });\n}\n\n/**\n * Takes JSON as input and returns the graph representation.\n *\n * @param json - JSON serializable graph representation\n * @returns graph constructed according to specified representation\n *\n * @example\n * var g2 = graphlib.json.read(JSON.parse(str));\n * g2.nodes();\n * // ['a', 'b']\n * g2.edges()\n * // [ { v: 'a', w: 'b' } ]\n */\nexport function read<GraphLabel = Label, NodeLabel = Label, EdgeLabel = Label>(\n    json: JsonGraph\n): Graph<GraphLabel, NodeLabel, EdgeLabel> {\n    const g = new Graph<GraphLabel, NodeLabel, EdgeLabel>(json.options);\n\n    if (json.value !== undefined) {\n        g.setGraph(json.value as GraphLabel);\n    }\n\n    json.nodes.forEach(entry => {\n        g.setNode(entry.v, entry.value as NodeLabel);\n        if (entry.parent) {\n            g.setParent(entry.v, entry.parent);\n        }\n    });\n\n    json.edges.forEach(entry => {\n        g.setEdge({v: entry.v, w: entry.w, name: entry.name}, entry.value as EdgeLabel);\n    });\n\n    return g;\n}\n", "export {bellmanFord} from './bellman-ford';\nexport {components} from './components';\nexport {dijkstra} from './dijkstra';\nexport {dijkstraAll} from './dijkstra-all';\nexport {findCycles} from './find-cycles';\nexport {floydWarshall} from './floyd-warshall';\nexport {isAcyclic} from './is-acyclic';\nexport {postorder} from './postorder';\nexport {preorder} from './preorder';\nexport {prim} from './prim';\nexport {shortestPaths} from './shortest-paths';\nexport {tarjan} from './tarjan';\nexport {topsort, CycleException} from './topsort';\n", "import {Graph} from '../graph';\nimport type {Edge, EdgeFunction, Path, WeightFunction} from '../types';\n\nconst DEFAULT_WEIGHT_FUNC: WeightFunction = () => 1;\n\nexport function bellmanFord(\n    g: Graph,\n    source: string,\n    weightFn?: WeightFunction,\n    edgeFn?: EdgeFunction\n): Record<string, Path> {\n    return runBellmanFord(\n        g,\n        String(source),\n        weightFn || DEFAULT_WEIGHT_FUNC,\n        edgeFn || function (v) {\n            return g.outEdges(v) ?? [];\n        }\n    );\n}\n\nfunction runBellmanFord(\n    g: Graph,\n    source: string,\n    weightFn: WeightFunction,\n    edgeFn: EdgeFunction\n): Record<string, Path> {\n    const results: Record<string, Path> = {};\n    let didADistanceUpgrade: boolean;\n    let iterations = 0;\n    const nodes = g.nodes();\n\n    const relaxEdge = function (edge: Edge): void {\n        const uEntry = results[edge.v];\n        const wEntry = results[edge.w];\n        if (!uEntry || !wEntry) return;\n        const edgeWeight = weightFn(edge);\n        if (uEntry.distance + edgeWeight < wEntry.distance) {\n            results[edge.w] = {\n                distance: uEntry.distance + edgeWeight,\n                predecessor: edge.v\n            };\n            didADistanceUpgrade = true;\n        }\n    };\n\n    const relaxAllEdges = function (): void {\n        nodes.forEach(function (vertex) {\n            edgeFn(vertex).forEach(function (edge) {\n                // If the vertex on which the edgeFun in called is\n                // the edge.w, then we treat the edge as if it was reversed\n                const inVertex = edge.v === vertex ? edge.v : edge.w;\n                const outVertex = inVertex === edge.v ? edge.w : edge.v;\n                relaxEdge({v: inVertex, w: outVertex});\n            });\n        });\n    };\n\n    // Initialization\n    nodes.forEach(function (v) {\n        const distance = v === source ? 0 : Number.POSITIVE_INFINITY;\n        results[v] = {distance: distance, predecessor: ''};\n    });\n\n    const numberOfNodes = nodes.length;\n\n    // Relax all edges in |V|-1 iterations\n    for (let i = 1; i < numberOfNodes; i++) {\n        didADistanceUpgrade = false;\n        iterations++;\n        relaxAllEdges();\n        if (!didADistanceUpgrade) {\n            // \u0399f no update was made in an iteration, Bellman-Ford has finished\n            break;\n        }\n    }\n\n    // Detect if the graph contains a negative weight cycle\n    if (iterations === numberOfNodes - 1) {\n        didADistanceUpgrade = false;\n        relaxAllEdges();\n        if (didADistanceUpgrade) {\n            throw new Error(\"The graph contains a negative weight cycle\");\n        }\n    }\n\n    return results;\n}\n", "import {Graph} from '../graph';\n\n/**\n * Finds all connected components in a graph and returns an array of these components.\n * Each component is itself an array that contains the ids of nodes in the component.\n * Complexity: O(|V|).\n *\n * @param graph - graph to find components in.\n * @returns array of nodes list representing components\n */\nexport function components(graph: Graph): string[][] {\n    const visited: Record<string, boolean> = {};\n    const cmpts: string[][] = [];\n    let cmpt: string[];\n\n    function dfs(v: string): void {\n        if (v in visited) return;\n        visited[v] = true;\n        cmpt.push(v);\n        graph.successors(v)?.forEach(dfs);\n        graph.predecessors(v)?.forEach(dfs);\n    }\n\n    graph.nodes().forEach(function (v) {\n        cmpt = [];\n        dfs(v);\n        if (cmpt.length) {\n            cmpts.push(cmpt);\n        }\n    });\n\n    return cmpts;\n}\n", "/**\n * A min-priority queue data structure. This algorithm is derived from Cormen,\n * et al., \"Introduction to Algorithms\". The basic idea of a min-priority\n * queue is that you can efficiently (in O(1) time) get the smallest key in\n * the queue. Adding and removing elements takes O(log n) time. A key can\n * have its priority decreased in O(log n) time.\n */\n\ninterface PriorityQueueEntry {\n    key: string;\n    priority: number;\n}\n\nexport class PriorityQueue {\n    private _arr: PriorityQueueEntry[] = [];\n    private _keyIndices: Record<string, number> = {};\n\n    /**\n     * Returns the number of elements in the queue. Takes `O(1)` time.\n     */\n    size(): number {\n        return this._arr.length;\n    }\n\n    /**\n     * Returns the keys that are in the queue. Takes `O(n)` time.\n     */\n    keys(): string[] {\n        return this._arr.map(x => x.key);\n    }\n\n    /**\n     * Returns `true` if **key** is in the queue and `false` if not.\n     */\n    has(key: string): boolean {\n        return key in this._keyIndices;\n    }\n\n    /**\n     * Returns the priority for **key**. If **key** is not present in the queue\n     * then this function returns `undefined`. Takes `O(1)` time.\n     */\n    priority(key: string): number | undefined {\n        const index = this._keyIndices[key];\n        if (index !== undefined) {\n            return this._arr[index]!.priority;\n        }\n        return undefined;\n    }\n\n    /**\n     * Returns the key for the minimum element in this queue. If the queue is\n     * empty this function throws an Error. Takes `O(1)` time.\n     */\n    min(): string {\n        if (this.size() === 0) {\n            throw new Error(\"Queue underflow\");\n        }\n        return this._arr[0]!.key;\n    }\n\n    /**\n     * Inserts a new key into the priority queue. If the key already exists in\n     * the queue this function returns `false`; otherwise it will return `true`.\n     * Takes `O(n)` time.\n     */\n    add(key: string, priority: number): boolean {\n        const keyIndices = this._keyIndices;\n        const keyStr = String(key);\n\n        if (!(keyStr in keyIndices)) {\n            const arr = this._arr;\n            const index = arr.length;\n            keyIndices[keyStr] = index;\n            arr.push({key: keyStr, priority});\n            this._decrease(index);\n            return true;\n        }\n        return false;\n    }\n\n    /**\n     * Removes and returns the smallest key in the queue. Takes `O(log n)` time.\n     */\n    removeMin(): string {\n        if (this.size() === 0) {\n            throw new Error(\"Queue underflow\");\n        }\n        this._swap(0, this._arr.length - 1);\n        const min = this._arr.pop()!;\n        delete this._keyIndices[min.key];\n        this._heapify(0);\n        return min.key;\n    }\n\n    /**\n     * Decreases the priority for **key** to **priority**. If the new priority is\n     * greater than the previous priority, this function will throw an Error.\n     */\n    decrease(key: string, priority: number): void {\n        const index = this._keyIndices[key];\n        if (index === undefined) {\n            throw new Error(`Key not found: ${key}`);\n        }\n\n        const currentPriority = this._arr[index]!.priority;\n        if (priority > currentPriority) {\n            throw new Error(\n                `New priority is greater than current priority. Key: ${key} Old: ${currentPriority} New: ${priority}`\n            );\n        }\n        this._arr[index]!.priority = priority;\n        this._decrease(index);\n    }\n\n    private _heapify(i: number): void {\n        const arr = this._arr;\n        const l = 2 * i;\n        const r = l + 1;\n        let largest = i;\n\n        if (l < arr.length) {\n            largest = arr[l]!.priority < arr[largest]!.priority ? l : largest;\n            if (r < arr.length) {\n                largest = arr[r]!.priority < arr[largest]!.priority ? r : largest;\n            }\n            if (largest !== i) {\n                this._swap(i, largest);\n                this._heapify(largest);\n            }\n        }\n    }\n\n    private _decrease(index: number): void {\n        const arr = this._arr;\n        const priority = arr[index]!.priority;\n        let parent: number;\n\n        while (index !== 0) {\n            parent = index >> 1;\n            if (arr[parent]!.priority < priority) {\n                break;\n            }\n            this._swap(index, parent);\n            index = parent;\n        }\n    }\n\n    private _swap(i: number, j: number): void {\n        const arr = this._arr;\n        const keyIndices = this._keyIndices;\n        const origArrI = arr[i]!;\n        const origArrJ = arr[j]!;\n\n        arr[i] = origArrJ;\n        arr[j] = origArrI;\n        keyIndices[origArrJ.key] = i;\n        keyIndices[origArrI.key] = j;\n    }\n}\n", "import {Graph} from '../graph';\nimport {PriorityQueue} from '../data/priority-queue';\nimport type {Edge, EdgeFunction, Path, WeightFunction} from '../types';\n\nconst DEFAULT_WEIGHT_FUNC: WeightFunction = () => 1;\n\n/**\n * This function is an implementation of Dijkstra's algorithm which finds the shortest\n * path from source to all other nodes in graph. This function returns a map of\n * v -> { distance, predecessor }. The distance property holds the sum of the weights\n * from source to v along the shortest path or Number.POSITIVE_INFINITY if there is no path\n * from source. The predecessor property can be used to walk the individual elements of the\n * path from source to v in reverse order.\n * Complexity: O((|E| + |V|) * log |V|).\n *\n * @param graph - graph where to search paths.\n * @param source - node to start paths from.\n * @param weightFn - function which takes edge e and returns the weight of it. If no weightFn\n * is supplied then each edge is assumed to have a weight of 1. This function throws an\n * Error if any of the traversed edges have a negative edge weight.\n * @param edgeFn - function which takes a node v and returns the ids of all edges incident to it\n * for the purposes of shortest path traversal. By default this function uses the graph.outEdges.\n * @returns shortest paths map that starts from node source\n */\nexport function dijkstra(\n    graph: Graph,\n    source: string,\n    weightFn?: WeightFunction,\n    edgeFn?: EdgeFunction\n): Record<string, Path> {\n    const defaultEdgeFn: EdgeFunction = function (v) {\n        return graph.outEdges(v) ?? [];\n    };\n\n    return runDijkstra(graph, String(source),\n        weightFn || DEFAULT_WEIGHT_FUNC,\n        edgeFn || defaultEdgeFn);\n}\n\nfunction runDijkstra(\n    graph: Graph,\n    source: string,\n    weightFn: WeightFunction,\n    edgeFn: EdgeFunction\n): Record<string, Path> {\n    const results: Record<string, Path> = {};\n    const pq = new PriorityQueue();\n    let v: string, vEntry: Path;\n\n    const updateNeighbors = function (edge: Edge): void {\n        const w = edge.v !== v ? edge.v : edge.w;\n        const wEntry = results[w];\n        if (!wEntry) return;\n        const weight = weightFn(edge);\n        const distance = vEntry.distance + weight;\n\n        if (weight < 0) {\n            throw new Error(\"dijkstra does not allow negative edge weights. \" +\n                \"Bad edge: \" + edge + \" Weight: \" + weight);\n        }\n\n        if (distance < wEntry.distance) {\n            wEntry.distance = distance;\n            wEntry.predecessor = v;\n            pq.decrease(w, distance);\n        }\n    };\n\n    graph.nodes().forEach(function (v) {\n        const distance = v === source ? 0 : Number.POSITIVE_INFINITY;\n        results[v] = {distance: distance, predecessor: ''};\n        pq.add(v, distance);\n    });\n\n    while (pq.size() > 0) {\n        v = pq.removeMin();\n        const entry = results[v];\n        if (!entry || entry.distance === Number.POSITIVE_INFINITY) {\n            break;\n        }\n        vEntry = entry;\n\n        edgeFn(v).forEach(updateNeighbors);\n    }\n\n    return results;\n}\n", "import {Graph} from '../graph';\nimport type {EdgeFunction, Path, WeightFunction} from '../types';\nimport {dijkstra} from './dijkstra';\n\n/**\n * This function finds the shortest path from each node to every other reachable node in\n * the graph. It is similar to alg.dijkstra, but instead of returning a single-source\n * array, it returns a mapping of source -> alg.dijkstra(g, source, weightFn, edgeFn).\n * Complexity: O(|V| * (|E| + |V|) * log |V|).\n *\n * @param graph - graph where to search paths.\n * @param weightFn - function which takes edge e and returns the weight of it. If no weightFn\n * is supplied then each edge is assumed to have a weight of 1. This function throws an\n * Error if any of the traversed edges have a negative edge weight.\n * @param edgeFn - function which takes a node v and returns the ids of all edges incident to it\n * for the purposes of shortest path traversal. By default this function uses the graph.outEdges.\n * @returns shortest paths map.\n */\nexport function dijkstraAll(\n    graph: Graph,\n    weightFn?: WeightFunction,\n    edgeFn?: EdgeFunction\n): Record<string, Record<string, Path>> {\n    return graph.nodes().reduce(function (acc, v) {\n        acc[v] = dijkstra(graph, v, weightFn, edgeFn);\n        return acc;\n    }, {} as Record<string, Record<string, Path>>);\n}\n", "import {Graph} from '../graph';\n\ninterface VisitedEntry {\n    onStack: boolean;\n    lowlink: number;\n    index: number;\n}\n\n/**\n * This function is an implementation of Tarjan's algorithm which finds all strongly connected\n * components in the directed graph g. Each strongly connected component is composed of nodes that\n * can reach all other nodes in the component via directed edges. A strongly connected component\n * can consist of a single node if that node cannot both reach and be reached by any other\n * specific node in the graph. Components of more than one node are guaranteed to have at least\n * one cycle.\n * Complexity: O(|V| + |E|).\n *\n * @param graph - graph to find all strongly connected components of.\n * @returns an array of components. Each component is itself an array that contains\n * the ids of all nodes in the component.\n */\nexport function tarjan(graph: Graph): string[][] {\n    let index = 0;\n    const stack: string[] = [];\n    const visited: Record<string, VisitedEntry> = {}; // node id -> { onStack, lowlink, index }\n    const results: string[][] = [];\n\n    function dfs(v: string): void {\n        const entry = visited[v] = {\n            onStack: true,\n            lowlink: index,\n            index: index++\n        };\n        stack.push(v);\n\n        graph.successors(v)?.forEach(function (w) {\n            if (!(w in visited)) {\n                dfs(w);\n                const wEntry = visited[w];\n                if (wEntry) {\n                    entry.lowlink = Math.min(entry.lowlink, wEntry.lowlink);\n                }\n            } else {\n                const wEntry = visited[w];\n                if (wEntry?.onStack) {\n                    entry.lowlink = Math.min(entry.lowlink, wEntry.index);\n                }\n            }\n        });\n\n        if (entry.lowlink === entry.index) {\n            const cmpt: string[] = [];\n            let w: string;\n            do {\n                w = stack.pop()!;\n                const wEntry = visited[w];\n                if (wEntry) {\n                    wEntry.onStack = false;\n                }\n                cmpt.push(w);\n            } while (v !== w);\n            results.push(cmpt);\n        }\n    }\n\n    graph.nodes().forEach(function (v) {\n        if (!(v in visited)) {\n            dfs(v);\n        }\n    });\n\n    return results;\n}\n", "import {Graph} from '../graph';\nimport {tarjan} from './tarjan';\n\n/**\n * Given a Graph, graph, this function returns all nodes that are part of a cycle. As there\n * may be more than one cycle in a graph this function return an array of these cycles,\n * where each cycle is itself represented by an array of ids for each node involved in\n * that cycle. Method alg.isAcyclic is more efficient if you only need to determine whether a graph has a\n * cycle or not.\n * Complexity: O(|V| + |E|).\n *\n * @param graph - graph where to search cycles.\n * @returns cycles list.\n */\nexport function findCycles(graph: Graph): string[][] {\n    return tarjan(graph).filter(function (cmpt) {\n        const firstNode = cmpt[0];\n        if (!firstNode) return false;\n        return cmpt.length > 1\n            || (cmpt.length === 1 && (graph.outEdges(firstNode, firstNode) ?? []).length > 0);\n    });\n}\n", "import {Graph} from '../graph';\nimport type {EdgeFunction, Path, WeightFunction} from '../types';\n\nconst DEFAULT_WEIGHT_FUNC: WeightFunction = () => 1;\n\n/**\n * This function is an implementation of the Floyd-Warshall algorithm, which finds the\n * shortest path from each node to every other reachable node in the graph. It is similar\n * to alg.dijkstraAll, but it handles negative edge weights and is more efficient for some types\n * of graphs. This function returns a map of source -> { target -> { distance, predecessor }.\n * The distance property holds the sum of the weights from source to target along the shortest\n * path of Number.POSITIVE_INFINITY if there is no path from source. The predecessor property\n * can be used to walk the individual elements of the path from source to target in reverse\n * order.\n * Complexity: O(|V|^3).\n *\n * @param graph - graph where to search paths.\n * @param weightFn - function which takes edge e and returns the weight of it. If no weightFn\n * is supplied then each edge is assumed to have a weight of 1. This function throws an\n * Error if any of the traversed edges have a negative edge weight.\n * @param edgeFn - function which takes a node v and returns the ids of all edges incident to it\n * for the purposes of shortest path traversal. By default this function uses the graph.outEdges.\n * @returns shortest paths map.\n */\nexport function floydWarshall(\n    graph: Graph,\n    weightFn?: WeightFunction,\n    edgeFn?: EdgeFunction\n): Record<string, Record<string, Path>> {\n    return runFloydWarshall(graph,\n        weightFn || DEFAULT_WEIGHT_FUNC,\n        edgeFn || function (v) {\n            return graph.outEdges(v) ?? [];\n        });\n}\n\nfunction runFloydWarshall(\n    graph: Graph,\n    weightFn: WeightFunction,\n    edgeFn: EdgeFunction\n): Record<string, Record<string, Path>> {\n    const results: Record<string, Record<string, Path>> = {};\n    const nodes = graph.nodes();\n\n    nodes.forEach(function (v) {\n        const rowV: Record<string, Path> = {};\n        results[v] = rowV;\n        rowV[v] = {distance: 0, predecessor: ''};\n        nodes.forEach(function (w) {\n            if (v !== w) {\n                rowV[w] = {distance: Number.POSITIVE_INFINITY, predecessor: ''};\n            }\n        });\n        edgeFn(v).forEach(function (edge) {\n            const w = edge.v === v ? edge.w : edge.v;\n            const d = weightFn(edge);\n            rowV[w] = {distance: d, predecessor: v};\n        });\n    });\n\n    nodes.forEach(function (k) {\n        const rowK = results[k];\n        if (!rowK) return;\n        nodes.forEach(function (i) {\n            const rowI = results[i];\n            if (!rowI) return;\n            nodes.forEach(function (j) {\n                const ik = rowI[k];\n                const kj = rowK[j];\n                const ij = rowI[j];\n                if (ik && kj && ij) {\n                    const altDistance = ik.distance + kj.distance;\n                    if (altDistance < ij.distance) {\n                        ij.distance = altDistance;\n                        ij.predecessor = kj.predecessor;\n                    }\n                }\n            });\n        });\n    });\n\n    return results;\n}\n", "import {Graph} from '../graph';\n\nexport class CycleException extends Error {\n    constructor(message?: string) {\n        super(message);\n        this.name = \"CycleException\";\n    }\n}\n\n/**\n * Given a graph this function applies topological sorting to it.\n * If the graph has a cycle it is impossible to generate such a list and CycleException is thrown.\n * Complexity: O(|V| + |E|).\n *\n * @param graph - graph to apply topological sorting to.\n * @returns an array of nodes such that for each edge u -> v, u appears before v in the array.\n */\nexport function topsort(graph: Graph): string[] {\n    const visited: Record<string, boolean> = {};\n    const stack: Record<string, boolean> = {};\n    const results: string[] = [];\n\n    function visit(node: string): void {\n        if (node in stack) {\n            throw new CycleException();\n        }\n\n        if (!(node in visited)) {\n            stack[node] = true;\n            visited[node] = true;\n            graph.predecessors(node)?.forEach(visit);\n            delete stack[node];\n            results.push(node);\n        }\n    }\n\n    graph.sinks().forEach(visit);\n\n    if (Object.keys(visited).length !== graph.nodeCount()) {\n        throw new CycleException();\n    }\n\n    return results;\n}\n", "import {Graph} from '../graph';\nimport {CycleException, topsort} from './topsort';\n\n/**\n * Given a Graph, graph, this function returns true if the graph has no cycles and returns false if it\n * does. This algorithm returns as soon as it detects the first cycle. You can use alg.findCycles\n * to get the actual list of cycles in the graph.\n *\n * @param graph - graph to detect whether it acyclic or not.\n * @returns whether graph contain cycles or not.\n */\nexport function isAcyclic(graph: Graph): boolean {\n    try {\n        topsort(graph);\n    } catch (e) {\n        if (e instanceof CycleException) {\n            return false;\n        }\n        throw e;\n    }\n    return true;\n}\n", "import {Graph} from '../graph';\n\n/*\n * A helper that preforms a pre- or post-order traversal on the input graph\n * and processes the nodes in the order they are visited. If the graph is\n * undirected then this algorithm will navigate using neighbors. If the graph\n * is directed then this algorithm will navigate using successors.\n *\n * Order must be one of \"pre\" or \"post\".\n */\nexport function reduce<T>(\n    g: Graph,\n    vs: string | string[],\n    order: \"pre\" | \"post\",\n    fn: (acc: T, v: string) => T,\n    acc: T\n): T {\n    if (!Array.isArray(vs)) {\n        vs = [vs];\n    }\n\n    const navigation = ((v: string) => (g.isDirected() ? g.successors(v) : g.neighbors(v)) ?? []);\n\n    const visited: Record<string, boolean> = {};\n    vs.forEach(function (v) {\n        if (!g.hasNode(v)) {\n            throw new Error(\"Graph does not have node: \" + v);\n        }\n\n        acc = doReduce(g, v, order === \"post\", visited, navigation, fn, acc);\n    });\n    return acc;\n}\n\nfunction doReduce<T>(\n    g: Graph,\n    v: string,\n    postorder: boolean,\n    visited: Record<string, boolean>,\n    navigation: (v: string) => string[],\n    fn: (acc: T, v: string) => T,\n    acc: T\n): T {\n    if (!(v in visited)) {\n        visited[v] = true;\n\n        if (!postorder) {\n            acc = fn(acc, v);\n        }\n        navigation(v).forEach(function (w) {\n            acc = doReduce(g, w, postorder, visited, navigation, fn, acc);\n        });\n        if (postorder) {\n            acc = fn(acc, v);\n        }\n    }\n    return acc;\n}\n", "import {Graph} from '../graph';\nimport {reduce} from './reduce';\n\n/*\n * Pre- or post-order traversal on the input graph.\n * Returns an array of the nodes in the order they were visited.\n *\n * If the order is not \"post\", it will be treated as \"pre\".\n */\nexport function dfs(g: Graph, vs: string | string[], order: \"pre\" | \"post\"): string[] {\n    return reduce(g, vs, order, function (acc, v) {\n        acc.push(v);\n        return acc;\n    }, [] as string[]);\n}\n", "import {Graph} from '../graph';\nimport {dfs} from './dfs';\n\n/**\n * Performs post-order depth first traversal on the input graph. If the graph is\n * undirected then this algorithm will navigate using neighbors. If the graph\n * is directed then this algorithm will navigate using successors.\n *\n * @param graph - depth first traversal target.\n * @param vs - nodes list to traverse.\n * @returns the nodes in the order they were visited as a list of their names.\n */\nexport function postorder(graph: Graph, vs: string | string[]): string[] {\n    return dfs(graph, vs, \"post\");\n}\n", "import {Graph} from '../graph';\nimport {dfs} from './dfs';\n\n/**\n * Performs pre-order depth first traversal on the input graph. If the graph is\n * undirected then this algorithm will navigate using neighbors. If the graph\n * is directed then this algorithm will navigate using successors.\n *\n * @param graph - depth first traversal target.\n * @param vs - nodes list to traverse.\n * @returns the nodes in the order they were visited as a list of their names.\n */\nexport function preorder(graph: Graph, vs: string | string[]): string[] {\n    return dfs(graph, vs, \"pre\");\n}\n", "import {Graph} from '../graph';\nimport {PriorityQueue} from '../data/priority-queue';\nimport type {Edge, WeightFunction} from '../types';\n\n/**\n * Prim's algorithm takes a connected undirected graph and generates a minimum spanning tree. This\n * function returns the minimum spanning tree as an undirected graph. This algorithm is derived\n * from the description in \"Introduction to Algorithms\", Third Edition, Cormen, et al., Pg 634.\n * Complexity: O(|E| * log |V|);\n *\n * @param graph - graph to generate a minimum spanning tree of.\n * @param weightFn - function which takes edge e and returns the weight of it. It throws an Error if\n * the graph is not connected.\n * @returns minimum spanning tree of graph.\n */\nexport function prim(graph: Graph, weightFn: WeightFunction): Graph {\n    const result = new Graph();\n    const parents: Record<string, string> = {};\n    const pq = new PriorityQueue();\n    let v: string;\n\n    function updateNeighbors(edge: Edge): void {\n        const w = edge.v === v ? edge.w : edge.v;\n        const pri = pq.priority(w);\n        if (pri !== undefined) {\n            const edgeWeight = weightFn(edge);\n            if (edgeWeight < pri) {\n                parents[w] = v;\n                pq.decrease(w, edgeWeight);\n            }\n        }\n    }\n\n    if (graph.nodeCount() === 0) {\n        return result;\n    }\n\n    graph.nodes().forEach(function (v) {\n        pq.add(v, Number.POSITIVE_INFINITY);\n        result.setNode(v);\n    });\n\n    // Start from an arbitrary node\n    const firstNode = graph.nodes()[0];\n    if (firstNode !== undefined) {\n        pq.decrease(firstNode, 0);\n    }\n\n    let init = false;\n    while (pq.size() > 0) {\n        v = pq.removeMin();\n        if (v in parents) {\n            result.setEdge(v, parents[v]!);\n        } else if (init) {\n            throw new Error(\"Input graph is not connected: \" + graph);\n        } else {\n            init = true;\n        }\n\n        graph.nodeEdges(v)?.forEach(updateNeighbors);\n    }\n\n    return result;\n}\n", "import {dijkstra} from './dijkstra';\nimport {bellmanFord} from './bellman-ford';\nimport {Graph} from '../graph';\nimport type {EdgeFunction, Path, WeightFunction} from '../types';\n\nexport function shortestPaths(\n    g: Graph,\n    source: string,\n    weightFn?: WeightFunction,\n    edgeFn?: EdgeFunction\n): Record<string, Path> {\n    return runShortestPaths(\n        g,\n        source,\n        weightFn,\n        edgeFn ?? ((v: string) => {\n            return g.outEdges(v) ?? [];\n        })\n    );\n}\n\nfunction runShortestPaths(\n    g: Graph,\n    source: string,\n    weightFn: WeightFunction | undefined,\n    edgeFn: EdgeFunction\n): Record<string, Path> {\n    if (weightFn === undefined) {\n        return dijkstra(g, source, weightFn, edgeFn);\n    }\n\n    let negativeEdgeExists = false;\n    const nodes = g.nodes();\n\n    for (let i = 0; i < nodes.length; i++) {\n        const node = nodes[i];\n        if (node === undefined) continue;\n        const adjList = edgeFn(node);\n\n        for (let j = 0; j < adjList.length; j++) {\n            const edge = adjList[j];\n            if (!edge) continue;\n            const inVertex = edge.v === node ? edge.v : edge.w;\n            const outVertex = inVertex === edge.v ? edge.w : edge.v;\n\n            if (weightFn({v: inVertex, w: outVertex}) < 0) {\n                negativeEdgeExists = true;\n            }\n        }\n\n        if (negativeEdgeExists) {\n            return bellmanFord(g, source, weightFn, edgeFn);\n        }\n    }\n\n    return dijkstra(g, source, weightFn, edgeFn);\n}\n"],
  "mappings": "yaAAA,IAAAA,GAAA,GAAAC,EAAAD,GAAA,WAAAE,EAAA,QAAAC,EAAA,SAAAC,EAAA,YAAAC,IAAA,eAAAC,EAAAN,ICgBO,IAAMO,EAAN,KAAsE,CA4BzE,YAAYC,EAAqB,CA3BjC,KAAQ,YAAuB,GAC/B,KAAQ,cAAyB,GACjC,KAAQ,YAAuB,GAK/B,KAAQ,OAAoC,CAAC,EAE7C,KAAQ,IAA4C,CAAC,EAErD,KAAQ,OAAiD,CAAC,EAE1D,KAAQ,KAA6C,CAAC,EAEtD,KAAQ,MAAgD,CAAC,EAEzD,KAAQ,UAAkC,CAAC,EAE3C,KAAQ,YAAyC,CAAC,EAElD,KAAQ,WAAqB,EAE7B,KAAQ,WAAqB,EAwvB7B,KAAQ,oBAAmD,IAAG,GAG9D,KAAQ,oBAAmD,IAAG,GAtvBtDA,IACA,KAAK,YAAc,aAAcA,EAAOA,EAAK,SAAY,GACzD,KAAK,cAAgB,eAAgBA,EAAOA,EAAK,WAAc,GAC/D,KAAK,YAAc,aAAcA,EAAOA,EAAK,SAAY,IAGzD,KAAK,cAEL,KAAK,QAAU,CAAC,EAGhB,KAAK,UAAY,CAAC,EAClB,KAAK,UAAU,IAAU,EAAI,CAAC,EAEtC,CAOA,YAAsB,CAClB,OAAO,KAAK,WAChB,CAOA,cAAwB,CACpB,OAAO,KAAK,aAChB,CASA,YAAsB,CAClB,OAAO,KAAK,WAChB,CAQA,SAASC,EAAyB,CAC9B,YAAK,OAASA,EACP,IACX,CAOA,OAAoB,CAEhB,OAAO,KAAK,MAChB,CAUA,oBAAoBC,EAA0D,CAC1E,OAAI,OAAOA,GAAc,WACrB,KAAK,oBAAsB,IAAMA,EAEjC,KAAK,oBAAsBA,EAGxB,IACX,CAQA,WAAoB,CAChB,OAAO,KAAK,UAChB,CAYA,OAAkB,CACd,OAAO,OAAO,KAAK,KAAK,MAAM,CAClC,CAQA,SAAoB,CAChB,OAAO,KAAK,MAAM,EAAE,OAAOC,GAAK,OAAO,KAAK,KAAK,IAAIA,CAAC,CAAE,EAAE,SAAW,CAAC,CAC1E,CAQA,OAAkB,CACd,OAAO,KAAK,MAAM,EAAE,OAAOA,GAAK,OAAO,KAAK,KAAK,KAAKA,CAAC,CAAE,EAAE,SAAW,CAAC,CAC3E,CAUA,SAASC,EAAiBH,EAAyB,CAC/C,OAAAG,EAAM,QAASD,GAAM,CACbF,IAAU,OACV,KAAK,QAAQE,EAAGF,CAAK,EAErB,KAAK,QAAQE,CAAC,CAEtB,CAAC,EACM,IACX,CAYA,QAAQE,EAAcJ,EAAyB,CAC3C,OAAII,KAAQ,KAAK,QACT,UAAU,OAAS,IACnB,KAAK,OAAOA,CAAI,EAAIJ,GAEjB,OAGX,KAAK,OAAOI,CAAI,EAAI,UAAU,OAAS,EAAIJ,EAAS,KAAK,oBAAoBI,CAAI,EAC7E,KAAK,cACL,KAAK,QAASA,CAAI,EAAI,KACtB,KAAK,UAAWA,CAAI,EAAI,CAAC,EACzB,KAAK,UAAW,IAAU,EAAGA,CAAI,EAAI,IAEzC,KAAK,IAAIA,CAAI,EAAI,CAAC,EAClB,KAAK,OAAOA,CAAI,EAAI,CAAC,EACrB,KAAK,KAAKA,CAAI,EAAI,CAAC,EACnB,KAAK,MAAMA,CAAI,EAAI,CAAC,EACpB,EAAE,KAAK,WACA,KACX,CASA,KAAKA,EAAyB,CAE1B,OAAO,KAAK,OAAOA,CAAI,CAC3B,CAQA,QAAQA,EAAuB,CAC3B,OAAOA,KAAQ,KAAK,MACxB,CAWA,WAAWA,EAAoB,CAC3B,GAAIA,KAAQ,KAAK,OAAQ,CACrB,IAAMC,EAAcC,GAAc,KAAK,WAAW,KAAK,UAAUA,CAAC,CAAE,EACpE,OAAO,KAAK,OAAOF,CAAI,EACnB,KAAK,cACL,KAAK,4BAA4BA,CAAI,EACrC,OAAO,KAAK,QAASA,CAAI,EACzB,KAAK,SAASA,CAAI,EAAE,QAASG,GAAU,CACnC,KAAK,UAAUA,CAAK,CACxB,CAAC,EACD,OAAO,KAAK,UAAWH,CAAI,GAE/B,OAAO,KAAK,KAAK,IAAIA,CAAI,CAAE,EAAE,QAAQC,CAAU,EAC/C,OAAO,KAAK,IAAID,CAAI,EACpB,OAAO,KAAK,OAAOA,CAAI,EACvB,OAAO,KAAK,KAAK,KAAKA,CAAI,CAAE,EAAE,QAAQC,CAAU,EAChD,OAAO,KAAK,KAAKD,CAAI,EACrB,OAAO,KAAK,MAAMA,CAAI,EACtB,EAAE,KAAK,UACX,CACA,OAAO,IACX,CAYA,UAAUF,EAAWM,EAAuB,CACxC,GAAI,CAAC,KAAK,YACN,MAAM,IAAI,MAAM,2CAA2C,EAG/D,GAAIA,IAAW,OACXA,EAAS,SACN,CAEHA,GAAU,GACV,QAASC,EAA+BD,EAAQC,IAAa,OAAWA,EAAW,KAAK,OAAOA,CAAQ,EACnG,GAAIA,IAAaP,EACb,MAAM,IAAI,MAAM,WAAaM,EAAS,iBAAmBN,EACrD,uBAAuB,EAInC,KAAK,QAAQM,CAAM,CACvB,CAEA,YAAK,QAAQN,CAAC,EACd,KAAK,4BAA4BA,CAAC,EAClC,KAAK,QAASA,CAAC,EAAIM,EACnB,KAAK,UAAWA,CAAM,EAAGN,CAAC,EAAI,GACvB,IACX,CASA,OAAOA,EAA+B,CAClC,GAAI,KAAK,YAAa,CAClB,IAAMM,EAAS,KAAK,QAASN,CAAC,EAC9B,GAAIM,IAAW,KACX,OAAOA,CAEf,CAEJ,CASA,SAASN,EAAY,KAAsB,CACvC,GAAI,KAAK,YAAa,CAClB,IAAMQ,EAAW,KAAK,UAAWR,CAAC,EAClC,GAAIQ,EACA,OAAO,OAAO,KAAKA,CAAQ,CAEnC,KAAO,IAAIR,IAAM,KACb,OAAO,KAAK,MAAM,EACf,GAAI,KAAK,QAAQA,CAAC,EACrB,MAAO,CAAC,EAEZ,MAAO,CAAC,CACZ,CAUA,aAAaA,EAAiC,CAC1C,IAAMS,EAAS,KAAK,OAAOT,CAAC,EAC5B,GAAIS,EACA,OAAO,OAAO,KAAKA,CAAM,CAGjC,CAUA,WAAWT,EAAiC,CACxC,IAAMU,EAAQ,KAAK,MAAMV,CAAC,EAC1B,GAAIU,EACA,OAAO,OAAO,KAAKA,CAAK,CAGhC,CAUA,UAAUV,EAAiC,CACvC,IAAMW,EAAQ,KAAK,aAAaX,CAAC,EACjC,GAAIW,EAAO,CACP,IAAMC,EAAQ,IAAI,IAAID,CAAK,EACrBE,EAAO,KAAK,WAAWb,CAAC,EAC9B,GAAIa,EACA,QAAWC,KAAQD,EACfD,EAAM,IAAIE,CAAI,EAItB,OAAO,MAAM,KAAKF,EAAM,OAAO,CAAC,CACpC,CAEJ,CAEA,OAAOZ,EAAoB,CAzZ/B,IAAAe,EA0ZQ,IAAIC,EACJ,OAAI,KAAK,WAAW,EAChBA,EAAY,KAAK,WAAWhB,CAAC,EAE7BgB,EAAY,KAAK,UAAUhB,CAAC,IAExBe,EAAAC,GAAA,YAAAA,EAAW,SAAX,KAAAD,EAAqB,KAAO,CACxC,CAWA,YAAYE,EAAsC,CAC9C,IAAMC,EAAO,IAAK,KAAK,YAA+D,CAClF,SAAU,KAAK,YACf,WAAY,KAAK,cACjB,SAAU,KAAK,WACnB,CAAC,EAEDA,EAAK,SAAS,KAAK,MAAM,CAAE,EAE3B,OAAO,QAAQ,KAAK,MAAM,EAAE,QAAQ,CAAC,CAAClB,EAAGmB,CAAK,IAAM,CAC5CF,EAAOjB,CAAC,GACRkB,EAAK,QAAQlB,EAAGmB,CAAK,CAE7B,CAAC,EAED,OAAO,OAAO,KAAK,SAAS,EAAE,QAASf,GAAM,CACrCc,EAAK,QAAQd,EAAE,CAAC,GAAKc,EAAK,QAAQd,EAAE,CAAC,GACrCc,EAAK,QAAQd,EAAG,KAAK,KAAKA,CAAC,CAAC,CAEpC,CAAC,EAED,IAAMgB,EAA8C,CAAC,EAC/CC,EAAcrB,GAAkC,CAClD,IAAMM,EAAS,KAAK,OAAON,CAAC,EAC5B,MAAI,CAACM,GAAUY,EAAK,QAAQZ,CAAM,GAC9Bc,EAAQpB,CAAC,EAAIM,EACNA,GACAA,KAAUc,EACVA,EAAQd,CAAM,EAEde,EAAWf,CAAM,CAEhC,EAEA,OAAI,KAAK,aACLY,EAAK,MAAM,EAAE,QAAQlB,GAAKkB,EAAK,UAAUlB,EAAGqB,EAAWrB,CAAC,CAAC,CAAC,EAGvDkB,CACX,CAUA,oBAAoBnB,EAA0D,CAC1E,OAAI,OAAOA,GAAc,WACrB,KAAK,oBAAsB,IAAMA,EAEjC,KAAK,oBAAsBA,EAGxB,IACX,CAQA,WAAoB,CAChB,OAAO,KAAK,UAChB,CAQA,OAAgB,CACZ,OAAO,OAAO,OAAO,KAAK,SAAS,CACvC,CAcA,QAAQuB,EAAiBxB,EAAyB,CAC9C,OAAAwB,EAAM,OAAO,CAACtB,EAAGuB,KACTzB,IAAU,OACV,KAAK,QAAQE,EAAGuB,EAAGzB,CAAK,EAExB,KAAK,QAAQE,EAAGuB,CAAC,EAEdA,EACV,EACM,IACX,CA8BA,QAAQvB,EAAkBuB,EAAwBJ,EAAmBjB,EAAqB,CACtF,IAAIsB,EACAC,EACAC,EACAC,EACAC,EAAiB,GAEjB,OAAO5B,GAAM,UAAYA,IAAM,MAAQ,MAAOA,GAC9CwB,EAAOxB,EAAE,EACTyB,EAAOzB,EAAE,EACT0B,EAAU1B,EAAE,KACR,UAAU,SAAW,IACrB2B,EAAYJ,EACZK,EAAiB,MAGrBJ,EAAOxB,EACPyB,EAAOF,EACPG,EAAUxB,EACN,UAAU,OAAS,IACnByB,EAAYR,EACZS,EAAiB,KAIzBJ,EAAO,GAAKA,EACZC,EAAO,GAAKA,EACRC,IAAY,SACZA,EAAU,GAAKA,GAGnB,IAAMtB,EAAIyB,EAAa,KAAK,YAAaL,EAAMC,EAAMC,CAAO,EAC5D,GAAItB,KAAK,KAAK,YACV,OAAIwB,IACA,KAAK,YAAYxB,CAAC,EAAIuB,GAEnB,KAGX,GAAID,IAAY,QAAa,CAAC,KAAK,cAC/B,MAAM,IAAI,MAAM,mDAAmD,EAKvE,KAAK,QAAQF,CAAI,EACjB,KAAK,QAAQC,CAAI,EAEjB,KAAK,YAAYrB,CAAC,EAAIwB,EAAiBD,EAAa,KAAK,oBAAoBH,EAAMC,EAAMC,CAAO,EAGhG,IAAMI,EAAUC,EAAc,KAAK,YAAaP,EAAMC,EAAMC,CAAO,EAEnE,OAAAF,EAAOM,EAAQ,EACfL,EAAOK,EAAQ,EAEf,OAAO,OAAOA,CAAO,EACrB,KAAK,UAAU1B,CAAC,EAAI0B,EACpBE,EAAqB,KAAK,OAAOP,CAAI,EAAID,CAAI,EAC7CQ,EAAqB,KAAK,MAAMR,CAAI,EAAIC,CAAI,EAC5C,KAAK,IAAIA,CAAI,EAAGrB,CAAC,EAAI0B,EACrB,KAAK,KAAKN,CAAI,EAAGpB,CAAC,EAAI0B,EACtB,KAAK,aACE,IACX,CAsBA,KAAK9B,EAAkBuB,EAAYrB,EAA0B,CAEzD,IAAME,EAAK,UAAU,SAAW,EAC1B6B,EAAY,KAAK,YAAajC,CAAS,EACvC6B,EAAa,KAAK,YAAa7B,EAAauB,EAAIrB,CAAI,EAC1D,OAAO,KAAK,YAAYE,CAAC,CAC7B,CAsBA,UAAUJ,EAAkBuB,EAAYrB,EAAqC,CACzE,IAAMgC,EAAY,UAAU,SAAW,EACjC,KAAK,KAAKlC,CAAS,EACnB,KAAK,KAAKA,EAAauB,EAAIrB,CAAI,EAErC,OAAI,OAAOgC,GAAc,UAAYA,IAAc,KACxC,CAAC,MAAOA,CAAsB,EAGlCA,CACX,CAsBA,QAAQlC,EAAkBuB,EAAYrB,EAAwB,CAI1D,OAHW,UAAU,SAAW,EAC1B+B,EAAY,KAAK,YAAajC,CAAS,EACvC6B,EAAa,KAAK,YAAa7B,EAAauB,EAAIrB,CAAI,KAC9C,KAAK,WACrB,CAsBA,WAAWF,EAAkBuB,EAAYrB,EAAqB,CAC1D,IAAME,EAAK,UAAU,SAAW,EAC1B6B,EAAY,KAAK,YAAajC,CAAS,EACvC6B,EAAa,KAAK,YAAa7B,EAAauB,EAAIrB,CAAI,EACpDiC,EAAO,KAAK,UAAU/B,CAAC,EAC7B,GAAI+B,EAAM,CACN,IAAMX,EAAOW,EAAK,EACZV,EAAOU,EAAK,EAClB,OAAO,KAAK,YAAY/B,CAAC,EACzB,OAAO,KAAK,UAAUA,CAAC,EACvBgC,EAAuB,KAAK,OAAOX,CAAI,EAAID,CAAI,EAC/CY,EAAuB,KAAK,MAAMZ,CAAI,EAAIC,CAAI,EAC9C,OAAO,KAAK,IAAIA,CAAI,EAAGrB,CAAC,EACxB,OAAO,KAAK,KAAKoB,CAAI,EAAGpB,CAAC,EACzB,KAAK,YACT,CACA,OAAO,IACX,CAWA,QAAQJ,EAAWuB,EAAgC,CAC/C,OAAI,KAAK,WAAW,EACT,KAAK,YAAY,KAAK,IAAIvB,CAAC,EAAGA,EAAGuB,CAAC,EAEtC,KAAK,UAAUvB,EAAGuB,CAAC,CAC9B,CAWA,SAASvB,EAAWuB,EAAgC,CAChD,OAAI,KAAK,WAAW,EACT,KAAK,YAAY,KAAK,KAAKvB,CAAC,EAAGA,EAAGuB,CAAC,EAEvC,KAAK,UAAUvB,EAAGuB,CAAC,CAC9B,CAWA,UAAUvB,EAAWuB,EAAgC,CACjD,GAAIvB,KAAK,KAAK,OACV,OAAO,KAAK,YAAY,CAAC,GAAG,KAAK,IAAIA,CAAC,EAAI,GAAG,KAAK,KAAKA,CAAC,CAAE,EAAGA,EAAGuB,CAAC,CAGzE,CAQQ,4BAA4BvB,EAAiB,CACjD,OAAO,KAAK,UAAW,KAAK,QAASA,CAAC,CAAE,EAAGA,CAAC,CAChD,CAEQ,YAAYqC,EAAwCC,EAAmBC,EAAyC,CACpH,GAAI,CAACF,EACD,OAEJ,IAAMG,EAAQ,OAAO,OAAOH,CAAI,EAChC,OAAKE,EAGEC,EAAM,OAAQL,GACVA,EAAK,IAAMG,GAAaH,EAAK,IAAMI,GACnCJ,EAAK,IAAMI,GAAcJ,EAAK,IAAMG,CAC9C,EALUE,CAMf,CACJ,EAGA,SAASR,EAAqBS,EAA6BC,EAAiB,CACpED,EAAIC,CAAC,EACLD,EAAIC,CAAC,IAELD,EAAIC,CAAC,EAAI,CAEjB,CAEA,SAASN,EAAuBK,EAA6BC,EAAiB,CACtED,EAAIC,CAAC,IAAM,QAAa,CAAC,EAAED,EAAIC,CAAC,GAChC,OAAOD,EAAIC,CAAC,CAEpB,CAEA,SAASb,EAAac,EAAqBC,EAAYC,EAAY3C,EAAuB,CACtF,IAAIF,EAAI,GAAK4C,EACTrB,EAAI,GAAKsB,EACb,GAAI,CAACF,GAAc3C,EAAIuB,EAAG,CACtB,IAAMuB,EAAM9C,EACZA,EAAIuB,EACJA,EAAIuB,CACR,CACA,OAAO9C,EAAI,IAAiBuB,EAAI,KAC3BrB,IAAS,OAAY,KAAoBA,EAClD,CAEA,SAAS6B,EAAcY,EAAqBC,EAAYC,EAAY3C,EAAqB,CACrF,IAAIF,EAAI,GAAK4C,EACTrB,EAAI,GAAKsB,EACb,GAAI,CAACF,GAAc3C,EAAIuB,EAAG,CACtB,IAAMuB,EAAM9C,EACZA,EAAIuB,EACJA,EAAIuB,CACR,CACA,IAAMhB,EAAgB,CAAC,EAAG9B,EAAG,EAAGuB,CAAC,EACjC,OAAIrB,IACA4B,EAAQ,KAAO5B,GAEZ4B,CACX,CAEA,SAASG,EAAYU,EAAqBb,EAAuB,CAC7D,OAAOD,EAAac,EAAYb,EAAQ,EAAGA,EAAQ,EAAGA,EAAQ,IAAI,CACtE,CCp2BO,IAAMiB,EAAU,QCAvB,IAAAC,EAAA,GAAAC,EAAAD,EAAA,UAAAE,EAAA,UAAAC,IA8BO,SAASC,EAAMC,EAAyB,CAC3C,IAAMC,EAAkB,CACpB,QAAS,CACL,SAAUD,EAAM,WAAW,EAC3B,WAAYA,EAAM,aAAa,EAC/B,SAAUA,EAAM,WAAW,CAC/B,EACA,MAAOE,EAAWF,CAAK,EACvB,MAAOG,EAAWH,CAAK,CAC3B,EAEMI,EAAaJ,EAAM,MAAM,EAC/B,OAAII,IAAe,SACfH,EAAK,MAAQ,gBAAgBG,CAAU,GAGpCH,CACX,CAEA,SAASC,EAAWG,EAAsB,CACtC,OAAOA,EAAE,MAAM,EAAE,IAAIC,GAAK,CACtB,IAAMC,EAAYF,EAAE,KAAKC,CAAC,EACpBE,EAASH,EAAE,OAAOC,CAAC,EACnBG,EAAiB,CAAC,EAAAH,CAAC,EAEzB,OAAIC,IAAc,SACdE,EAAK,MAAQF,GAEbC,IAAW,SACXC,EAAK,OAASD,GAGXC,CACX,CAAC,CACL,CAEA,SAASN,EAAWE,EAAsB,CACtC,OAAOA,EAAE,MAAM,EAAE,IAAI,GAAK,CACtB,IAAMK,EAAYL,EAAE,KAAK,CAAC,EACpBM,EAAiB,CAAC,EAAG,EAAE,EAAG,EAAG,EAAE,CAAC,EAEtC,OAAI,EAAE,OAAS,SACXA,EAAK,KAAO,EAAE,MAEdD,IAAc,SACdC,EAAK,MAAQD,GAGVC,CACX,CAAC,CACL,CAeO,SAASC,EACZX,EACuC,CACvC,IAAMI,EAAI,IAAIQ,EAAwCZ,EAAK,OAAO,EAElE,OAAIA,EAAK,QAAU,QACfI,EAAE,SAASJ,EAAK,KAAmB,EAGvCA,EAAK,MAAM,QAAQa,GAAS,CACxBT,EAAE,QAAQS,EAAM,EAAGA,EAAM,KAAkB,EACvCA,EAAM,QACNT,EAAE,UAAUS,EAAM,EAAGA,EAAM,MAAM,CAEzC,CAAC,EAEDb,EAAK,MAAM,QAAQa,GAAS,CACxBT,EAAE,QAAQ,CAAC,EAAGS,EAAM,EAAG,EAAGA,EAAM,EAAG,KAAMA,EAAM,IAAI,EAAGA,EAAM,KAAkB,CAClF,CAAC,EAEMT,CACX,CCpHA,IAAAU,EAAA,GAAAC,EAAAD,EAAA,oBAAAE,EAAA,gBAAAC,EAAA,eAAAC,EAAA,aAAAC,EAAA,gBAAAC,EAAA,eAAAC,EAAA,kBAAAC,EAAA,cAAAC,EAAA,cAAAC,EAAA,aAAAC,EAAA,SAAAC,EAAA,kBAAAC,EAAA,WAAAC,EAAA,YAAAC,ICGA,IAAMC,EAAsC,IAAM,EAE3C,SAASC,EACZC,EACAC,EACAC,EACAC,EACoB,CACpB,OAAOC,GACHJ,EACA,OAAOC,CAAM,EACbC,GAAYJ,EACZK,GAAU,SAAUE,EAAG,CAf/B,IAAAC,EAgBY,OAAOA,EAAAN,EAAE,SAASK,CAAC,IAAZ,KAAAC,EAAiB,CAAC,CAC7B,CACJ,CACJ,CAEA,SAASF,GACLJ,EACAC,EACAC,EACAC,EACoB,CACpB,IAAMI,EAAgC,CAAC,EACnCC,EACAC,EAAa,EACXC,EAAQV,EAAE,MAAM,EAEhBW,EAAY,SAAUC,EAAkB,CAC1C,IAAMC,EAASN,EAAQK,EAAK,CAAC,EACvBE,EAASP,EAAQK,EAAK,CAAC,EAC7B,GAAI,CAACC,GAAU,CAACC,EAAQ,OACxB,IAAMC,EAAab,EAASU,CAAI,EAC5BC,EAAO,SAAWE,EAAaD,EAAO,WACtCP,EAAQK,EAAK,CAAC,EAAI,CACd,SAAUC,EAAO,SAAWE,EAC5B,YAAaH,EAAK,CACtB,EACAJ,EAAsB,GAE9B,EAEMQ,EAAgB,UAAkB,CACpCN,EAAM,QAAQ,SAAUO,EAAQ,CAC5Bd,EAAOc,CAAM,EAAE,QAAQ,SAAUL,EAAM,CAGnC,IAAMM,EAAWN,EAAK,IAAMK,EAASL,EAAK,EAAIA,EAAK,EAC7CO,EAAYD,IAAaN,EAAK,EAAIA,EAAK,EAAIA,EAAK,EACtDD,EAAU,CAAC,EAAGO,EAAU,EAAGC,CAAS,CAAC,CACzC,CAAC,CACL,CAAC,CACL,EAGAT,EAAM,QAAQ,SAAUL,EAAG,CACvB,IAAMe,EAAWf,IAAMJ,EAAS,EAAI,OAAO,kBAC3CM,EAAQF,CAAC,EAAI,CAAC,SAAUe,EAAU,YAAa,EAAE,CACrD,CAAC,EAED,IAAMC,EAAgBX,EAAM,OAG5B,QAASY,EAAI,EAAGA,EAAID,IAChBb,EAAsB,GACtBC,IACAO,EAAc,EACV,EAACR,GAJ0Bc,IAI/B,CAOJ,GAAIb,IAAeY,EAAgB,IAC/Bb,EAAsB,GACtBQ,EAAc,EACVR,GACA,MAAM,IAAI,MAAM,4CAA4C,EAIpE,OAAOD,CACX,CC7EO,SAASgB,EAAWC,EAA0B,CACjD,IAAMC,EAAmC,CAAC,EACpCC,EAAoB,CAAC,EACvBC,EAEJ,SAASC,EAAIC,EAAiB,CAflC,IAAAC,EAAAC,EAgBYF,KAAKJ,IACTA,EAAQI,CAAC,EAAI,GACbF,EAAK,KAAKE,CAAC,GACXC,EAAAN,EAAM,WAAWK,CAAC,IAAlB,MAAAC,EAAqB,QAAQF,IAC7BG,EAAAP,EAAM,aAAaK,CAAC,IAApB,MAAAE,EAAuB,QAAQH,GACnC,CAEA,OAAAJ,EAAM,MAAM,EAAE,QAAQ,SAAUK,EAAG,CAC/BF,EAAO,CAAC,EACRC,EAAIC,CAAC,EACDF,EAAK,QACLD,EAAM,KAAKC,CAAI,CAEvB,CAAC,EAEMD,CACX,CCnBO,IAAMM,EAAN,KAAoB,CAApB,cACH,KAAQ,KAA6B,CAAC,EACtC,KAAQ,YAAsC,CAAC,EAK/C,MAAe,CACX,OAAO,KAAK,KAAK,MACrB,CAKA,MAAiB,CACb,OAAO,KAAK,KAAK,IAAIC,GAAKA,EAAE,GAAG,CACnC,CAKA,IAAIC,EAAsB,CACtB,OAAOA,KAAO,KAAK,WACvB,CAMA,SAASA,EAAiC,CACtC,IAAMC,EAAQ,KAAK,YAAYD,CAAG,EAClC,GAAIC,IAAU,OACV,OAAO,KAAK,KAAKA,CAAK,EAAG,QAGjC,CAMA,KAAc,CACV,GAAI,KAAK,KAAK,IAAM,EAChB,MAAM,IAAI,MAAM,iBAAiB,EAErC,OAAO,KAAK,KAAK,CAAC,EAAG,GACzB,CAOA,IAAID,EAAaE,EAA2B,CACxC,IAAMC,EAAa,KAAK,YAClBC,EAAS,OAAOJ,CAAG,EAEzB,GAAI,EAAEI,KAAUD,GAAa,CACzB,IAAME,EAAM,KAAK,KACXJ,EAAQI,EAAI,OAClB,OAAAF,EAAWC,CAAM,EAAIH,EACrBI,EAAI,KAAK,CAAC,IAAKD,EAAQ,SAAAF,CAAQ,CAAC,EAChC,KAAK,UAAUD,CAAK,EACb,EACX,CACA,MAAO,EACX,CAKA,WAAoB,CAChB,GAAI,KAAK,KAAK,IAAM,EAChB,MAAM,IAAI,MAAM,iBAAiB,EAErC,KAAK,MAAM,EAAG,KAAK,KAAK,OAAS,CAAC,EAClC,IAAMK,EAAM,KAAK,KAAK,IAAI,EAC1B,cAAO,KAAK,YAAYA,EAAI,GAAG,EAC/B,KAAK,SAAS,CAAC,EACRA,EAAI,GACf,CAMA,SAASN,EAAaE,EAAwB,CAC1C,IAAMD,EAAQ,KAAK,YAAYD,CAAG,EAClC,GAAIC,IAAU,OACV,MAAM,IAAI,MAAM,kBAAkBD,CAAG,EAAE,EAG3C,IAAMO,EAAkB,KAAK,KAAKN,CAAK,EAAG,SAC1C,GAAIC,EAAWK,EACX,MAAM,IAAI,MACN,uDAAuDP,CAAG,SAASO,CAAe,SAASL,CAAQ,EACvG,EAEJ,KAAK,KAAKD,CAAK,EAAG,SAAWC,EAC7B,KAAK,UAAUD,CAAK,CACxB,CAEQ,SAASO,EAAiB,CAC9B,IAAMH,EAAM,KAAK,KACXI,EAAI,EAAID,EACRE,EAAID,EAAI,EACVE,EAAUH,EAEVC,EAAIJ,EAAI,SACRM,EAAUN,EAAII,CAAC,EAAG,SAAWJ,EAAIM,CAAO,EAAG,SAAWF,EAAIE,EACtDD,EAAIL,EAAI,SACRM,EAAUN,EAAIK,CAAC,EAAG,SAAWL,EAAIM,CAAO,EAAG,SAAWD,EAAIC,GAE1DA,IAAYH,IACZ,KAAK,MAAMA,EAAGG,CAAO,EACrB,KAAK,SAASA,CAAO,GAGjC,CAEQ,UAAUV,EAAqB,CACnC,IAAMI,EAAM,KAAK,KACXH,EAAWG,EAAIJ,CAAK,EAAG,SACzBW,EAEJ,KAAOX,IAAU,IACbW,EAASX,GAAS,EACd,EAAAI,EAAIO,CAAM,EAAG,SAAWV,KAG5B,KAAK,MAAMD,EAAOW,CAAM,EACxBX,EAAQW,CAEhB,CAEQ,MAAMJ,EAAWK,EAAiB,CACtC,IAAMR,EAAM,KAAK,KACXF,EAAa,KAAK,YAClBW,EAAWT,EAAIG,CAAC,EAChBO,EAAWV,EAAIQ,CAAC,EAEtBR,EAAIG,CAAC,EAAIO,EACTV,EAAIQ,CAAC,EAAIC,EACTX,EAAWY,EAAS,GAAG,EAAIP,EAC3BL,EAAWW,EAAS,GAAG,EAAID,CAC/B,CACJ,EC3JA,IAAMG,GAAsC,IAAM,EAoB3C,SAASC,EACZC,EACAC,EACAC,EACAC,EACoB,CACpB,IAAMC,EAA8B,SAAUC,EAAG,CA9BrD,IAAAC,EA+BQ,OAAOA,EAAAN,EAAM,SAASK,CAAC,IAAhB,KAAAC,EAAqB,CAAC,CACjC,EAEA,OAAOC,GAAYP,EAAO,OAAOC,CAAM,EACnCC,GAAYJ,GACZK,GAAUC,CAAa,CAC/B,CAEA,SAASG,GACLP,EACAC,EACAC,EACAC,EACoB,CACpB,IAAMK,EAAgC,CAAC,EACjCC,EAAK,IAAIC,EACXL,EAAWM,EAETC,EAAkB,SAAUC,EAAkB,CAChD,IAAMC,EAAID,EAAK,IAAMR,EAAIQ,EAAK,EAAIA,EAAK,EACjCE,EAASP,EAAQM,CAAC,EACxB,GAAI,CAACC,EAAQ,OACb,IAAMC,EAASd,EAASW,CAAI,EACtBI,EAAWN,EAAO,SAAWK,EAEnC,GAAIA,EAAS,EACT,MAAM,IAAI,MAAM,4DACGH,EAAO,YAAcG,CAAM,EAG9CC,EAAWF,EAAO,WAClBA,EAAO,SAAWE,EAClBF,EAAO,YAAcV,EACrBI,EAAG,SAASK,EAAGG,CAAQ,EAE/B,EAQA,IANAjB,EAAM,MAAM,EAAE,QAAQ,SAAUK,EAAG,CAC/B,IAAMY,EAAWZ,IAAMJ,EAAS,EAAI,OAAO,kBAC3CO,EAAQH,CAAC,EAAI,CAAC,SAAUY,EAAU,YAAa,EAAE,EACjDR,EAAG,IAAIJ,EAAGY,CAAQ,CACtB,CAAC,EAEMR,EAAG,KAAK,EAAI,GAAG,CAClBJ,EAAII,EAAG,UAAU,EACjB,IAAMS,EAAQV,EAAQH,CAAC,EACvB,GAAI,CAACa,GAASA,EAAM,WAAa,OAAO,kBACpC,MAEJP,EAASO,EAETf,EAAOE,CAAC,EAAE,QAAQO,CAAe,CACrC,CAEA,OAAOJ,CACX,CCpEO,SAASW,EACZC,EACAC,EACAC,EACoC,CACpC,OAAOF,EAAM,MAAM,EAAE,OAAO,SAAUG,EAAKC,EAAG,CAC1C,OAAAD,EAAIC,CAAC,EAAIC,EAASL,EAAOI,EAAGH,EAAUC,CAAM,EACrCC,CACX,EAAG,CAAC,CAAyC,CACjD,CCNO,SAASG,EAAOC,EAA0B,CAC7C,IAAIC,EAAQ,EACNC,EAAkB,CAAC,EACnBC,EAAwC,CAAC,EACzCC,EAAsB,CAAC,EAE7B,SAASC,EAAIC,EAAiB,CA3BlC,IAAAC,EA4BQ,IAAMC,EAAQL,EAAQG,CAAC,EAAI,CACvB,QAAS,GACT,QAASL,EACT,MAAOA,GACX,EAkBA,GAjBAC,EAAM,KAAKI,CAAC,GAEZC,EAAAP,EAAM,WAAWM,CAAC,IAAlB,MAAAC,EAAqB,QAAQ,SAAUE,EAAG,CACtC,GAAMA,KAAKN,EAMJ,CACH,IAAMO,EAASP,EAAQM,CAAC,EACpBC,GAAA,MAAAA,EAAQ,UACRF,EAAM,QAAU,KAAK,IAAIA,EAAM,QAASE,EAAO,KAAK,EAE5D,KAXqB,CACjBL,EAAII,CAAC,EACL,IAAMC,EAASP,EAAQM,CAAC,EACpBC,IACAF,EAAM,QAAU,KAAK,IAAIA,EAAM,QAASE,EAAO,OAAO,EAE9D,CAMJ,GAEIF,EAAM,UAAYA,EAAM,MAAO,CAC/B,IAAMG,EAAiB,CAAC,EACpBF,EACJ,EAAG,CACCA,EAAIP,EAAM,IAAI,EACd,IAAMQ,EAASP,EAAQM,CAAC,EACpBC,IACAA,EAAO,QAAU,IAErBC,EAAK,KAAKF,CAAC,CACf,OAASH,IAAMG,GACfL,EAAQ,KAAKO,CAAI,CACrB,CACJ,CAEA,OAAAX,EAAM,MAAM,EAAE,QAAQ,SAAUM,EAAG,CACzBA,KAAKH,GACPE,EAAIC,CAAC,CAEb,CAAC,EAEMF,CACX,CC1DO,SAASQ,EAAWC,EAA0B,CACjD,OAAOC,EAAOD,CAAK,EAAE,OAAO,SAAUE,EAAM,CAfhD,IAAAC,EAgBQ,IAAMC,EAAYF,EAAK,CAAC,EACxB,OAAKE,EACEF,EAAK,OAAS,GACbA,EAAK,SAAW,KAAMC,EAAAH,EAAM,SAASI,EAAWA,CAAS,IAAnC,KAAAD,EAAwC,CAAC,GAAG,OAAS,EAF5D,EAG3B,CAAC,CACL,CClBA,IAAME,GAAsC,IAAM,EAqB3C,SAASC,EACZC,EACAC,EACAC,EACoC,CACpC,OAAOC,GAAiBH,EACpBC,GAAYH,GACZI,GAAU,SAAUE,EAAG,CA/B/B,IAAAC,EAgCY,OAAOA,EAAAL,EAAM,SAASI,CAAC,IAAhB,KAAAC,EAAqB,CAAC,CACjC,CAAC,CACT,CAEA,SAASF,GACLH,EACAC,EACAC,EACoC,CACpC,IAAMI,EAAgD,CAAC,EACjDC,EAAQP,EAAM,MAAM,EAE1B,OAAAO,EAAM,QAAQ,SAAUH,EAAG,CACvB,IAAMI,EAA6B,CAAC,EACpCF,EAAQF,CAAC,EAAII,EACbA,EAAKJ,CAAC,EAAI,CAAC,SAAU,EAAG,YAAa,EAAE,EACvCG,EAAM,QAAQ,SAAUE,EAAG,CACnBL,IAAMK,IACND,EAAKC,CAAC,EAAI,CAAC,SAAU,OAAO,kBAAmB,YAAa,EAAE,EAEtE,CAAC,EACDP,EAAOE,CAAC,EAAE,QAAQ,SAAUM,EAAM,CAC9B,IAAMD,EAAIC,EAAK,IAAMN,EAAIM,EAAK,EAAIA,EAAK,EACjCC,EAAIV,EAASS,CAAI,EACvBF,EAAKC,CAAC,EAAI,CAAC,SAAUE,EAAG,YAAaP,CAAC,CAC1C,CAAC,CACL,CAAC,EAEDG,EAAM,QAAQ,SAAUK,EAAG,CACvB,IAAMC,EAAOP,EAAQM,CAAC,EACjBC,GACLN,EAAM,QAAQ,SAAUO,EAAG,CACvB,IAAMC,EAAOT,EAAQQ,CAAC,EACjBC,GACLR,EAAM,QAAQ,SAAUS,EAAG,CACvB,IAAMC,EAAKF,EAAKH,CAAC,EACXM,EAAKL,EAAKG,CAAC,EACXG,EAAKJ,EAAKC,CAAC,EACjB,GAAIC,GAAMC,GAAMC,EAAI,CAChB,IAAMC,EAAcH,EAAG,SAAWC,EAAG,SACjCE,EAAcD,EAAG,WACjBA,EAAG,SAAWC,EACdD,EAAG,YAAcD,EAAG,YAE5B,CACJ,CAAC,CACL,CAAC,CACL,CAAC,EAEMZ,CACX,CChFO,IAAMe,EAAN,cAA6B,KAAM,CACtC,YAAYC,EAAkB,CAC1B,MAAMA,CAAO,EACb,KAAK,KAAO,gBAChB,CACJ,EAUO,SAASC,EAAQC,EAAwB,CAC5C,IAAMC,EAAmC,CAAC,EACpCC,EAAiC,CAAC,EAClCC,EAAoB,CAAC,EAE3B,SAASC,EAAMC,EAAoB,CAtBvC,IAAAC,EAuBQ,GAAID,KAAQH,EACR,MAAM,IAAIL,EAGRQ,KAAQJ,IACVC,EAAMG,CAAI,EAAI,GACdJ,EAAQI,CAAI,EAAI,IAChBC,EAAAN,EAAM,aAAaK,CAAI,IAAvB,MAAAC,EAA0B,QAAQF,GAClC,OAAOF,EAAMG,CAAI,EACjBF,EAAQ,KAAKE,CAAI,EAEzB,CAIA,GAFAL,EAAM,MAAM,EAAE,QAAQI,CAAK,EAEvB,OAAO,KAAKH,CAAO,EAAE,SAAWD,EAAM,UAAU,EAChD,MAAM,IAAIH,EAGd,OAAOM,CACX,CChCO,SAASI,EAAUC,EAAuB,CAC7C,GAAI,CACAC,EAAQD,CAAK,CACjB,OAAS,EAAG,CACR,GAAI,aAAaE,EACb,MAAO,GAEX,MAAM,CACV,CACA,MAAO,EACX,CCXO,SAASC,EACZC,EACAC,EACAC,EACAC,EACAC,EACC,CACI,MAAM,QAAQH,CAAE,IACjBA,EAAK,CAACA,CAAE,GAGZ,IAAMI,GAAeC,GAAW,CArBpC,IAAAC,EAqBwC,OAAAA,EAAAP,EAAE,WAAW,EAAIA,EAAE,WAAWM,CAAC,EAAIN,EAAE,UAAUM,CAAC,IAAhD,KAAAC,EAAsD,CAAC,IAErFC,EAAmC,CAAC,EAC1C,OAAAP,EAAG,QAAQ,SAAUK,EAAG,CACpB,GAAI,CAACN,EAAE,QAAQM,CAAC,EACZ,MAAM,IAAI,MAAM,6BAA+BA,CAAC,EAGpDF,EAAMK,EAAST,EAAGM,EAAGJ,IAAU,OAAQM,EAASH,EAAYF,EAAIC,CAAG,CACvE,CAAC,EACMA,CACX,CAEA,SAASK,EACLT,EACAM,EACAI,EACAF,EACAH,EACAF,EACAC,EACC,CACD,OAAME,KAAKE,IACPA,EAAQF,CAAC,EAAI,GAERI,IACDN,EAAMD,EAAGC,EAAKE,CAAC,GAEnBD,EAAWC,CAAC,EAAE,QAAQ,SAAUK,EAAG,CAC/BP,EAAMK,EAAST,EAAGW,EAAGD,EAAWF,EAASH,EAAYF,EAAIC,CAAG,CAChE,CAAC,EACGM,IACAN,EAAMD,EAAGC,EAAKE,CAAC,IAGhBF,CACX,CChDO,SAASQ,EAAIC,EAAUC,EAAuBC,EAAiC,CAClF,OAAOC,EAAOH,EAAGC,EAAIC,EAAO,SAAUE,EAAKC,EAAG,CAC1C,OAAAD,EAAI,KAAKC,CAAC,EACHD,CACX,EAAG,CAAC,CAAa,CACrB,CCFO,SAASE,EAAUC,EAAcC,EAAiC,CACrE,OAAOC,EAAIF,EAAOC,EAAI,MAAM,CAChC,CCFO,SAASE,EAASC,EAAcC,EAAiC,CACpE,OAAOC,EAAIF,EAAOC,EAAI,KAAK,CAC/B,CCCO,SAASE,EAAKC,EAAcC,EAAiC,CAfpE,IAAAC,EAgBI,IAAMC,EAAS,IAAIC,EACbC,EAAkC,CAAC,EACnCC,EAAK,IAAIC,EACXC,EAEJ,SAASC,EAAgBC,EAAkB,CACvC,IAAMC,EAAID,EAAK,IAAMF,EAAIE,EAAK,EAAIA,EAAK,EACjCE,EAAMN,EAAG,SAASK,CAAC,EACzB,GAAIC,IAAQ,OAAW,CACnB,IAAMC,EAAaZ,EAASS,CAAI,EAC5BG,EAAaD,IACbP,EAAQM,CAAC,EAAIH,EACbF,EAAG,SAASK,EAAGE,CAAU,EAEjC,CACJ,CAEA,GAAIb,EAAM,UAAU,IAAM,EACtB,OAAOG,EAGXH,EAAM,MAAM,EAAE,QAAQ,SAAUQ,EAAG,CAC/BF,EAAG,IAAIE,EAAG,OAAO,iBAAiB,EAClCL,EAAO,QAAQK,CAAC,CACpB,CAAC,EAGD,IAAMM,EAAYd,EAAM,MAAM,EAAE,CAAC,EAC7Bc,IAAc,QACdR,EAAG,SAASQ,EAAW,CAAC,EAG5B,IAAIC,EAAO,GACX,KAAOT,EAAG,KAAK,EAAI,GAAG,CAElB,GADAE,EAAIF,EAAG,UAAU,EACbE,KAAKH,EACLF,EAAO,QAAQK,EAAGH,EAAQG,CAAC,CAAE,MAC1B,IAAIO,EACP,MAAM,IAAI,MAAM,iCAAmCf,CAAK,EAExDe,EAAO,IAGXb,EAAAF,EAAM,UAAUQ,CAAC,IAAjB,MAAAN,EAAoB,QAAQO,EAChC,CAEA,OAAON,CACX,CC1DO,SAASa,EACZC,EACAC,EACAC,EACAC,EACoB,CACpB,OAAOC,GACHJ,EACAC,EACAC,EACAC,GAAA,KAAAA,GAAYE,GAAc,CAflC,IAAAC,EAgBY,OAAOA,EAAAN,EAAE,SAASK,CAAC,IAAZ,KAAAC,EAAiB,CAAC,CAC7B,EACJ,CACJ,CAEA,SAASF,GACLJ,EACAC,EACAC,EACAC,EACoB,CACpB,GAAID,IAAa,OACb,OAAOK,EAASP,EAAGC,EAAQC,EAAUC,CAAM,EAG/C,IAAIK,EAAqB,GACnBC,EAAQT,EAAE,MAAM,EAEtB,QAASU,EAAI,EAAGA,EAAID,EAAM,OAAQC,IAAK,CACnC,IAAMC,EAAOF,EAAMC,CAAC,EACpB,GAAIC,IAAS,OAAW,SACxB,IAAMC,EAAUT,EAAOQ,CAAI,EAE3B,QAASE,EAAI,EAAGA,EAAID,EAAQ,OAAQC,IAAK,CACrC,IAAMC,EAAOF,EAAQC,CAAC,EACtB,GAAI,CAACC,EAAM,SACX,IAAMC,EAAWD,EAAK,IAAMH,EAAOG,EAAK,EAAIA,EAAK,EAC3CE,EAAYD,IAAaD,EAAK,EAAIA,EAAK,EAAIA,EAAK,EAElDZ,EAAS,CAAC,EAAGa,EAAU,EAAGC,CAAS,CAAC,EAAI,IACxCR,EAAqB,GAE7B,CAEA,GAAIA,EACA,OAAOS,EAAYjB,EAAGC,EAAQC,EAAUC,CAAM,CAEtD,CAEA,OAAOI,EAASP,EAAGC,EAAQC,EAAUC,CAAM,CAC/C",
  "names": ["index_exports", "__export", "Graph", "alg_exports", "json_exports", "version", "__toCommonJS", "Graph", "opts", "label", "labelOrFn", "v", "names", "name", "removeEdge", "e", "child", "parent", "ancestor", "children", "predsV", "sucsV", "preds", "union", "sucs", "succ", "_a", "neighbors", "filter", "copy", "value", "parents", "findParent", "nodes", "w", "vStr", "wStr", "nameStr", "edgeValue", "valueSpecified", "edgeArgsToId", "edgeObj", "edgeArgsToObj", "incrementOrInitEntry", "edgeObjToId", "edgeLabel", "edge", "decrementOrRemoveEntry", "setV", "localEdge", "remoteEdge", "edges", "map", "k", "isDirected", "v_", "w_", "tmp", "version", "json_exports", "__export", "read", "write", "write", "graph", "json", "writeNodes", "writeEdges", "graphLabel", "g", "v", "nodeValue", "parent", "node", "edgeValue", "edge", "read", "Graph", "entry", "alg_exports", "__export", "CycleException", "bellmanFord", "components", "dijkstra", "dijkstraAll", "findCycles", "floydWarshall", "isAcyclic", "postorder", "preorder", "prim", "shortestPaths", "tarjan", "topsort", "DEFAULT_WEIGHT_FUNC", "bellmanFord", "g", "source", "weightFn", "edgeFn", "runBellmanFord", "v", "_a", "results", "didADistanceUpgrade", "iterations", "nodes", "relaxEdge", "edge", "uEntry", "wEntry", "edgeWeight", "relaxAllEdges", "vertex", "inVertex", "outVertex", "distance", "numberOfNodes", "i", "components", "graph", "visited", "cmpts", "cmpt", "dfs", "v", "_a", "_b", "PriorityQueue", "x", "key", "index", "priority", "keyIndices", "keyStr", "arr", "min", "currentPriority", "i", "l", "r", "largest", "parent", "j", "origArrI", "origArrJ", "DEFAULT_WEIGHT_FUNC", "dijkstra", "graph", "source", "weightFn", "edgeFn", "defaultEdgeFn", "v", "_a", "runDijkstra", "results", "pq", "PriorityQueue", "vEntry", "updateNeighbors", "edge", "w", "wEntry", "weight", "distance", "entry", "dijkstraAll", "graph", "weightFn", "edgeFn", "acc", "v", "dijkstra", "tarjan", "graph", "index", "stack", "visited", "results", "dfs", "v", "_a", "entry", "w", "wEntry", "cmpt", "findCycles", "graph", "tarjan", "cmpt", "_a", "firstNode", "DEFAULT_WEIGHT_FUNC", "floydWarshall", "graph", "weightFn", "edgeFn", "runFloydWarshall", "v", "_a", "results", "nodes", "rowV", "w", "edge", "d", "k", "rowK", "i", "rowI", "j", "ik", "kj", "ij", "altDistance", "CycleException", "message", "topsort", "graph", "visited", "stack", "results", "visit", "node", "_a", "isAcyclic", "graph", "topsort", "CycleException", "reduce", "g", "vs", "order", "fn", "acc", "navigation", "v", "_a", "visited", "doReduce", "postorder", "w", "dfs", "g", "vs", "order", "reduce", "acc", "v", "postorder", "graph", "vs", "dfs", "preorder", "graph", "vs", "dfs", "prim", "graph", "weightFn", "_a", "result", "Graph", "parents", "pq", "PriorityQueue", "v", "updateNeighbors", "edge", "w", "pri", "edgeWeight", "firstNode", "init", "shortestPaths", "g", "source", "weightFn", "edgeFn", "runShortestPaths", "v", "_a", "dijkstra", "negativeEdgeExists", "nodes", "i", "node", "adjList", "j", "edge", "inVertex", "outVertex", "bellmanFord"]
}