function Graph(serialized) { // List of 'public' methods (returned with the Graph instance) const graph = { setLookup, getLookup, addNode, removeNode, nodes, adjacent, inNodes, inEdges, outEdges, distinctNeighbours, component, components, addEdge, addUndirectedEdge, removeEdge, contractEdge, hasEdge, setEdgeWeight, getEdgeWeight, getEdgeWeights, indegree, outdegree, depthFirstSearch, breadthFirstSearch, hasCycle, isTree, lowestCommonAncestors, topologicalSort, distancesFrom, distancesTo, costMatrix, diameter, betweenness, shortestPath, mst, contract, serialize, deserialize, toDot }; // Provide a string encoding of an edge, const encodeEdge = (u, v) => u + "|" + v; // Queue for BFS. class Queue { constructor() { this.items = {}; this.front = 0; this.rear = 0; } enqueue(item) { this.items[this.rear] = item; this.rear++; return this; } dequeue() { const item = this.items[this.front]; delete this.items[this.front]; this.front++; return item; } peek() { return this.items[this.front]; } get size() { return this.rear - this.front; } } // A Disjoint Set data structure - see https://en.wikipedia.org/wiki/Disjoint-set_data_structure // Elements are defined by their integer indices not their values. class DisjointSet { constructor(n) { this.rank = Array(n).fill(0); this.parent = Array(n) .fill(0) .map((_, i) => i); this.n = n; } find(x) { if (this.parent[x] !== x) { this.parent[x] = this.find(this.parent[x]); } return this.parent[x]; } union(x, y) { const xRoot = this.find(x); const yRoot = this.find(y); if (xRoot === yRoot) { // No merging as already in the same set. return; } if (this.rank[xRoot] < this.rank[yRoot]) { this.parent[xRoot] = yRoot; } else if (this.rank[yRoot] < this.rank[xRoot]) { this.parent[yRoot] = xRoot; } else { this.parent[yRoot] = xRoot; this.rank[xRoot] = this.rank[xRoot] + 1; } } } // The adjacency list of the graph. Keys are node ids. Values are adjacent node id arrays. const edges = Object.create(null); const revEdges = Object.create(null); // The weights of edges. Keys are string encodings of edges. aVlues are arrays of weights, // one per parallel edge instance, in insertion order.`` const edgeWeights = Object.create(null); // Optional lookup data structure for relating node ids to other attributes. let lu; // For internal processing that might include parallel edge weights function minEdgeWeight(u, v) { const ws = edgeWeights[encodeEdge(u, v)]; if (!ws || ws.length === 0) { return 1; } let m = ws[0]; for (let i = 1; i < ws.length; i++) { if (ws[i] < m) { m = ws[i]; } } return m; } // If a serialized graph was passed into the constructor, deserialize it. if (serialized) { deserialize(serialized); } // --------------------------------------------------------------- Set the lookup data structure // For storing multiple attributes associated with each node ID. If nodes are integers, can be // an array where the index is the node ID. Or could be an object with key as node id and value // as associated attributes. function setLookup(newLu) { lu = newLu; return graph; } // --------------------------------------------------------------- Get the lookup data structure function getLookup() { return lu; } // --------------------------------------------------------------- Add a node to the graph. // If node was not already added, this function sets up an empty adjacency list. function addNode(node) { edges[node] ??= []; revEdges[node] ??= []; return graph; } // --------------------------------------------------------------- Remove a node from the graph. // Also removes incoming and outgoing edges. function removeNode(node) { for (const v of new Set(adjacent(node))) { removeEdge(node, v); } for (const u of new Set(inNodes(node))) { removeEdge(u, node); } delete edges[node]; delete revEdges[node]; return graph; } // --------------------------------------------------------------- Connected sub-graph connected to a node function component(startNode, { weak = true } = {}) { if (!(startNode in edges) && !(startNode in revEdges)) { return new Graph(); } const neighboursOf = weak ? distinctNeighbours : adjacent; // BFS to collect nodes in the component const visited = new Set([startNode]); const q = new Queue().enqueue(startNode); while (q.size > 0) { const u = q.dequeue(); for (const v of neighboursOf(u)) { if (!visited.has(v)) { visited.add(v); q.enqueue(v); } } } // Build induced subgraph const sub = new Graph(); const nodesIn = visited; // Copy lookup for just these nodes if (lu !== undefined && lu !== null) { if (Array.isArray(lu)) { const lu2 = []; for (const n of nodesIn) { const i = Number(n); if (Number.isInteger(i) && i >= 0 && i < lu.length) { lu2[i] = lu[i]; } } sub.setLookup(lu2); } else if (typeof lu === "object") { const lu2 = {}; for (const n of nodesIn) { if (n in lu) { lu2[n] = lu[n]; } } sub.setLookup(lu2); } else { sub.setLookup(lu); } } for (const u of nodesIn) { sub.addNode(u); } // Copy edges for (const u of nodesIn) { const outs = typeof graph.outEdges === "function" ? graph.outEdges(u) : adjacent(u).map((v) => ({ to: v, weight: getEdgeWeight(u, v) })); for (const { to: v, weight } of outs) { if (nodesIn.has(v)) { sub.addEdge(u, v, weight); } } } return sub; } // --------------------------------------------------------------- Report distinct sub-graphs (components) function components({ weak = true } = {}) { const [ns, comp, groups] = [nodes(), new Map(), []]; let id = 0; for (const start of ns) { if (comp.has(start)) { continue; } const group = []; comp.set(start, id); const q = new Queue().enqueue(start); while (q.size > 0) { const u = q.dequeue(); group.push(u); for (const v of adjacent(u)) { if (!comp.has(v)) { comp.set(v, id); q.enqueue(v); } } if (weak) { for (const v of inNodes(u)) { if (!comp.has(v)) { comp.set(v, id); q.enqueue(v); } } } } groups.push(group); id++; } return { count: id, comp, groups }; } // --------------------------------------------------------------- Report nodes added to the graph. function nodes(byGroup = false) { const nodeSet = {}; Object.keys(edges).forEach(function (u) { nodeSet[u] = true; edges[u].forEach(function (v) { nodeSet[v] = true; }); }); const nodes = Object.keys(nodeSet); // Group by connected nodes if requested. if (byGroup) { const visited = new Set(); const groups = []; for (const node of nodes) { if (!visited.has(node)) { const newNodes = breadthFirstSearch(node); groups.push(newNodes); newNodes.forEach((n) => visited.add(n)); } } return groups; } // Otherwise all nodes, whether connected or not. return nodes; } // --------------------------------------------------------------- Outgoing nodes adjacent to given node. // Returns an empty array for unknown nodes. function adjacent(node) { return edges[node] || []; } // --------------------------------------------------------------- What are the incoming nodes? function inNodes(node) { return revEdges[node] || []; } // --------------------------------------------------------------- Distinct neighbouring nodes. function distinctNeighbours(node) { const ns = new Set(inNodes(node).concat(adjacent(node))); ns.delete(node); return [...ns]; } // --------------------------------------------------------------- Incoming edges to given node. function inEdges(v) { const ins = inNodes(v); const counts = new Map(); const result = []; for (const u of ins) { const k = encodeEdge(u, v); const i = counts.get(k) ?? 0; counts.set(k, i + 1); const ws = edgeWeights[k] ?? []; result.push({ from: u, weight: ws[i] ?? 1 }); } return result; } // --------------------------------------------------------------- Outgoing edges from given node. function outEdges(u) { const outs = adjacent(u); const counts = new Map(); const result = []; for (const v of outs) { const k = encodeEdge(u, v); const i = counts.get(k) ?? 0; counts.set(k, i + 1); const ws = edgeWeights[k] ?? []; result.push({ to: v, weight: ws[i] ?? 1 }); } return result; } // --------------------------------------------------------------- Set the weight of the given edge. function setEdgeWeight(u, v, weight) { const k = encodeEdge(u, v); edgeWeights[k] = Array.isArray(weight) ? weight.slice() : [weight]; return graph; } // --------------------------------------------------------------- Report weight of the given edge. // For backward compatibility, returns the last edge weight set if multiple weighted // edges between u and v exist. function getEdgeWeight(u, v) { const ws = edgeWeights[encodeEdge(u, v)]; return ws === undefined ? 1 : ws.at(-1); } // The weights in edge insertion order. function getEdgeWeights(u, v) { const ws = edgeWeights[encodeEdge(u, v)]; return ws === undefined ? [] : ws.slice(); } // --------------------------------------------------------------- Add an edge from node u to node v. // Implicitly adds the nodes if they were not already added. function addEdge(u, v, weight) { addNode(u); addNode(v); edges[u].push(v); revEdges[v].push(u); const k = encodeEdge(u, v); (edgeWeights[k] ??= []).push(weight === undefined ? 1 : weight); return graph; } // --------------------------------------------------------------- Add an undirected edge between u and v. // Implicitly adds the nodes if they were not already added. function addUndirectedEdge(u, v, weight) { return addEdge(u, v, weight).addEdge(v, u, weight); } // --------------------------------------------------------------- Remove the edge from node u to node v. // Does not remove the nodes. // Does nothing if the edge does not exist. function removeEdge(u, v) { if (edges[u]) { edges[u] = edges[u].filter((_v) => _v !== v); } if (revEdges[v]) { revEdges[v] = revEdges[v].filter((_u) => _u !== u); } delete edgeWeights[encodeEdge(u, v)]; // Remove all parallel weights return graph; } // --------------------------------------------------------------- Contract the edge from node u to node v. // Incindent nodes directly connected to the edge nodes are connected to the new node. // Does nothing if the edge does not exist. function contractEdge(u, v, reducer = (weights) => Math.min(...weights)) { if (hasEdge(u, v) || hasEdge(v, u)) { removeEdge(u, v); removeEdge(v, u); // Ensure new contracted node has a unique name. let [uv, counter] = [`${u}-${v}`, 1]; const ns = nodes(); // Existing node names while (ns.includes(uv)) { uv = `${u}-${v}-${counter}`; counter++; } addNode(uv); const adjacentToU = new Set(adjacent(u)); const adjacentToV = new Set(adjacent(v)); for (const n of adjacentToU) { const w = getEdgeWeight(u, n); removeEdge(u, n); if (!adjacentToV.has(n)) { addEdge(uv, n, reducer([w])); } } for (const n of adjacentToV) { const w = getEdgeWeight(v, n); removeEdge(v, n); addEdge(uv, n, reducer([w])); } const inToU = new Set(inNodes(u)); const inToV = new Set(inNodes(v)); for (const n of inToU) { const w = getEdgeWeight(n, u); removeEdge(n, u); if (!inToV.has(n)) { addEdge(n, uv, reducer([w])); } } for (const n of inToV) { const w = getEdgeWeight(n, v); removeEdge(n, v); addEdge(n, uv, reducer([w])); } removeNode(u); removeNode(v); } return this; } // --------------------------------------------------------------- Is there an edge from node u to v? function hasEdge(u, v) { return adjacent(u).includes(v); } // --------------------------------------------------------------- Indegree for the given node. function indegree(node) { return (revEdges[node] ?? []).length; } // --------------------------------------------------------------- Outdegree for the given node. function outdegree(node) { return node in edges ? edges[node].length : 0; } // --------------------------------------------------------------- Depth-first search // If graph contains cycles, returns empty list. // Inspired by Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 604 // The additional option `includeSourceNodes` specifies whether to // include or exclude the source nodes from the result (true by default). // If `sourceNodes` is not specified, all nodes in the graph // are used as source nodes. function depthFirstSearch( sourceNodes, includeSourceNodes = true, errorOnCycle = false ) { try { if (!sourceNodes) { sourceNodes = nodes(); } if (typeof includeSourceNodes !== "boolean") { includeSourceNodes = true; } const visited = {}; const visiting = {}; const nodeList = []; function DFSVisit(node) { if (visiting[node] && errorOnCycle) { throw new CycleError( "Cycle found when trying to perform depth-first search" ); } if (!visited[node]) { visited[node] = true; visiting[node] = true; // temporary flag while visiting adjacent(node).forEach(DFSVisit); visiting[node] = false; nodeList.push(node); } } if (includeSourceNodes) { sourceNodes.forEach(DFSVisit); } else { sourceNodes.forEach(function (node) { visited[node] = true; }); sourceNodes.forEach(function (node) { adjacent(node).forEach(DFSVisit); }); } return nodeList; } catch (error) { console.log(error); return []; } } // --------------------------------------------------------------- Breadth-first search // Unlike a depth-first traversal, this can handle cyclic graphs. // Will traverse all connected nodes to the root one in breadth-first order. // Can be limited with an optional maximum distnace from the start node. function breadthFirstSearch(startNode, maxDistance = -1) { const visited = new Set([startNode]); const todo = new Queue().enqueue([startNode, 0]); const nodeList = []; while (todo.size > 0) { const [n0, depth] = todo.dequeue(); nodeList.push(n0); if (depth < maxDistance || maxDistance < 0) { adjacent(n0).forEach((n) => { if (!visited.has(n)) { visited.add(n); todo.enqueue([n, depth + 1]); } }); } } return nodeList; } // --------------------------------------------------------------- Does the graph have at least one cycle? // Note that if edges are undirected, graph is considered as having cycles. // For testing for tree topology with undirected edges, use isTree() instead. function hasCycle() { return depthFirstSearch(undefined, true, true).length === 0; } // --------------------------------------------------------------- Is the graph a tree? // As well as testing for non-retracing cycles, all nodes must be connected to be a tree. function isTree() { const visited = new Set(); const startNode = nodes()[0]; // Arbitrarily choose a start node function dfs(current, parent) { if (visited.has(current)) { return false; // Node was already visited, graph has a cycle } visited.add(current); for (const neighbour of adjacent(current)) { if (neighbour !== parent && !dfs(neighbour, current)) { return false; } } return true; } // Start DFS from the starting node, with no parent. if (!dfs(startNode, null)) { return false; // Graph has a cycle } // Check if the graph is connected by ensuring all nodes were visited return visited.size === nodes().length; } // --------------------------------------------------------------- Lowest common ancestors // Inspired by https://github.com/relaxedws/lca/blob/master/src/LowestCommonAncestor.php code // but uses depth search instead of breadth. Also uses some optimizations function lowestCommonAncestors(node1, node2) { const node1Ancestors = []; const lcas = []; function CA1Visit(visited, node) { if (!visited[node]) { visited[node] = true; node1Ancestors.push(node); if (node == node2) { lcas.push(node); return false; // found - shortcut } return adjacent(node).every((node) => { return CA1Visit(visited, node); }); } else { return true; } } function CA2Visit(visited, node) { if (!visited[node]) { visited[node] = true; if (node1Ancestors.indexOf(node) >= 0) { lcas.push(node); } else if (lcas.length == 0) { adjacent(node).forEach((node) => { CA2Visit(visited, node); }); } } } if (CA1Visit({}, node1)) { // No shortcut worked CA2Visit({}, node2); } return lcas; } // --------------------------------------------------------------- Topological sort. // The topological sort algorithm yields a list of visited nodes // such that for each visited edge (u, v), u comes before v in the list. // Amazingly, this comes from just reversing the result from depth-first search. // Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 613 function topologicalSort(sourceNodes, includeSourceNodes = true) { return depthFirstSearch(sourceNodes, includeSourceNodes, true).reverse(); } // --------------------------------------------------------------- All pairwise node distances // Uses Floyd-Warshall (https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm) function costMatrix() { const ns = nodes(); const costs = Object.create(null); for (const u of ns) { const row = Object.create(null); for (const v of ns) { row[v] = Infinity; } row[u] = 0; costs[u] = row; } for (const u of ns) { costs[u][u] = 0; for (const { to: v, weight: w } of outEdges(u)) { costs[u][v] = Math.min(costs[u][v], w); } } for (const k of ns) { for (const u of ns) { const uk = costs[u][k]; if (!Number.isFinite(uk)) { continue; } for (const v of ns) { const kv = costs[k][v]; if (!Number.isFinite(kv)) { continue; } const alt = uk + kv; if (alt < costs[u][v]) { costs[u][v] = alt; } } } } return costs; } // --------------------------------------------------------------- Betweenness of the graph. // Returns a [node,betweeenness] tuple for every node in the graph orderd // from most to least central. function betweenness() { const nodes = this.nodes(); const betweenness = new Map(nodes.map((node) => [node, 0])); for (const s of nodes) { const [stack, queue] = [[], [s]]; const predecessors = Object.fromEntries(nodes.map((w) => [w, []])); const sigma = Object.fromEntries(nodes.map((w) => [w, 0])); // Number of shortest paths from s->w const distance = Object.fromEntries(nodes.map((w) => [w, -1])); sigma[s] = 1; distance[s] = 0; let qh = 0; while (qh < queue.length) { const v = queue[qh++]; stack.push(v); for (const w of this.adjacent(v)) { if (distance[w] < 0) { queue.push(w); distance[w] = distance[v] + 1; } if (distance[w] == distance[v] + 1) { sigma[w] += sigma[v]; predecessors[w].push(v); } } } const dependency = Object.fromEntries(nodes.map((node) => [node, 0])); while (stack.length > 0) { const w = stack.pop(); for (const v of predecessors[w]) { dependency[v] += (sigma[v] / sigma[w]) * (1 + dependency[w]); } if (w != s) { betweenness.set(w, betweenness.get(w) + dependency[w]); } } } return Array.from(betweenness).sort((a, b) => b[1] - a[1]); } // --------------------------------------------------------------- Diameter of the graph. // Returns the longest shortest path between nodes as their // endpoint nodes and the given cost between them.along shortest path. function diameter() { const ns = nodes(); if (!ns.length) { return { diameter: 0, start: null, end: null, disconnected: false }; } const maxCostNode = (n0, reverseEdgeDir = false) => { let [maxCost, maxNode] = [-Infinity, null]; const traverse = reverseEdgeDir ? inNodes : adjacent; const dfs = (node, prev, prevCost) => { const currentCost = prevCost + (prev ? getEdgeWeight(prev, node) : 0); if (currentCost > maxCost) { maxCost = currentCost; maxNode = node; } for (const nextNode of traverse(node)) { if (nextNode !== prev) { dfs(nextNode, node, currentCost); } } }; dfs(n0, null, 0); return { node: maxNode, cost: maxCost }; }; if (isTree()) { const { node: n1 } = maxCostNode(ns[0]); const { node: n2, cost: diameterLength } = maxCostNode(n1, true); return { diameter: diameterLength, start: n2, end: n1, disconnected: false }; } const costs = costMatrix(); let best = -Infinity; let bestPair = { start: null, end: null }; let disconnected = false; for (const u of Object.keys(costs)) { for (const v of Object.keys(costs[u])) { if (u === v) { continue; } const c = costs[u][v]; if (!Number.isFinite(c)) { disconnected = true; continue; } if (c > best) { best = c; bestPair = { start: u, end: v }; } } } if (best === -Infinity) { // no reachable pairs (e.g. single node or all isolated) return { diameter: 0, start: null, end: null, disconnected }; } return { diameter: best, ...bestPair, disconnected }; } // --------------------------------------------------------------- Dijkstra's Shortest Path // Private Dijkstra, used by public API shortestPath, distancesFrom and distancesTo // direction: "out" traverses outEdges(u): u -> v // direction: "in" traverses inEdges(u): v -> u // Returns { dist: Map(node -> number), prev?: Object }. // If target is provided, stops early once target is settled. function dijkstraDistances(source, options = {}) { const { wFn = (d) => d, direction = "out", target = null, trackPrev = false } = options; const ns = nodes(); const has = new Set(ns); if (!has.has(source)) { return { dist: new Map() }; } const dist = new Map(ns.map((n) => [n, Infinity])); const prev = trackPrev ? Object.create(null) : null; // Binary min-heap of [dist, node] const heap = []; const push = (item) => { heap.push(item); for (let i = heap.length - 1; i > 0; ) { const parent = (i - 1) >> 1; if (heap[parent][0] <= heap[i][0]) { break; } [heap[parent], heap[i]] = [heap[i], heap[parent]]; i = parent; } }; const pop = () => { if (heap.length === 0) { return null; } const top = heap[0]; const last = heap.pop(); if (heap.length > 0) { heap[0] = last; for (let i = 0; ; ) { const l = i * 2 + 1; const r = l + 1; if (l >= heap.length) { break; } const j = r < heap.length && heap[r][0] < heap[l][0] ? r : l; if (heap[i][0] <= heap[j][0]) { break; } [heap[i], heap[j]] = [heap[j], heap[i]]; i = j; } } return top; }; // Cache transformed weights to avoid repeated wFn calls const wCache = new Map(); const weightOf = (u, v, wRaw) => { const k = `${u}|${v}|${wRaw}`; const cached = wCache.get(k); if (cached !== undefined) { return cached; } const w = wFn(wRaw); if (!Number.isFinite(w)) { throw new Error("wFn must return a finite number."); } if (w < 0) { throw new Error("Dijkstra requires non-negative edge weights."); } wCache.set(k, w); return w; }; dist.set(source, 0); push([0, source]); while (heap.length > 0) { const item = pop(); if (!item) { break; } const [du, u] = item; // stale entry if (du !== dist.get(u)) { continue; } if (target !== null && u === target) { break; } if (direction === "out") { for (const { to: v, weight: wRaw } of outEdges(u)) { const w = weightOf(u, v, wRaw); const alt = du + w; if (alt < dist.get(v)) { dist.set(v, alt); if (trackPrev) { prev[v] = u; } push([alt, v]); } } } else if (direction === "in") { for (const { from: v, weight: wRaw } of inEdges(u)) { const w = weightOf(v, u, wRaw); const alt = du + w; if (alt < dist.get(v)) { dist.set(v, alt); if (trackPrev) { prev[v] = u; } push([alt, v]); } } } else { throw new Error('direction must be "out" or "in".'); } } return trackPrev ? { dist, prev } : { dist }; } // --------------------------------------------------------------- Distances from a source to all nodes function distancesFrom(source, options = {}) { const { wFn = (d) => d } = options; return dijkstraDistances(source, { wFn, direction: "out" }).dist; } // --------------------------------------------------------------- Distances to a target from all nodes // (i.e. min cost v -> target for every v) function distancesTo(target, options = {}) { const { wFn = (d) => d } = options; return dijkstraDistances(target, { wFn, direction: "in" }).dist; } function shortestPath(source, destination, options = {}) { const { wFn = (d) => d } = options; const ns = nodes(); const has = new Set(ns); if (!has.has(source) || !has.has(destination)) { return []; } const { dist, prev } = dijkstraDistances(source, { wFn, direction: "out", target: destination, trackPrev: true }); const best = dist.get(destination); if (!Number.isFinite(best)) { return []; } // Reconstruct const path = []; for (let cur = destination; cur !== undefined; cur = prev[cur]) { path.push(cur); if (cur === source) { break; } } path.reverse(); path.weight = best; return path; } // --------------------------------------------------------------- Minimum Spanning Tree // Minimum spanning tree using Kruskal's algorithm // See https://en.wikipedia.org/wiki/Kruskal%27s_algorithm function mst() { // Create a disjoint-set data structure based on node index. const ns = nodes(); const ds = new DisjointSet(ns.length); const nodeIndices = Object.create(null); for (let i = 0; i < ns.length; i++) { nodeIndices[ns[i]] = i; } const mstGraph = new Graph(); mstGraph.setLookup(lu); // Provide list of edges sorted from lowest to highest weight. const edges = []; ns.forEach((n1, i) => { adjacent(n1).forEach((n2) => { if (nodeIndices[n1] < nodeIndices[n2]) { edges.push([nodeIndices[n1], nodeIndices[n2], minEdgeWeight(n1, n2)]); } }); }); edges.sort((e1, e2) => (e1[2] < e2[2] ? -1 : 1)); // Build MST from lowest weight edges upward, merging edge sets as we go. edges.forEach(([i1, i2, w]) => { const [s1, s2] = [ds.find(i1), ds.find(i2)]; if (s1 !== s2) { mstGraph.addUndirectedEdge(ns[i1], ns[i2], w); ds.union(s1, s2); } }); return mstGraph; } // --------------------------------------------------------------- Contract graph // Remove 'pass through' nodes aggregating the incoming and outgoing edge weights function contract(graph) { const g = new Graph(this.serialize()); // Clone to avoid mutating the original. let contractionMade; do { contractionMade = false; // Will repeatedly try to remove nodes until no more contractions possible g.nodes().forEach((n) => { const ns = g.distinctNeighbours(n); // Check if the node has exactly two neighbours if (ns.length === 2) { const [n1, n2] = ns; const contractBoth = // Can we contract in both directions? g.hasEdge(n1, n) && g.hasEdge(n, n1) && g.hasEdge(n, n2) && g.hasEdge(n2, n); const contractOne = // Can we contract in one direction? g.hasEdge(n1, n) && g.hasEdge(n, n2) && !(g.hasEdge(n2, n) || g.hasEdge(n, n1)); if (contractBoth || contractOne) { const w1 = g.getEdgeWeight(n1, n) + g.getEdgeWeight(n, n2); const w2 = contractBoth ? g.getEdgeWeight(n2, n) + g.getEdgeWeight(n, n1) : null; g.addEdge(n1, n2, w1); if (contractBoth) { g.addEdge(n2, n1, w2); } g.removeEdge(n1, n); g.removeEdge(n, n2); if (contractBoth) { g.removeEdge(n2, n); g.removeEdge(n, n1); } g.removeNode(n); contractionMade = true; } } }); } while (contractionMade); return g; } // --------------------------------------------------------------- Serializes the graph. function serialize() { const serialized = { nodes: nodes().map((id) => ({ id })), links: [] }; if (lu !== undefined) { serialized.lookup = JSON.stringify(lu); } for (const { id: source } of serialized.nodes) { const outs = typeof graph.outEdges === "function" ? graph.outEdges(source) : adjacent(source).map((target) => ({ to: target, weight: getEdgeWeight(source, target) })); for (const { to: target, weight } of outs) { serialized.links.push({ source, target, weight }); } } return serialized; } // --------------------------------------------------------------- Deserializes the given serialized graph. function deserialize(serialized) { serialized.nodes.forEach((node) => addNode(node.id)); serialized.links.forEach((link) => { addEdge(link.source, link.target, link.weight); }); if (serialized.lookup !== undefined) { setLookup(JSON.parse(serialized.lookup)); } return graph; } // --------------------------------------------------------------- Output graph as a graphViz dot. function toDot(options = {}) { const { showWeights = false, showEdges = true, showDirected = false, showTree = false, rankDir = "TB", nodeLabels = undefined, scale = 1, compact = false, extra = "", edgeAtts = null, // (e) => "color=red, penwidth=3" OR (e) => ({ color: "red", penwidth: 3 }) debug = false } = options; const compactSetting = compact ? `margin="0.05,0" width=0 height=0` : ""; const connector = showDirected ? " -> " : " -- "; const ser = serialize(); const isSafeId = (s) => /^[a-zA-Z_][\w.:-]*$/.test(s); const fmtVal = (v) => { if (typeof v === "number" || typeof v === "boolean") { return String(v); } const s = String(v); if ( (s.startsWith("<") && s.endsWith(">")) || (s.startsWith('"') && s.endsWith('"')) ) { return s; } return isSafeId(s) ? s : `"${s.replaceAll("\\", "\\\\").replaceAll('"', '\\"')}"`; }; const nLabels = nodeLabels ? ser.nodes .map((o) => o.id) .reduce( (s, n) => nodeLabels[n] === undefined ? s : s + `${fmtVal(n)} [label=${fmtVal(nodeLabels[n])}${ compactSetting ? ` ${compactSetting}` : "" }];`, "" ) : ""; const normWeight = (w) => { const v = w ?? 1; if (typeof v === "string") { const n = Number(v); if (Number.isFinite(n)) { return n; } } return v; }; const fmtAttrs = (spec) => { if (!spec) { return ""; } if (typeof spec === "string") { const t = spec.trim(); if (t.startsWith("[") && t.endsWith("]")) { return t.slice(1, -1).trim(); } return t; } if (typeof spec === "object") { return Object.entries(spec) .filter(([, v]) => v !== undefined && v !== null) .map(([k, v]) => `${k}=${fmtVal(v)}`) .join(", "); } return ""; }; const edgeAttrText = (e) => !edgeAtts ? "" : typeof edgeAtts === "function" ? fmtAttrs(edgeAtts(e)) : ""; const ns = nodes(); let edges; if (showTree) { const visited = new Set([ns[0]]); edges = []; breadthFirstSearch(ns[0]).forEach((n1) => adjacent(n1).forEach((n2) => { if (!visited.has(n2)) { edges.push({ source: n1, target: n2, weight: normWeight(getEdgeWeight(n1, n2)) }); visited.add(n2); } }) ); } else if (showDirected) { edges = ser.links.map((e) => ({ ...e, weight: normWeight(e.weight) })); } else { edges = [ ...ser.links.reduce((edges, link) => { const w = normWeight(link.weight); const linkAB = link.source + "§" + link.target + "§" + w; const linkBA = link.target + "§" + link.source + "§" + w; if (!edges.has(linkAB) && !edges.has(linkBA)) { edges.add(linkAB); } return edges; }, new Set()) ].map((s) => { const [src, tgt, w] = s.split("§"); return { source: src, target: tgt, weight: normWeight(w) }; }); } const eVis = showEdges === false ? " edge [style=invis]; " : ""; const displayCompact = compact === true ? `node [${compactSetting}]` : ``; // Separate self-loops as much as possible const loopPorts = ["e", "ne", "nw", "w", "sw", "se", "n", "s"]; const loopCount = new Map(); const edgeStmt = (e) => { const { source, target } = e; const weight = normWeight(e.weight); const extraAttrs = edgeAttrText({ source, target, weight }); const extraPart = extraAttrs ? `, ${extraAttrs}` : ""; if (source === target) { const i = loopCount.get(source) ?? 0; loopCount.set(source, i + 1); const port = loopPorts[i % loopPorts.length]; const ring = Math.floor(i / loopPorts.length); const dist = 2.6 + ring * 1.1; // push outward const minlen = 2 + ring; // outer rings bigger const p = `"${source}":${port}`; return `${p}${connector}${p}[${ showWeights ? `label="", headlabel="${weight}", labeldistance=${dist}, labelangle=0, labelfloat=true, minlen=${minlen}, constraint=false${extraPart}` : `labelfloat=true, minlen=${minlen}, constraint=false${extraPart}` }];`; } const attrs = [showWeights ? `label="${weight}"` : "", extraAttrs].filter( Boolean ); return `"${source}" ${connector} "${target}"${ attrs.length ? ` [${attrs.join(", ")}]` : "" }; `; }; const dotText = `${showDirected ? "digraph" : "graph"} { ${extra} rankdir=${rankDir}; ` + eVis + nLabels + displayCompact + edges.map(edgeStmt).join("") + `}`; const dotCmd = dot`${dotText}`; if (debug) { console.log("DOT: %s", dotText); } if (scale === undefined || scale === 1) { return dotCmd; } return md`

${dotCmd}

`; } // The returned graph instance. return graph; }