30:T530,## Constructing * **Graph()** : Create a new empty graph. * **Graph(_obj_)** Create a new graph from the given serialized object. See `serialize()` below for details of the object format. Nodes in the graph should be primitives such as strings or integers and should be unique. Each node therefore has a single identifier. To store multiple node attributes, create a separate data structure such as an array, object or Map linking node IDs to other arbitrary attributes and add them with `setLookup()`. Nodes can be added directly with **addNode(_n_)**, but more usefully added as edges: * **addEdge(_n1_, _n2_ _[,w]_)** Add a directed edge from node _n1_ to node _n2_ with an optional edge weight _w_ (defaults to _w_=1). If the nodes do not currently exist in the graph they are implicitly added. If either is already present they are connected to the edge. * **addUndirectedEdge(_n1_, _n2_ _[,w]_)** Adds an undirected edge between the two given nodes. In practice this adds two directed edges: _n1 -> n2_ and _n2 -> n1_. * **setLookup(_lu_)** Set the node lookup for this graph allowing each node ID to be associated with any arbitrary additional attributes. If node IDs are sequential integers, this can be an array with each index being a node ID. Or could be an object with keys as node IDs and values as attributes.31:T73e,## Query * **nodes(_byGroup_)** A list of graph nodes in insert order. If the optional `byGroup` parameter is `true` (default `false`), a list of node lists for each unconnected sub-graph is returned. * **getLookup()** The node lookup for this graph allowing multiple attributes per node to be queried. * **indegree(_n_)** The number of incoming edges connected to the given node. * **outdegree(_n_)** The number of outgoing edges connected to the given node. * **adjacent(_n_)** A list of all nodes directly connected to the given one via outgoing edges. A node can be listed more than once if it is connected by more then one edge. * **inNodes(_n_)** A list of all nodes directly connected to the given one via incoming edges. A node can be listed more than once if it is connected by more then one edge. * **inEdges(_n_)** Array of edges incoming to the given node _n_. Useful for multi-edges between a pair of nodes that each have possibly different weights. * **outEdges(_n_)** Array of edges outgoing from the given node _n_. Useful for multi-edges between a pair of nodes that each have possibly different weights. * **distinctNeighbours(_n_)** A list of all nodes directly connected to the given one whether via incoming or outgoing edges. Will exclude the given node itself even if it has a self-connected edge. * **hasEdge(_n1_,_n2_)** Reports whether or not there exists an edge from node _n1_ to node _n2_. * **getEdgeWeight(_n1_,_n2_)** Reports the weight of the edge from node _n1_ to node _n2_. * **getEdgeWeights(_n1_,_n2_)** Reports the list of weights corresponding to the edges from node _n1_ to _n2_. Useful for multi-edges between the same pair of nodes that have different weights. * **hasCycle()** Reports whether or not the graph contains any cycles. Note that by definition, undirected graphs with any edges always have cycles.32:Tc8c,## Traversal * **depthFirstSearch()** An ordered list of nodes in depth-first search order for an acyclic graph (i.e. from 'bottom' to root). If the graph contains cycles, including undirected edges, an empty list is returned and error message reported to the console. * **topologicalSort()** Report an ordered list of nodes in order of dependency on other nodes. i.e. the opposite order of the depth-first traversal, starting with the root. If the graph contains cycles, including undirected edges, an empty list is returned and error message reported to the console. * **breadthFirstSearch(_n_ _[, maxDistance]_)** Report an ordered list of nodes in breadth-first order from the given node _n_. Unlike depth first searching, this will work with cyclic graphs. Can optionally limit the search to a fixed distance from the start node, which can be useful for larger graphs. * **component(_n_ _[, strong]_)** Report the sub-graph ('component') this is connected to the given node _n_. If the optional _strong_ (default `false`) parameter is true, in a directed graph, only nodes directly traversable from _n_ will be included. If `false`, any edge that has a pathway to or from _n_ will be included. * **lowestCommonAncestors(_n1_, _n2_)** List of the [lowest common ancestors](https://en.wikipedia.org/wiki/Lowest_common_ancestor) of the given pair of nodes in a directed acyclic graph. * **shortestPath(_n1_, _n2_ _[, {options} ]_)** An array of nodes representing the shortest path between the two given nodes. Also includes a `weight` property storing the total cost (sum of edge weights) along that path. The option `wFn(w)` allows alternative weight (cost) values to be calculated from the edge weight `w`. * **diameter()** The 'longest shortest path' through the graph. Takes into account the weight of edges. Returns the two end nodes of the path and its total cost. To see the actual path, call `shortestPath()` between these two end nodes. * **betweenness()** The [betweenness centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) of every node in the graph. i.e. the proportion of shortest paths that travel through each node. Returns an array of `[node,score]` tuples ordered from most to least central. * **costMatrix()** An object of objects describing the sums of edge weights along the shortest path between all pairs of nodes. The key to each object is the node id, the value of the inner objects the cost of the shortest path between the pair of nodes. If traversal is not possible for a given pair of nodes, a large, but finite, cost is reported. Calculated with the [Floyd-Warshall algorithm](https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm). * **mst()** A new graph representing the [minimum spanning tree](https://en.wikipedia.org/wiki/Minimum_spanning_tree) joining all nodes in the graph. * **lineGraph(_optionsObject_)** Create a [line graph]() from the graph where edges become nodes and paris of adjacent edges become edges of the line graph. Options include `idFn:({ source, target, index })` for customising the line graph's node ids (default: _"source|target|index"_); `edgeWeight`:({source,target}) for customising the line graph's edge weights (default: _1_)33:Ta77,## Output * **serialize()** Produces a serialized object representing the graph in the form `{nodes: [], links[], lookup: lu}` where the `nodes` list is an array of objects each in the form `{id: x}` with `x` being each node's identifier; the `links` list is an array of objects each in the form `{source: n1, target: n2, weight: w}` where `n1` and `n2` are the ids of the nodes connected with the edge and `w` the edge weight; and the optional `lookup` value `lu` is a serialised version of the node lookup. This serialized form useful as input for [d3.simulation.nodes](https://github.com/d3/d3-force#simulation_nodes) and [d3.forceLinks](https://github.com/d3/d3-force#links) for force directed layouts. It can also be used to clone a graph with `g2 = Graph(g1.serialize())` * **toDot(_optionsObject_)** Produces a graphical representation of the graph using [GraphViz dot](https://graphviz.org) which can be displayed directly in Observable pages. Appearance can be customised with following object options: * * `showWeights: [true|false]` Determines whether or not edge weights are shown (default `false`). * `showDirected: [true|false]` Determines whether or not edge directions are symbolised (default `false`). * `showEdges: [true|false]` Determines whether or not edges are symbolised (default `true`). * `showTree: [true|false]` Determines whether or not an acyclic graph is shown as a tree (default `false`). * `rankDir: ["TB"|"BT"|"LR"|"RL"]` Determines the [layout](https://graphviz.org/docs/attrs/rankdir/) of the graph (top-to-bottom, left-to-right etc). Default `TB` (top-to-bottom). * `nodeLabels: obj` Customise node labels with an object of node IDs as keys and their respective labels as values. Defaults to using the node ID as label if not specified. * `scale: k` Set the zoom scale of the output (default 1), for example to halve the area of the output: `scale: 0.71` * `compact: [true|false]` Determines whether or not more compact labelling of nodes is used (default `false`). * `extra: [str]` Allow extra dot expression to be inserted in the spec for customisation, such as highlighting specific nodes. * `edgeLabel: fn` Customise edge label content with the given function in the form `fn(edge, label) => newLabel`. For example: `edgeLabel: (e,label) => e.source==="a" && e.target==="b" ? "my annotated label" : label` * `edgeAtts: fn` Customise appearance of selected edges with the given function in the form `fn({source, target, weight}) => {attributes}`. For example: `edgeAtts: ({ target }) => target === "goal" ? { color: "red" } : {}`34:T464,{ const lu = graph3.getLookup(); const r = new Renderer(600, 300) .fit([ [-1, -1], [11, 5] ]) .flipY() .textBaseline("middle") .textAlign("middle") .textSize(12); const drawNode = ([n, atts], r) => { // Draw edges from each node. r.stroke("lightgrey"); graph3.adjacent(n).forEach((n1) => r.line([ [lu[n].x, lu[n].y], [lu[n1].x, lu[n1].y] ]) ); // Draw node symbol. r.stroke() .fill("black") .ellipse(atts.x, atts.y, 0.15) .text(atts.name, atts.x + 0.15, atts.y + 0.3); return r; }; const drawShortestPath = (n1, n2) => { const path = graph3.shortestPath(n1, n2); r.strokeWidth(3); for (let i = 0; i < path.length - 1; i++) { r.line([ [lu[path[i]].x, lu[path[i]].y], [lu[path[i + 1]].x, lu[path[i + 1]].y] ]); } }; Object.entries(lu).forEach((entry) => drawNode(entry, r)); // Draw shortest path between any pair of nodes. r.stroke("steelblue"); drawShortestPath("h", "w"); r.stroke("brown"); drawShortestPath("w", "h"); return r.render(); }35:T453,function drawGeoGraph(g, options = {}) { const { w = 600, h = 400, topoOnly = false } = options; const pts = g.getLookup(); const topoPts = mst .contract() .nodes() .map((n) => [...pts[n], n]); const sp = g.shortestPath("0", `${pts.length - 1}`); const path = sp.map((i) => pts[Number(i)]); const [xMin, xMax] = d3.extent(pts, ([x, y]) => x); const [yMin, yMax] = d3.extent(pts, ([x, y]) => y); const r = new Renderer(w, h) .fit( [ [xMin, yMin], [xMax, yMax] ], w * 0.05 // 5% border ) .strokeWidth(0.2) .pointSize(3) .textSize(6); pts.forEach(([x, y], i) => g.adjacent(i).forEach((j) => (i < j ? r.line([pts[i], pts[j]]) : [])) ); (topoOnly ? topoPts : pts).forEach(([x, y], i) => g.adjacent(i).forEach((j) => r.points([[x, y]])) ); r.stroke().fill("black"); (topoOnly ? topoPts : pts).forEach(([x, y, n], i) => r.text(n ?? i, x, y)); r.fill("red") .textSize(12) .stroke() .text(d3.format(",.0f")(sp.weight), xMax, yMax - 10); return r.strokeWidth(2).stroke("red").line(path).render(); }36:Ta05b,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, lineGraph, 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; } // --------------------------------------------------------------- The line graph of g (edges as nodes). function lineGraph(options = {}) { const { idFn = ({ source, target, index }) => `${source}|${target}|${index}`, nodeData = (e) => e, edgeWeight = () => 1, setLookup = true } = options; const lg = new Graph(); const inByNode = new Map(); const outByNode = new Map(); const lookup = Object.create(null); const push = (map, key, value) => { if (!map.has(key)) { map.set(key, []); } map.get(key).push(value); }; let index = 0; for (const source of nodes()) { for (const { to: target, weight } of outEdges(source)) { const e = { source, target, weight, index }; const id = idFn(e); const edgeNode = { ...e, id }; lg.addNode(id); lookup[id] = nodeData(edgeNode); push(outByNode, source, edgeNode); push(inByNode, target, edgeNode); index++; } } for (const [via, ins] of inByNode) { const outs = outByNode.get(via) ?? []; for (const e of ins) { for (const f of outs) { lg.addEdge(e.id, f.id, edgeWeight({ from: e, to: f, via })); } } } if (setLookup) { lg.setLookup(lookup); } return lg; } // --------------------------------------------------------------- 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 }) edgeLabel = null, // (e, label) => label 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 fmtAttrs = (spec) => { if (!spec) { return ""; } if (typeof spec === "string") { const t = spec.trim(); return t.startsWith("[") && t.endsWith("]") ? t.slice(1, -1).trim() : t; } if (typeof spec === "object") { return Object.entries(spec) .filter(([, v]) => v !== undefined && v !== null) .map(([k, v]) => `${k}=${fmtVal(v)}`) .join(", "); } return ""; }; const normWeight = (w) => { const v = w ?? 1; if (typeof v === "string") { const n = Number(v); if (Number.isFinite(n)) { return n; } } return v; }; const edgeAttrText = (e) => typeof edgeAtts === "function" ? fmtAttrs(edgeAtts(e)) : fmtAttrs(edgeAtts); const edgeLabelText = (e) => { const base = showWeights ? String(e.weight) : ""; if (typeof edgeLabel !== "function") { return base; } const label = edgeLabel(e, base); return label == null ? "" : String(label); }; const attrList = (...attrs) => attrs.filter(Boolean).join(", "); const nLabels = nodeLabels ? ser.nodes .map((o) => o.id) .map((n) => { if (nodeLabels[n] === undefined) { return ""; } const attrs = attrList( `label=${fmtVal(nodeLabels[n])}`, compactSetting ); return `${fmtVal(n)} [${attrs}];`; }) .join("") : ""; 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((seen, link) => { const w = normWeight(link.weight); const linkAB = `${link.source}§${link.target}§${w}`; const linkBA = `${link.target}§${link.source}§${w}`; if (!seen.has(linkAB) && !seen.has(linkBA)) { seen.add(linkAB); } return seen; }, new Set()) ].map((s) => { const [source, target, weight] = s.split("§"); return { source, target, weight: normWeight(weight) }; }); } // Self-loop layout slots to push edge labels out from node while maintaing spacing const loopSlots = [ { port: "e", labelangle: 60 }, { port: "ne", labelangle: -60 }, { port: "n", labelangle: -30 }, { port: "nw", labelangle: -65 }, { port: "w", labelangle: -30 }, { port: "sw", labelangle: 10 }, { port: "s", labelangle: 30 }, { port: "se", labelangle: 60 } ]; // Distribute self-loops around the node so they are spaced out. const loopOrders = { 1: [0], 2: [0, 3], 3: [0, 3, 5], 4: [0, 2, 4, 6], 5: [0, 1, 3, 5, 7], 6: [0, 1, 3, 4, 5, 7], 7: [0, 1, 2, 3, 4, 5, 7], 8: [0, 1, 2, 3, 4, 5, 6, 7] }; const selfLoopTotals = edges.reduce((counts, { source, target }) => { if (source === target) { counts.set(source, (counts.get(source) ?? 0) + 1); } return counts; }, new Map()); const loopSeen = new Map(); const nextLoopSlot = (source) => { const i = loopSeen.get(source) ?? 0; loopSeen.set(source, i + 1); const total = selfLoopTotals.get(source) ?? 1; const ring = Math.floor(i / loopSlots.length); const j = i % loopSlots.length; const remaining = Math.min( total - ring * loopSlots.length, loopSlots.length ); const order = loopOrders[remaining] ?? loopOrders[8]; return { ...loopSlots[order[j]], ring }; }; const edgeStmt = (e) => { const { source, target } = e; const weight = normWeight(e.weight); const edge = { source, target, weight }; const label = edgeLabelText(edge); const extraAttrs = edgeAttrText(edge); if (source === target) { const { port, labelangle, ring } = nextLoopSlot(source); const p = `${fmtVal(source)}:${port}`; const attrs = attrList( `label=""`, label ? `headlabel=${fmtVal(label)}` : "", `labeldistance=${2.2 + ring * 1.1}`, `labelangle=${labelangle}`, `labelfloat=true`, `minlen=${2 + ring}`, `constraint=false`, extraAttrs ); return `${p}${connector}${p} [${attrs}];`; } const attrs = attrList(label ? `label=${fmtVal(label)}` : "", extraAttrs); return `${fmtVal(source)}${connector}${fmtVal(target)}${ attrs ? ` [${attrs}]` : "" };`; }; const eVis = showEdges === false ? " edge [style=invis]; " : ""; const displayCompact = compact ? `node [${compactSetting}];` : ""; 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); } return scale === undefined || scale === 1 ? dotCmd : md`

${dotCmd}

`; } // The returned graph instance for chaining. return graph; }37:Tf09,`Graph` is an extension of [Graph Data Structure](https://github.com/datavis-tech/graph-data-structure) from [Datavis Tech](https://github.com/datavis-tech). Amendments to the original: ### Data model and internal representation * **Different adjacency semantics:** `adjacent(node)` returns an array, rather than a `Set | undefined`. * **Multigraph support (parallel edges):** adjacency lists may contain duplicates, and edge weights are stored per edge instance (in insertion order), exposed via `getEdgeWeights(u, v)`. * **Reverse adjacency index:** maintains incoming adjacency to support efficient `inNodes(node)` and `indegree(node)`. ### Queries and traversal utilities * `inNodes(node)` for reporting the in-nodes for any given node. * **Incoming/outgoing edge enumeration:** `inEdges(node)` / `outEdges(node)` yield edge records including weights (and handle parallel edges deterministically). * **Node enumeration utilities:** `nodes([byGroup])` enumerates all nodes (including “target-only” nodes), with optional grouping by connectivity. * **Neighbour helpers:** `distinctNeighbours(node)` for unique neighbourhood queries. * **shortestPath()** has optional weight function for customisable traversal cost calculations. ### Connectivity and structure * `addUndirectedEdge(a, b [,w])` for adding undirected edges between two nodes with optional weight. * **Connectivity / components:** `component(startNode, {weak})` for subgraph extraction and `components({weak})` for component labelling/grouping. * **Structural predicates:** `hasCycle()` and `isTree()`. ### Additional graph algorithms * `breadthFirstSearch` for breadth-first traversal with optional depth limit. * `depthFirstSearch` for depth-first traversal. * `diameter()`. * `betweenness()` for finding the centrality of every node. * `costMatrix` for the cost (sum of edge weights) between every pair of nodes in the graph. * `mst()` for creating a minimum spanning tree. * `contract()` for removing degree-2 “corridor” nodes) * `contractEdge()` for merging two nodes into a new node, reconnecting incident edges. ### Lookup, serialization and visualization * **Lookup attachment:** `setLookup()` / `getLookup()` for node-associated attribute tables, preserved/propagated where relevant (e.g. `mst`, `component`, serialization). * **Serialization moved onto the instance and extended:** `serialize()` / `deserialize()` as methods (rather than standalone helpers) and optional lookup persistence. * [GraphViz dot](https://graphviz.org) output options to visualize the graph. Original code: [Graph Data Structure](https://github.com/datavis-tech/graph-data-structure) from [Datavis Tech](https://github.com/datavis-tech) with the following MIT licence: > The MIT License (MIT) > >Copyright (c) 2016 Curran Kelleher > >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.38:[] 2e:{"title":"GDS Graph","cells":[{"id":0,"value":"# GDS Graph\n\nA `Graph` package that extends [Graph Data Structure](https://github.com/datavis-tech/graph-data-structure) from [Datavis Tech](https://github.com/datavis-tech). Can represent cyclic and acyclic graphs, perform depth-first and breadth-first traversals, shortest path, topological sorting, indegree and outdegree measures, minimum spanning tree, cost matrix generation and graphical output via [GraphViz dot](https://graphviz.org).\n\nTo use:\n\n`import {Graph} from \"@jwolondon/gds-graph\"`\n\nHere's a minimal example:","pinned":false,"hidden":false,"mode":"md"},{"id":99,"value":"graph1 = Graph()\n .addEdge(\"a\", \"b\")\n .addEdge(\"a\", \"c\")\n .addEdge(\"b\", \"d\")\n .addEdge(\"b\", \"e\")\n .addEdge(\"b\", \"f\")\n .addEdge(\"c\", \"g\")\n .addEdge(\"e\", \"h\")\n .addEdge(\"e\", \"i\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":88,"value":"graph1.toDot({ showDirected: true })","pinned":true,"hidden":false,"mode":"ojs"},{"id":2200,"value":"And here's the same graph with some specific nodes and edges highlighted by customising the dot output:","pinned":false,"hidden":false,"mode":"md"},{"id":2159,"value":"graph1.toDot({\n showDirected: true,\n extra: `b [style=filled, fillcolor=cornSilk]; g [style=filled, fillcolor=cornSilk];`,\n edgeAtts: ({ source, target }) =>\n source === \"a\" || target == \"g\" ? { color: \"brown\" } : {}\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1382,"value":"$30","pinned":false,"hidden":false,"mode":"md"},{"id":1451,"value":"## Editing\n\n* **removeNode(_n_)** Remove the given node from the graph. If the node is connected to any others, all relevant edges are removed too.\n* **removeEdge(_n1_, _n2_)** Remove the edge from node _n1_ to _n2_ if it exists. This will only remove the edge, but leave the nodes in the graph. \n* **contractEdge(_n1_, _n2_)** Remove the edge from _n1_ to _n2_ if it exists while maintaining connections with all edges incident on the nodes removed.\n* **setEdgeWeight(_n1_, _n2_, _w_)** Set the weight of the edge from node _n1_ to _n2_ to the given value. This will store the weight associated with _n1->n2_ even if the edge has yet to be added. If the graph is undirected, it is safer to set the weights when adding edges (using the optional third _w_ parameter). Otherwise the edge weight needs to be set for both _n1->n2_ and _n2->n1_.\n* **contract()** Create a new graph where all 'pass-through' nodes have been removed, being replaced by an edge that connects the removed node's two neighbours.","pinned":false,"hidden":false,"mode":"md"},{"id":1391,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":1393,"value":"$32","pinned":false,"hidden":false,"mode":"md"},{"id":1395,"value":"$33","pinned":false,"hidden":false,"mode":"md"},{"id":1397,"value":"## Examples","pinned":false,"hidden":false,"mode":"md"},{"id":19,"value":"### 1. Directed Acyclic Graphs","pinned":false,"hidden":false,"mode":"md"},{"id":1413,"value":"graph1.toDot({ showDirected: true })","pinned":true,"hidden":false,"mode":"ojs"},{"id":2157,"value":"graph1.serialize()","pinned":true,"hidden":false,"mode":"ojs"},{"id":121,"value":"We can query the set of nodes in the graph which will return all nodes in insert order.","pinned":false,"hidden":false,"mode":"md"},{"id":652,"value":"graph1.nodes()","pinned":true,"hidden":false,"mode":"ojs"},{"id":112,"value":"Depth-first node traversal order:","pinned":false,"hidden":false,"mode":"md"},{"id":108,"value":"graph1.depthFirstSearch()","pinned":true,"hidden":false,"mode":"ojs"},{"id":116,"value":"which is the opposite traversal of a topological order:","pinned":false,"hidden":false,"mode":"md"},{"id":118,"value":"graph1.topologicalSort()","pinned":true,"hidden":false,"mode":"ojs"},{"id":449,"value":"A breadth-first traversal:","pinned":false,"hidden":false,"mode":"md"},{"id":451,"value":"graph1.breadthFirstSearch(\"a\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":548,"value":"For large or deep graphs we may wish to limit the depth of the traversal:","pinned":false,"hidden":false,"mode":"md"},{"id":550,"value":"graph1.breadthFirstSearch(\"a\", 2)","pinned":true,"hidden":false,"mode":"ojs"},{"id":659,"value":"To retrieve the edges, serialise the graph and extract the edges from the serialised object:","pinned":false,"hidden":false,"mode":"md"},{"id":656,"value":"graph1.serialize().links.map((obj) => [obj.source, obj.target, obj.weight])","pinned":true,"hidden":false,"mode":"ojs"},{"id":649,"value":"For any node we can find its children with O(1) efficiency:","pinned":false,"hidden":false,"mode":"md"},{"id":123,"value":"graph1.adjacent(\"b\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":153,"value":"We can also query incoming nodes with an linear efficiency of O(E) where E is the number of edges:","pinned":false,"hidden":false,"mode":"md"},{"id":145,"value":"graph1.inNodes(\"e\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":157,"value":"What is the distance from one node to another? If there is a path, this returns the nodes along the shortest path and the sum of the weights of that path traversal.","pinned":false,"hidden":false,"mode":"md"},{"id":159,"value":"graph1.shortestPath(\"a\", \"i\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1882,"value":"What is the longest path? If we don't backtrack or visit any node more than once, it is along one of the graph's _diameters_, which in the case of a tree will be the distance from root to the deepest node in a depth-first search:","pinned":false,"hidden":false,"mode":"md"},{"id":1880,"value":"graph1.diameter()","pinned":true,"hidden":false,"mode":"ojs"},{"id":1485,"value":"To provide a custom view of the graph:","pinned":false,"hidden":false,"mode":"md"},{"id":593,"value":"{\n const labels = {\n a: \"Root\",\n d: \"d (leaf)\",\n f: \"f (leaf)\",\n g: \"g (leaf)\",\n h: \"h (leaf)\",\n i: \"i (leaf)\"\n };\n return graph1.toDot({\n showDirected: true,\n rankDir: \"BT\",\n nodeLabels: labels\n });\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":66,"value":"### 2. Undirected cyclic graph","pinned":false,"hidden":false,"mode":"md"},{"id":25,"value":"graph2.toDot({ showWeights: true, rankDir: \"LR\" })","pinned":false,"hidden":false,"mode":"ojs"},{"id":70,"value":"graph2 = Graph()\n .addUndirectedEdge(\"a\", \"b\", 7)\n .addUndirectedEdge(\"a\", \"c\", 9)\n .addUndirectedEdge(\"a\", \"f\", 14)\n .addUndirectedEdge(\"b\", \"c\", 10)\n .addUndirectedEdge(\"b\", \"d\", 15)\n .addUndirectedEdge(\"c\", \"d\", 11)\n .addUndirectedEdge(\"c\", \"f\", 2)\n .addUndirectedEdge(\"d\", \"e\", 6)\n .addUndirectedEdge(\"e\", \"f\", 9)\n .addUndirectedEdge(\"e\", \"e\", 5)","pinned":true,"hidden":false,"mode":"ojs"},{"id":501,"value":"graph2.breadthFirstSearch(\"a\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1685,"value":"A minimum spanning tree:","pinned":false,"hidden":false,"mode":"md"},{"id":1687,"value":"graph2.mst().toDot({ rankDir: \"LR\" })","pinned":true,"hidden":false,"mode":"ojs"},{"id":665,"value":"Minimum cost (sum of weights) of traversing between every pair of nodes in the graph:","pinned":false,"hidden":false,"mode":"md"},{"id":667,"value":"graph2.costMatrix()","pinned":true,"hidden":false,"mode":"ojs"},{"id":690,"value":"By default, when querying edge weights on a per-node basis (`getEdgeWeight()`), all edge weights are 1. Even a query of an edge weight between nodes not directly connected will be 1. To prevent this, test to see if an edge exists first before querying the weight:","pinned":false,"hidden":false,"mode":"md"},{"id":684,"value":"{\n const ew = (n1, n2) =>\n graph2.hasEdge(n1, n2)\n ? `Weight from ${n1} to ${n2} is ${graph2.getEdgeWeight(n1, n2)}`\n : `No edge from ${n1} to ${n2}`;\n return [ew(\"a\", \"b\"), ew(\"a\", \"d\"), ew(\"b\", \"b\"), ew(\"e\", \"e\")];\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":242,"value":"Adjacent nodes to `c`:","pinned":false,"hidden":false,"mode":"md"},{"id":244,"value":"graph2.adjacent(\"c\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":254,"value":"Shortest path from `e` to `a` along with its total cost of traversal.","pinned":false,"hidden":false,"mode":"md"},{"id":256,"value":"graph2.shortestPath(\"e\", \"a\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1774,"value":"The diameter is the longest shortest path between any pair of nodes in the graph with the highest traversal cost:","pinned":false,"hidden":false,"mode":"md"},{"id":1776,"value":"{\n const { start, end } = graph2.diameter();\n return graph2.shortestPath(start, end);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":265,"value":"### 3. Directed Cyclic Graph with multi-attribute nodes\n\nHere we create a lookup object for the node IDs containing each node's attributes.","pinned":false,"hidden":false,"mode":"md"},{"id":270,"value":"graph3.toDot({\n showWeights: true,\n showDirected: true,\n rankDir: \"LR\",\n nodeLabels: objectMap(graph3.getLookup(), (o) => o.name)\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1534,"value":"function objectMap(obj, fn) {\n return Object.fromEntries(\n Object.entries(obj).map(([k, v], i) => [k, fn(v, k, i)])\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":267,"value":"graph3 = Graph()\n .addEdge(\"h\", \"c\", 5)\n .addEdge(\"a\", \"h\", 3)\n .addUndirectedEdge(\"b\", \"h\", 2)\n .addUndirectedEdge(\"b\", \"d\", 1)\n .addUndirectedEdge(\"b\", \"e\", 6)\n .addEdge(\"c\", \"e\", 2)\n .addEdge(\"d\", \"a\", 3)\n .addEdge(\"e\", \"f\", 1)\n .addEdge(\"e\", \"w\", 4)\n .addEdge(\"f\", \"d\", 4)\n .addEdge(\"w\", \"f\", 1)\n .setLookup({\n h: { x: 1, y: 4, name: \"Home\" },\n a: { x: 0, y: 1, name: \"A\" },\n b: { x: 1, y: 2, name: \"B\" },\n c: { x: 3, y: 4, name: \"C\" },\n d: { x: 3, y: 0, name: \"D\" },\n e: { x: 4, y: 3, name: \"E\" },\n f: { x: 6, y: 2, name: \"F\" },\n w: { x: 9, y: 3, name: \"Work\" }\n })","pinned":true,"hidden":false,"mode":"ojs"},{"id":555,"value":"A breadth-first traversal order respecting edge directions and querying the nodes object to extract node names.","pinned":false,"hidden":false,"mode":"md"},{"id":507,"value":"graph3.breadthFirstSearch(\"w\").map((n) => graph3.getLookup()[n].name)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1912,"value":"The path along the diameter of the graph:","pinned":false,"hidden":false,"mode":"md"},{"id":1914,"value":"{\n const { start, end } = graph3.diameter();\n return graph3.shortestPath(start, end).map((n) => graph3.getLookup()[n].name);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":2056,"value":"The betweenness of each node in the graph, identifying that `b` is the most central (removing it significantly alters the shortest paths between other nodes in the graph), while `work` is the least central (removing it has no effect on shortest paths between other pairs of nodes.)","pinned":false,"hidden":false,"mode":"md"},{"id":2052,"value":"graph3.betweenness()","pinned":true,"hidden":false,"mode":"ojs"},{"id":681,"value":"For directed graphs, the cost matrix may not be symmetrical:","pinned":false,"hidden":false,"mode":"md"},{"id":677,"value":"graph3.costMatrix()","pinned":true,"hidden":false,"mode":"ojs"},{"id":406,"value":"We can draw the network by extracting the position coordinates of each node and finding the path of the shortest distances from home to work (blue) and from work to home (red).","pinned":false,"hidden":false,"mode":"md"},{"id":331,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":1962,"value":"### 4. Unconnected Graphs\n\nNot all nodes are necessarily connected in a graph (e.g. a forest of trees). Therefore there is no guarantee when traversing from nodes in such graphs that they will visit all others. ","pinned":false,"hidden":false,"mode":"md"},{"id":1963,"value":"graph4 = new Graph()\n .addEdge(\"a\", \"b\", 1)\n .addEdge(\"b\", \"c\", 2)\n .addEdge(\"c\", \"a\", 3)\n\n .addEdge(\"d\", \"e\", 4)\n .addEdge(\"d\", \"f\", 5)\n .addEdge(\"d\", \"g\", 6)\n .addEdge(\"f\", \"h\", 7)\n .addEdge(\"f\", \"i\", 8)\n\n .addEdge(\"k\", \"k\", 9)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1968,"value":"graph4.toDot({ showDirected: true, showWeights: true })","pinned":false,"hidden":false,"mode":"ojs"},{"id":1971,"value":"Calling `nodes()` with the `byGroup` parameter set to `true` will return a list of node lists for each set of connected nodes. For example,","pinned":false,"hidden":false,"mode":"md"},{"id":1972,"value":"graph4.nodes(true)","pinned":true,"hidden":false,"mode":"ojs"},{"id":2586,"value":"### 5. Line Graphs\n\nA line graph ${tex`(G)`} is the transformation of a graph ${tex`G`} such that edges in ${tex`G`} become nodes in ${tex`L(G)`}. And the edges of ${tex`L(G)`} represent pairs of connected edges in ${tex`G`}. For example, suppose we had a simple graph ${tex`g1`}: ","pinned":false,"hidden":false,"mode":"md"},{"id":2591,"value":"g1 = new Graph()\n .addEdge(\"a\", \"b\", 1)\n .addEdge(\"a\", \"c\", 2)\n .addEdge(\"c\", \"d\", 3)\n .addEdge(\"d\", \"b\", 4)\n .addEdge(\"b\", \"b\", 5)","pinned":true,"hidden":false,"mode":"ojs"},{"id":2593,"value":"g1.toDot({ showDirected: true, showWeights: true, rankDir: \"LR\" })","pinned":false,"hidden":false,"mode":"ojs"},{"id":2604,"value":"Its line graph would be:","pinned":false,"hidden":false,"mode":"md"},{"id":2606,"value":"g1\n .lineGraph({ idFn: ({ source, target }) => `${source}${target}` })\n .toDot({ showDirected: true, rankDir: \"LR\" })","pinned":true,"hidden":false,"mode":"ojs"},{"id":2612,"value":"By default, calling `.lineGraph` will allocate an edge weight of 1 to all the line graph's edges. But we could instead concatenate the original edge weights by proving a custom edge function:","pinned":false,"hidden":false,"mode":"md"},{"id":2614,"value":"g1\n .lineGraph({\n idFn: ({ source, target }) => `${source}${target}`,\n edgeWeight: ({ from, to }) => `${from.weight}${to.weight}`\n })\n .toDot({ showDirected: true, rankDir: \"LR\", showWeights: true })","pinned":true,"hidden":false,"mode":"ojs"},{"id":703,"value":"### 6. Spatially Embedded Graphs\n\nThis is just a special case of a graph with multi-attribute nodes, where each node has its spatial location stored as attributes. Commonly we might weight edges as some measure of distance between nodes.","pinned":false,"hidden":false,"mode":"md"},{"id":853,"value":"To illustrate various spatially embedded graphs we will start with a list of randomly positioned points on a plane, sorted by distance from the origin (which will allow us later to select points that we know are far apart).","pinned":false,"hidden":false,"mode":"md"},{"id":859,"value":"pts = Array(100)\n .fill(0)\n .map((_, i) => [\n Math.round(Math.random() * 10000),\n Math.round(Math.random() * 10000)\n ])\n .sort(([x1, y1], [x2, y2]) =>\n x1 * x1 + y1 * y1 < x2 * x2 + y2 * y2 ? -1 : 1\n )","pinned":false,"hidden":false,"mode":"ojs"},{"id":976,"value":"And to help with visualising the various spatially embedded graphs, let's also create a function for drawing spatially embedded graphs. The ID of each node will be its index position in the lookup array of points. We will superimpose the shortest path between the first and last sorted point in the list along with an indication of its length.","pinned":false,"hidden":false,"mode":"md"},{"id":808,"value":"$35","pinned":true,"hidden":false,"mode":"ojs"},{"id":946,"value":"#### 6.1 Delaunay Triangulation\n\nThe Delaunay Triangulation of a set of points is conveniently calculated using [d3.Delaunay](https://github.com/d3/d3-delaunay).","pinned":false,"hidden":false,"mode":"md"},{"id":863,"value":"delaunay = d3.Delaunay.from(pts)","pinned":false,"hidden":false,"mode":"ojs"},{"id":870,"value":"Storing the Delaunay triangulation as a GDS graph simply involves adding an edge for each point's Delaunay neighbours giving the edge weight as the Euclidean distance between the pair of connected points. \n\nAdditionally, we can show the shortest path (in red) between two points in the graph (selected as nearest and furthest to/from the top-left), which acts as a useful comparison when constructing different spatially embedded graphs.","pinned":false,"hidden":false,"mode":"md"},{"id":707,"value":"{\n const graph = Graph();\n graph.setLookup(pts);\n pts.forEach((_, i) =>\n [...delaunay.neighbors(i)].forEach((j) =>\n graph.addEdge(\n `${i}`,\n `${j}`,\n Math.hypot(pts[i][0] - pts[j][0], pts[i][1] - pts[j][1])\n )\n )\n );\n return drawGeoGraph(graph);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":805,"value":"#### 6.2 Gabriel Graph\nThe [Gabriel graph](https://en.wikipedia.org/wiki/Gabriel_graph) of a set of points is a sub-graph of the Delaunay triangulation such that a disc with a diameter as an edge in the graph contains only the two nodes joined by that edge. We can construct Gabriel Graph by only adding Delaunay edges between nodes that are the closest ones to their midpoint.","pinned":false,"hidden":false,"mode":"md"},{"id":924,"value":"gabriel = {\n const dist = (a, b) => Math.hypot(a[0] - b[0], a[1] - b[1]);\n const mid = (a, b) => [(a[0] + b[0]) / 2, (a[1] + b[1]) / 2];\n const gg = Graph();\n gg.setLookup(pts);\n pts.forEach((_, i) =>\n [...delaunay.neighbors(i)].forEach((j) => {\n if (delaunay.find(...mid(pts[i], pts[j]), i) === i) {\n gg.addEdge(`${i}`, `${j}`, dist(pts[i], pts[j]));\n }\n })\n );\n return gg;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":872,"value":"drawGeoGraph(gabriel)","pinned":false,"hidden":false,"mode":"ojs"},{"id":934,"value":"#### 6.3 Relative Neighbourhood Graph\n\nThe [Relative Neighbourhood Graph (RNG)](https://en.wikipedia.org/wiki/Relative_neighborhood_graph) is a further sub-graph of the Gabriel Graph that connects points such that there are no points nearer to both connected points than the connected points are to each other.\n\nWhile not the most efficient algorithm, we can construct the RNG from the Gabriel Graph by filtering only edges of a length that is at shorter or the same length as the distance of all other nodes directly adjacent to both edge nodes (we could also do the same from the Delaunay triangulation but since the Gabriel graph has already removed some edges we know will never be in the RNG, there is no need).","pinned":false,"hidden":false,"mode":"md"},{"id":938,"value":"rng = {\n const dSq = (a, b) =>\n (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);\n const rnGraph = new Graph();\n rnGraph.setLookup(pts);\n\n gabriel.nodes().forEach((n1) => {\n const nodes = gabriel.adjacent(n1);\n gabriel.adjacent(n1).forEach((n2) => {\n const dEdge = dSq(pts[n1], pts[n2]);\n nodes.concat(gabriel.adjacent(n2));\n if (\n nodes\n .map((n) => Math.max(dSq(pts[n], pts[n1]), dSq(pts[n], pts[n2])))\n .filter((d) => d < dEdge).length === 0\n ) {\n rnGraph.addEdge(n1, n2, gabriel.getEdgeWeight(n1, n2));\n }\n });\n });\n return rnGraph;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":940,"value":"drawGeoGraph(rng)","pinned":false,"hidden":false,"mode":"ojs"},{"id":922,"value":"#### 6.4. Euclidean Minimum Spanning Tree\n\nThe [Euclidean minimum spanning tree](https://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree) will connect all nodes such that the total length of edges is minimised. It can be proved that a Euclidean MST will always be a subgraph of the relative neighbourhood graph, so we can calculate directly from the RNG via a call to `mst()` (although it would also work applied to the Gabriel graph or Delaunay Triangulation, albeit with more calculations).","pinned":false,"hidden":false,"mode":"md"},{"id":1212,"value":"mst = rng.mst()","pinned":true,"hidden":false,"mode":"ojs"},{"id":956,"value":"drawGeoGraph(mst)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1327,"value":"The MST as a tree without regard to spatial position:","pinned":false,"hidden":false,"mode":"md"},{"id":1209,"value":"mst.toDot({ rankDir: \"LR\", showTree: true, compact: true })","pinned":false,"hidden":false,"mode":"ojs"},{"id":2025,"value":"We can see the topology of the MST more clearly if we _contract_ it by removing any 'pass-through' nodes, leaving just leaf and junction nodes.","pinned":false,"hidden":false,"mode":"md"},{"id":2019,"value":"mst.contract().toDot({ rankDir: \"LR\", showTree: true, compact: true })","pinned":false,"hidden":false,"mode":"ojs"},{"id":2364,"value":"Embedding the simplified graph back in the spatial domain, we can map the topology of the MST:","pinned":false,"hidden":false,"mode":"md"},{"id":2333,"value":"drawGeoGraph(mst, { topoOnly: true })","pinned":false,"hidden":false,"mode":"ojs"},{"id":15,"value":"---\n\n### Appendix","pinned":false,"hidden":false,"mode":"md"},{"id":7,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":10,"value":"class CycleError extends Error {\n constructor(message) {\n super(message);\n Object.setPrototypeOf(this, CycleError.prototype);\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":327,"value":"import { Renderer } from \"@jwolondon/renderer\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":437,"value":"$37","pinned":false,"hidden":false,"mode":"md"}],"files":"$W38","stdlib":"1","titling":"auto"}