This is an automated email from the ASF dual-hosted git repository.
dongjoon pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/spark.git
The following commit(s) were added to refs/heads/master by this push:
new a663c0bf0c5 [SPARK-45104][UI] Upgrade `graphlib-dot.min.js` to 1.0.2
a663c0bf0c5 is described below
commit a663c0bf0c5b104170c0612f37a0b0cdf75cd45b
Author: Kent Yao <[email protected]>
AuthorDate: Fri Sep 8 13:32:37 2023 -0700
[SPARK-45104][UI] Upgrade `graphlib-dot.min.js` to 1.0.2
### What changes were proposed in this pull request?
This PR update the `graphlib-dot` library,
https://github.com/dagrejs/graphlib-dot/compare/v0.5.2...v1.0.2, this library
is used to read and parse dot files to graphics.
### Why are the changes needed?
Update UI js libraries
### Does this PR introduce _any_ user-facing change?
no
### How was this patch tested?
build and verify locally
### Was this patch authored or co-authored using generative AI tooling?
no
Closes #42853 from yaooqinn/SPARK-45104.
Authored-by: Kent Yao <[email protected]>
Signed-off-by: Dongjoon Hyun <[email protected]>
---
.../org/apache/spark/ui/static/graphlib-dot.min.js | 351 ++++++++++++++++++++-
1 file changed, 347 insertions(+), 4 deletions(-)
diff --git
a/core/src/main/resources/org/apache/spark/ui/static/graphlib-dot.min.js
b/core/src/main/resources/org/apache/spark/ui/static/graphlib-dot.min.js
index 037316f4e4f..d76e958f0e3 100644
--- a/core/src/main/resources/org/apache/spark/ui/static/graphlib-dot.min.js
+++ b/core/src/main/resources/org/apache/spark/ui/static/graphlib-dot.min.js
@@ -1,4 +1,347 @@
-/*v0.5.2*/(function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof
require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var
f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var
l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return
s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof
require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return
s})({1:[function(require,module,exports){(f [...]
-peg$currPos++}else{s3=peg$FAILED;if(peg$silentFails===0){peg$fail(peg$c81)}}}}while(s3!==peg$FAILED){s2.push(s3);s3=peg$currPos;if(input.substr(peg$currPos,2)===peg$c75){s4=peg$c75;peg$currPos+=2}else{s4=peg$FAILED;if(peg$silentFails===0){peg$fail(peg$c76)}}if(s4!==peg$FAILED){peg$reportedPos=s3;s4=peg$c77()}s3=s4;if(s3===peg$FAILED){s3=peg$currPos;if(input.charCodeAt(peg$currPos)===92){s4=peg$c78;peg$currPos++}else{s4=peg$FAILED;if(peg$silentFails===0){peg$fail(peg$c79)}}if(s4!==peg$FAI
[...]
\f "+"\n\r\u2028\u2029"+" ";var reEmptyStringLeading=/\b__p \+=
'';/g,reEmptyStringMiddle=/\b(__p \+=) ''
\+/g,reEmptyStringTrailing=/(__e\(.*?\)|\b__t\)) \+\n'';/g;var
reEsTemplate=/\$\{([^\\}]*(?:\\.[^\\}]*)*)\}/g;var reFlags=/\w*$/;var
reFuncName=/^\s*function[ \n\r\t]+\w/;var reInterpolate=/<%=([\s\S]+?)%>/g;var
reLeadingSpacesAndZeros=RegExp("^["+whitespace+"]*0+(?=.$)");var
reNoMatch=/($^)/;var reThis=/\bthis\b/;var
reUnescapedString=/['\n\r\t\u2028\u2029\\]/g;var co [...]
-var arrayRef=[];var objectProto=Object.prototype;var oldDash=context._;var
toString=objectProto.toString;var
reNative=RegExp("^"+String(toString).replace(/[.*+?^${}()|[\]\\]/g,"\\$&").replace(/toString|
for [^\]]+/g,".*?")+"$");var
ceil=Math.ceil,clearTimeout=context.clearTimeout,floor=Math.floor,fnToString=Function.prototype.toString,getPrototypeOf=isNative(getPrototypeOf=Object.getPrototypeOf)&&getPrototypeOf,hasOwnProperty=objectProto.hasOwnProperty,push=arrayRef.push,setTimeout=conte
[...]
-}}else{n=callback==null||thisArg?1:callback||n}return
slice(array,0,nativeMin(nativeMax(0,length-n),length))}function
intersection(){var
args=[],argsIndex=-1,argsLength=arguments.length,caches=getArray(),indexOf=getIndexOf(),trustIndexOf=indexOf===baseIndexOf,seen=getArray();while(++argsIndex<argsLength){var
value=arguments[argsIndex];if(isArray(value)||isArguments(value)){args.push(value);caches.push(trustIndexOf&&value.length>=largeArraySize&&createCache(argsIndex?args[argsIndex]:seen)
[...]
+/*
https://github.com/dagrejs/graphlib-dot/blob/v1.0.2/dist/graphlib-dot.min.js */
+(function(){function r(e,n,t){function o(i,f){if(!n[i]){if(!e[i]){var
c="function"==typeof require&&require;if(!f&&c)return c(i,!0);if(u)return
u(i,!0);var a=new Error("Cannot find module '"+i+"'");throw
a.code="MODULE_NOT_FOUND",a}var
p=n[i]={exports:{}};e[i][0].call(p.exports,function(r){var n=e[i][1][r];return
o(n||r)},p,p.exports,r,e,n,t)}return n[i].exports}for(var u="function"==typeof
require&&require,i=0;i<t.length;i++)o(t[i]);return o}return
r})()({1:[function(require,module,expo [...]
+/*
+ * Copyright (c) 2012-2013 Chris Pettitt
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to
deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
+global.graphlibDot=require("./index")}).call(this)}).call(this,typeof
global!=="undefined"?global:typeof self!=="undefined"?self:typeof
window!=="undefined"?window:{})},{"./index":2}],2:[function(require,module,exports){var
read=require("./lib/read-one");var readMany=require("./lib/read-many");var
write=require("./lib/write-one");var
version=require("./lib/version");module.exports={graphlib:require("@dagrejs/graphlib"),
+// Parsing
+read:read,readMany:readMany,
+// Writing
+write:write,
+// Version
+version:version,
+// For levelup encoding
+type:"dot",buffer:false}},{"./lib/read-many":5,"./lib/read-one":6,"./lib/version":7,"./lib/write-one":8,"@dagrejs/graphlib":9}],3:[function(require,module,exports){"use
strict";var
Graph=require("@dagrejs/graphlib").Graph;module.exports=buildGraph;function
buildGraph(parseTree){var
isDirected=parseTree.type!=="graph",isMultigraph=!parseTree.strict,defaultStack=[{node:{},edge:{}}],id=parseTree.id,g=new
Graph({directed:isDirected,multigraph:isMultigraph,compound:true});g.setGraph(id===null
[...]
+// If there are no statements remove the subgraph
+if(!g.children(id).length){g.removeNode(id)}defaultStack.pop()}function
handleAttrStmt(g,stmt,defaultStack){Object.assign(defaultStack[defaultStack.length-1][stmt.attrType],stmt.attrs)}function
handleInlineAttrsStmt(g,stmt,defaultStack,sg){Object.assign(sg?g.node(sg):g.graph(),stmt.attrs)}function
generateSubgraphId(g){var id;do{id=uniqueId("sg")}while(g.hasNode(id));return
id}function
maybeCreateNode(g,v,defaultStack,sg){if(!g.hasNode(v)){g.setNode(v,structuredClone(defaultStack[default
[...]
+// Collect all nodes involved in a subgraph statement
+function collectNodeIds(stmt){var ids={},stack=[],curr;var
push=stack.push.bind(stack);push(stmt);while(stack.length){curr=stack.pop();switch(curr.type){case"node":ids[curr.id]=true;break;case"edge":curr.elems.forEach(push);break;case"subgraph":curr.stmts.forEach(push);break}}return
Object.keys(ids)}let idCounter=0;function uniqueId(prefix){var
id=++idCounter;return
toString(prefix)+id}},{"@dagrejs/graphlib":9}],4:[function(require,module,exports){module.exports=function(){
+/*
+ * Generated by PEG.js 0.8.0.
+ *
+ * http://pegjs.majda.cz/
+ */
+function peg$subclass(child,parent){function
ctor(){this.constructor=child}ctor.prototype=parent.prototype;child.prototype=new
ctor}function
SyntaxError(message,expected,found,offset,line,column){this.message=message;this.expected=expected;this.found=found;this.offset=offset;this.line=line;this.column=column;this.name="SyntaxError"}peg$subclass(SyntaxError,Error);function
parse(input){var
options=arguments.length>1?arguments[1]:{},peg$FAILED={},peg$startRuleFunctions={start:peg$parsestar
[...]
+// Helper object for making a pretty printer
+function
Writer(){this._indent="";this._content="";this._shouldIndent=true}Writer.prototype.INDENT="
";Writer.prototype.indent=function(){this._indent+=this.INDENT};Writer.prototype.unindent=function(){this._indent=this._indent.slice(this.INDENT.length)};Writer.prototype.writeLine=function(line){this.write((line||"")+"\n");this._shouldIndent=true};Writer.prototype.write=function(str){if(this._shouldIndent){this._shouldIndent=false;this._content+=this._indent}this._content+=str};Writer.p
[...]
+/**
+ * Copyright (c) 2014, Chris Pettitt
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice,
this
+ * list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ *
+ * 3. Neither the name of the copyright holder nor the names of its
contributors
+ * may be used to endorse or promote products derived from this software
without
+ * specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+var
lib=require("./lib");module.exports={Graph:lib.Graph,json:require("./lib/json"),alg:require("./lib/alg"),version:lib.version}},{"./lib":25,"./lib/alg":16,"./lib/json":26}],10:[function(require,module,exports){module.exports=components;function
components(g){var visited={};var cmpts=[];var cmpt;function
dfs(v){if(visited.hasOwnProperty(v))return;visited[v]=true;cmpt.push(v);g.successors(v).forEach(dfs);g.predecessors(v).forEach(dfs)}g.nodes().forEach(function(v){cmpt=[];dfs(v);if(cmpt
[...]
+/*
+ * A helper that preforms a pre- or post-order traversal on the input graph
+ * and returns the nodes in the order they were visited. If the graph is
+ * undirected then this algorithm will navigate using neighbors. If the graph
+ * is directed then this algorithm will navigate using successors.
+ *
+ * If the order is not "post", it will be treated as "pre".
+ */function dfs(g,vs,order){if(!Array.isArray(vs)){vs=[vs]}var
navigation=g.isDirected()?v=>g.successors(v):v=>g.neighbors(v);var
orderFunc=order==="post"?postOrderDfs:preOrderDfs;var acc=[];var
visited={};vs.forEach(v=>{if(!g.hasNode(v)){throw new Error("Graph does not
have node: "+v)}orderFunc(v,navigation,visited,acc)});return acc}function
postOrderDfs(v,navigation,visited,acc){var
stack=[[v,false]];while(stack.length>0){var
curr=stack.pop();if(curr[1]){acc.push(curr[0])}else{if(!visi [...]
+// Start from an arbitrary node
+pq.decrease(g.nodes()[0],0);var
init=false;while(pq.size()>0){v=pq.removeMin();if(parents.hasOwnProperty(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}},{"../data/priority-queue":23,"../graph":24}],21:[function(require,module,exports){module.exports=tarjan;function
tarjan(g){var index=0;var stack=[];var visited={};// node id -> { onStack,
lowlink, index }
+var results=[];function dfs(v){var
entry=visited[v]={onStack:true,lowlink:index,index:index++};stack.push(v);g.successors(v).forEach(function(w){if(!visited.hasOwnProperty(w)){dfs(w);entry.lowlink=Math.min(entry.lowlink,visited[w].lowlink)}else
if(visited[w].onStack){entry.lowlink=Math.min(entry.lowlink,visited[w].index)}});if(entry.lowlink===entry.index){var
cmpt=[];var
w;do{w=stack.pop();visited[w].onStack=false;cmpt.push(w)}while(v!==w);results.push(cmpt)}}g.nodes().forEach(function(v
[...]
+/**
+ * A min-priority queue data structure. This algorithm is derived from Cormen,
+ * et al., "Introduction to Algorithms". The basic idea of a min-priority
+ * queue is that you can efficiently (in O(1) time) get the smallest key in
+ * the queue. Adding and removing elements takes O(log n) time. A key can
+ * have its priority decreased in O(log n) time.
+ */
+class PriorityQueue{#arr=[];#keyIndices={};
+/**
+ * Returns the number of elements in the queue. Takes `O(1)` time.
+ */size(){return this.#arr.length}
+/**
+ * Returns the keys that are in the queue. Takes `O(n)` time.
+ */keys(){return this.#arr.map(function(x){return x.key})}
+/**
+ * Returns `true` if **key** is in the queue and `false` if not.
+ */has(key){return this.#keyIndices.hasOwnProperty(key)}
+/**
+ * Returns the priority for **key**. If **key** is not present in the queue
+ * then this function returns `undefined`. Takes `O(1)` time.
+ *
+ * @param {Object} key
+ */priority(key){var
index=this.#keyIndices[key];if(index!==undefined){return
this.#arr[index].priority}}
+/**
+ * Returns the key for the minimum element in this queue. If the queue is
+ * empty this function throws an Error. Takes `O(1)` time.
+ */min(){if(this.size()===0){throw new Error("Queue underflow")}return
this.#arr[0].key}
+/**
+ * Inserts a new key into the priority queue. If the key already exists in
+ * the queue this function returns `false`; otherwise it will return `true`.
+ * Takes `O(n)` time.
+ *
+ * @param {Object} key the key to add
+ * @param {Number} priority the initial priority for the key
+ */add(key,priority){var
keyIndices=this.#keyIndices;key=String(key);if(!keyIndices.hasOwnProperty(key)){var
arr=this.#arr;var
index=arr.length;keyIndices[key]=index;arr.push({key:key,priority:priority});this.#decrease(index);return
true}return false}
+/**
+ * Removes and returns the smallest key in the queue. Takes `O(log n)` time.
+ */removeMin(){this.#swap(0,this.#arr.length-1);var
min=this.#arr.pop();delete this.#keyIndices[min.key];this.#heapify(0);return
min.key}
+/**
+ * Decreases the priority for **key** to **priority**. If the new priority is
+ * greater than the previous priority, this function will throw an Error.
+ *
+ * @param {Object} key the key for which to raise priority
+ * @param {Number} priority the new priority for the key
+ */decrease(key,priority){var
index=this.#keyIndices[key];if(priority>this.#arr[index].priority){throw new
Error("New priority is greater than current priority. "+"Key: "+key+" Old:
"+this.#arr[index].priority+" New:
"+priority)}this.#arr[index].priority=priority;this.#decrease(index)}#heapify(i){var
arr=this.#arr;var l=2*i;var r=l+1;var
largest=i;if(l<arr.length){largest=arr[l].priority<arr[largest].priority?l:largest;if(r<arr.length){largest=arr[r].priority<arr[largest].priority?r:la
[...]
+// Implementation notes:
+//
+// * Node id query functions should return string ids for the nodes
+// * Edge id query functions should return an "edgeObj", edge object, that is
+// composed of enough information to uniquely identify an edge: {v, w,
name}.
+// * Internally we use an "edgeId", a stringified form of the edgeObj, to
+// reference edges. This is because we need a performant way to look these
+// edges up and, object properties, which have string keys, are the closest
+// we're going to get to a performant hashtable in JavaScript.
+class Graph{#isDirected=true;#isMultigraph=false;#isCompound=false;
+// Label for the graph itself
+#label;
+// Defaults to be set when creating a new node
+#defaultNodeLabelFn=()=>undefined;
+// Defaults to be set when creating a new edge
+#defaultEdgeLabelFn=()=>undefined;
+// v -> label
+#nodes={};
+// v -> edgeObj
+#in={};
+// u -> v -> Number
+#preds={};
+// v -> edgeObj
+#out={};
+// v -> w -> Number
+#sucs={};
+// e -> edgeObj
+#edgeObjs={};
+// e -> label
+#edgeLabels={};
+/* Number of nodes in the graph. Should only be changed by the implementation.
*/#nodeCount=0;
+/* Number of edges in the graph. Should only be changed by the implementation.
*/#edgeCount=0;#parent;#children;constructor(opts){if(opts){this.#isDirected=opts.hasOwnProperty("directed")?opts.directed:true;this.#isMultigraph=opts.hasOwnProperty("multigraph")?opts.multigraph:false;this.#isCompound=opts.hasOwnProperty("compound")?opts.compound:false}if(this.#isCompound){
+// v -> parent
+this.#parent={};
+// v -> children
+this.#children={};this.#children[GRAPH_NODE]={}}}
+/* === Graph functions ========= */
+/**
+ * Whether graph was created with 'directed' flag set to true or not.
+ */isDirected(){return this.#isDirected}
+/**
+ * Whether graph was created with 'multigraph' flag set to true or not.
+ */isMultigraph(){return this.#isMultigraph}
+/**
+ * Whether graph was created with 'compound' flag set to true or not.
+ */isCompound(){return this.#isCompound}
+/**
+ * Sets the label of the graph.
+ */setGraph(label){this.#label=label;return this}
+/**
+ * Gets the graph label.
+ */graph(){return this.#label}
+/* === Node functions ========== */
+/**
+ * Sets the default node label. If newDefault is a function, it will be
+ * invoked ach time when setting a label for a node. Otherwise, this label
+ * will be assigned as default label in case if no label was specified while
+ * setting a node.
+ * Complexity: O(1).
+
*/setDefaultNodeLabel(newDefault){this.#defaultNodeLabelFn=newDefault;if(typeof
newDefault!=="function"){this.#defaultNodeLabelFn=()=>newDefault}return this}
+/**
+ * Gets the number of nodes in the graph.
+ * Complexity: O(1).
+ */nodeCount(){return this.#nodeCount}
+/**
+ * Gets all nodes of the graph. Note, the in case of compound graph subnodes
are
+ * not included in list.
+ * Complexity: O(1).
+ */nodes(){return Object.keys(this.#nodes)}
+/**
+ * Gets list of nodes without in-edges.
+ * Complexity: O(|V|).
+ */sources(){var self=this;return
this.nodes().filter(v=>Object.keys(self.#in[v]).length===0)}
+/**
+ * Gets list of nodes without out-edges.
+ * Complexity: O(|V|).
+ */sinks(){var self=this;return
this.nodes().filter(v=>Object.keys(self.#out[v]).length===0)}
+/**
+ * Invokes setNode method for each node in names list.
+ * Complexity: O(|names|).
+ */setNodes(vs,value){var args=arguments;var
self=this;vs.forEach(function(v){if(args.length>1){self.setNode(v,value)}else{self.setNode(v)}});return
this}
+/**
+ * Creates or updates the value for the node v in the graph. If label is
supplied
+ * it is set as the value for the node. If label is not supplied and the
node was
+ * created by this call then the default node label will be assigned.
+ * Complexity: O(1).
+
*/setNode(v,value){if(this.#nodes.hasOwnProperty(v)){if(arguments.length>1){this.#nodes[v]=value}return
this}this.#nodes[v]=arguments.length>1?value:this.#defaultNodeLabelFn(v);if(this.#isCompound){this.#parent[v]=GRAPH_NODE;this.#children[v]={};this.#children[GRAPH_NODE][v]=true}this.#in[v]={};this.#preds[v]={};this.#out[v]={};this.#sucs[v]={};++this.#nodeCount;return
this}
+/**
+ * Gets the label of node with specified name.
+ * Complexity: O(|V|).
+ */node(v){return this.#nodes[v]}
+/**
+ * Detects whether graph has a node with specified name or not.
+ */hasNode(v){return this.#nodes.hasOwnProperty(v)}
+/**
+ * Remove the node with the name from the graph or do nothing if the node is
not in
+ * the graph. If the node was removed this function also removes any incident
+ * edges.
+ * Complexity: O(1).
+ */removeNode(v){var self=this;if(this.#nodes.hasOwnProperty(v)){var
removeEdge=e=>self.removeEdge(self.#edgeObjs[e]);delete
this.#nodes[v];if(this.#isCompound){this.#removeFromParentsChildList(v);delete
this.#parent[v];this.children(v).forEach(function(child){self.setParent(child)});delete
this.#children[v]}Object.keys(this.#in[v]).forEach(removeEdge);delete
this.#in[v];delete
this.#preds[v];Object.keys(this.#out[v]).forEach(removeEdge);delete
this.#out[v];delete this.#sucs[v];--this. [...]
+/**
+ * Sets node p as a parent for node v if it is defined, or removes the
+ * parent for v if p is undefined. Method throws an exception in case of
+ * invoking it in context of noncompound graph.
+ * Average-case complexity: O(1).
+ */setParent(v,parent){if(!this.#isCompound){throw new Error("Cannot set
parent in a non-compound graph")}if(parent===undefined){parent=GRAPH_NODE}else{
+// Coerce parent to string
+parent+="";for(var
ancestor=parent;ancestor!==undefined;ancestor=this.parent(ancestor)){if(ancestor===v){throw
new Error("Setting "+parent+" as parent of "+v+" would create a
cycle")}}this.setNode(parent)}this.setNode(v);this.#removeFromParentsChildList(v);this.#parent[v]=parent;this.#children[parent][v]=true;return
this}#removeFromParentsChildList(v){delete this.#children[this.#parent[v]][v]}
+/**
+ * Gets parent node for node v.
+ * Complexity: O(1).
+ */parent(v){if(this.#isCompound){var
parent=this.#parent[v];if(parent!==GRAPH_NODE){return parent}}}
+/**
+ * Gets list of direct children of node v.
+ * Complexity: O(1).
+ */children(v=GRAPH_NODE){if(this.#isCompound){var
children=this.#children[v];if(children){return Object.keys(children)}}else
if(v===GRAPH_NODE){return this.nodes()}else if(this.hasNode(v)){return[]}}
+/**
+ * Return all nodes that are predecessors of the specified node or undefined
if node v is not in
+ * the graph. Behavior is undefined for undirected graphs - use neighbors
instead.
+ * Complexity: O(|V|).
+ */predecessors(v){var predsV=this.#preds[v];if(predsV){return
Object.keys(predsV)}}
+/**
+ * Return all nodes that are successors of the specified node or undefined
if node v is not in
+ * the graph. Behavior is undefined for undirected graphs - use neighbors
instead.
+ * Complexity: O(|V|).
+ */successors(v){var sucsV=this.#sucs[v];if(sucsV){return
Object.keys(sucsV)}}
+/**
+ * Return all nodes that are predecessors or successors of the specified
node or undefined if
+ * node v is not in the graph.
+ * Complexity: O(|V|).
+ */neighbors(v){var preds=this.predecessors(v);if(preds){const union=new
Set(preds);for(var succ of this.successors(v)){union.add(succ)}return
Array.from(union.values())}}isLeaf(v){var
neighbors;if(this.isDirected()){neighbors=this.successors(v)}else{neighbors=this.neighbors(v)}return
neighbors.length===0}
+/**
+ * Creates new graph with nodes filtered via filter. Edges incident to
rejected node
+ * are also removed. In case of compound graph, if parent is rejected by
filter,
+ * than all its children are rejected too.
+ * Average-case complexity: O(|E|+|V|).
+ */filterNodes(filter){var copy=new
this.constructor({directed:this.#isDirected,multigraph:this.#isMultigraph,compound:this.#isCompound});copy.setGraph(this.graph());var
self=this;Object.entries(this.#nodes).forEach(function([v,value]){if(filter(v)){copy.setNode(v,value)}});Object.values(this.#edgeObjs).forEach(function(e){if(copy.hasNode(e.v)&©.hasNode(e.w)){copy.setEdge(e,self.edge(e))}});var
parents={};function findParent(v){var
parent=self.parent(v);if(parent===undefined||copy. [...]
+/* === Edge functions ========== */
+/**
+ * Sets the default edge label or factory function. This label will be
+ * assigned as default label in case if no label was specified while setting
+ * an edge or this function will be invoked each time when setting an edge
+ * with no label specified and returned value * will be used as a label for
edge.
+ * Complexity: O(1).
+
*/setDefaultEdgeLabel(newDefault){this.#defaultEdgeLabelFn=newDefault;if(typeof
newDefault!=="function"){this.#defaultEdgeLabelFn=()=>newDefault}return this}
+/**
+ * Gets the number of edges in the graph.
+ * Complexity: O(1).
+ */edgeCount(){return this.#edgeCount}
+/**
+ * Gets edges of the graph. In case of compound graph subgraphs are not
considered.
+ * Complexity: O(|E|).
+ */edges(){return Object.values(this.#edgeObjs)}
+/**
+ * Establish an edges path over the nodes in nodes list. If some edge is
already
+ * exists, it will update its label, otherwise it will create an edge
between pair
+ * of nodes with label provided or default label if no label provided.
+ * Complexity: O(|nodes|).
+ */setPath(vs,value){var self=this;var
args=arguments;vs.reduce(function(v,w){if(args.length>1){self.setEdge(v,w,value)}else{self.setEdge(v,w)}return
w});return this}
+/**
+ * Creates or updates the label for the edge (v, w) with the optionally
supplied
+ * name. If label is supplied it is set as the value for the edge. If label
is not
+ * supplied and the edge was created by this call then the default edge
label will
+ * be assigned. The name parameter is only useful with multigraphs.
+ */setEdge(){var v,w,name,value;var valueSpecified=false;var
arg0=arguments[0];if(typeof arg0==="object"&&arg0!==null&&"v"in
arg0){v=arg0.v;w=arg0.w;name=arg0.name;if(arguments.length===2){value=arguments[1];valueSpecified=true}}else{v=arg0;w=arguments[1];name=arguments[3];if(arguments.length>2){value=arguments[2];valueSpecified=true}}v=""+v;w=""+w;if(name!==undefined){name=""+name}var
e=edgeArgsToId(this.#isDirected,v,w,name);if(this.#edgeLabels.hasOwnProperty(e)){if(valueSpecified){t
[...]
+// It didn't exist, so we need to create it.
+// First ensure the nodes exist.
+this.setNode(v);this.setNode(w);this.#edgeLabels[e]=valueSpecified?value:this.#defaultEdgeLabelFn(v,w,name);var
edgeObj=edgeArgsToObj(this.#isDirected,v,w,name);
+// Ensure we add undirected edges in a consistent way.
+v=edgeObj.v;w=edgeObj.w;Object.freeze(edgeObj);this.#edgeObjs[e]=edgeObj;incrementOrInitEntry(this.#preds[w],v);incrementOrInitEntry(this.#sucs[v],w);this.#in[w][e]=edgeObj;this.#out[v][e]=edgeObj;this.#edgeCount++;return
this}
+/**
+ * Gets the label for the specified edge.
+ * Complexity: O(1).
+ */edge(v,w,name){var
e=arguments.length===1?edgeObjToId(this.#isDirected,arguments[0]):edgeArgsToId(this.#isDirected,v,w,name);return
this.#edgeLabels[e]}
+/**
+ * Gets the label for the specified edge and converts it to an object.
+ * Complexity: O(1)
+ */edgeAsObj(){const edge=this.edge(...arguments);if(typeof
edge!=="object"){return{label:edge}}return edge}
+/**
+ * Detects whether the graph contains specified edge or not. No subgraphs
are considered.
+ * Complexity: O(1).
+ */hasEdge(v,w,name){var
e=arguments.length===1?edgeObjToId(this.#isDirected,arguments[0]):edgeArgsToId(this.#isDirected,v,w,name);return
this.#edgeLabels.hasOwnProperty(e)}
+/**
+ * Removes the specified edge from the graph. No subgraphs are considered.
+ * Complexity: O(1).
+ */removeEdge(v,w,name){var
e=arguments.length===1?edgeObjToId(this.#isDirected,arguments[0]):edgeArgsToId(this.#isDirected,v,w,name);var
edge=this.#edgeObjs[e];if(edge){v=edge.v;w=edge.w;delete
this.#edgeLabels[e];delete
this.#edgeObjs[e];decrementOrRemoveEntry(this.#preds[w],v);decrementOrRemoveEntry(this.#sucs[v],w);delete
this.#in[w][e];delete this.#out[v][e];this.#edgeCount--}return this}
+/**
+ * Return all edges that point to the node v. Optionally filters those edges
down to just those
+ * coming from node u. Behavior is undefined for undirected graphs - use
nodeEdges instead.
+ * Complexity: O(|E|).
+ */inEdges(v,u){var inV=this.#in[v];if(inV){var
edges=Object.values(inV);if(!u){return edges}return
edges.filter(edge=>edge.v===u)}}
+/**
+ * Return all edges that are pointed at by node v. Optionally filters those
edges down to just
+ * those point to w. Behavior is undefined for undirected graphs - use
nodeEdges instead.
+ * Complexity: O(|E|).
+ */outEdges(v,w){var outV=this.#out[v];if(outV){var
edges=Object.values(outV);if(!w){return edges}return
edges.filter(edge=>edge.w===w)}}
+/**
+ * Returns all edges to or from node v regardless of direction. Optionally
filters those edges
+ * down to just those between nodes v and w regardless of direction.
+ * Complexity: O(|E|).
+ */nodeEdges(v,w){var inEdges=this.inEdges(v,w);if(inEdges){return
inEdges.concat(this.outEdges(v,w))}}}function
incrementOrInitEntry(map,k){if(map[k]){map[k]++}else{map[k]=1}}function
decrementOrRemoveEntry(map,k){if(!--map[k]){delete map[k]}}function
edgeArgsToId(isDirected,v_,w_,name){var v=""+v_;var
w=""+w_;if(!isDirected&&v>w){var tmp=v;v=w;w=tmp}return
v+EDGE_KEY_DELIM+w+EDGE_KEY_DELIM+(name===undefined?DEFAULT_EDGE_NAME:name)}function
edgeArgsToObj(isDirected,v_,w_,name){var v=" [...]
+// Includes only the "core" of graphlib
+module.exports={Graph:require("./graph"),version:require("./version")}},{"./graph":24,"./version":27}],26:[function(require,module,exports){var
Graph=require("./graph");module.exports={write:write,read:read};
+/**
+ * Creates a JSON representation of the graph that can be serialized to a
string with
+ * JSON.stringify. The graph can later be restored using json.read.
+ */function write(g){var
json={options:{directed:g.isDirected(),multigraph:g.isMultigraph(),compound:g.isCompound()},nodes:writeNodes(g),edges:writeEdges(g)};if(g.graph()!==undefined){json.value=structuredClone(g.graph())}return
json}function writeNodes(g){return g.nodes().map(function(v){var
nodeValue=g.node(v);var parent=g.parent(v);var
node={v:v};if(nodeValue!==undefined){node.value=nodeValue}if(parent!==undefined){node.parent=parent}return
node})}function writeEdges(g){return g.edges [...]
+/**
+ * Takes JSON as input and returns the graph representation.
+ *
+ * @example
+ * var g2 = graphlib.json.read(JSON.parse(str));
+ * g2.nodes();
+ * // ['a', 'b']
+ * g2.edges()
+ * // [ { v: 'a', w: 'b' } ]
+ */function read(json){var g=new
Graph(json.options).setGraph(json.value);json.nodes.forEach(function(entry){g.setNode(entry.v,entry.value);if(entry.parent){g.setParent(entry.v,entry.parent)}});json.edges.forEach(function(entry){g.setEdge({v:entry.v,w:entry.w,name:entry.name},entry.value)});return
g}},{"./graph":24}],27:[function(require,module,exports){module.exports="2.1.13"},{}]},{},[1]);
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
