2b:null 2c:["$","title",null,{"children":"GDS Graph | linard-y | Observable"}] 31: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.32:T540,## 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. * **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_. * **hasCycle()** Reports whether or not the graph contains any cycles. Note that by definition, undirected graphs with any edges always have cycles.33:T954,## 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. * **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_)** 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. * **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.34:T7e9,## 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`).35: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(); }36:T6bf3,function Graph(serialized) { // List of 'public' methods (returned with the Graph instance) const graph = { setLookup, getLookup, addNode, removeNode, nodes, adjacent, inNodes, distinctNeighbours, addEdge, addUndirectedEdge, removeEdge, hasEdge, setEdgeWeight, getEdgeWeight, indegree, outdegree, depthFirstSearch, breadthFirstSearch, hasCycle, isTree, lowestCommonAncestors, topologicalSort, 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 = {}; // The weights of edges. Keys are string encodings of edges. Values are weights (numbers). const edgeWeights = {}; // Optional lookup data structure for relating node ids to other attributes. const lookup = {}; // 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(lu) { lookup.lu = lu; return graph; } // --------------------------------------------------------------- Get the lookup data structure function getLookup() { return lookup.lu; } // --------------------------------------------------------------- Add a node to the graph. // If node was already added, this function does nothing. // If node was not already added, this function sets up an empty adjacency list. function addNode(node) { edges[node] = adjacent(node); return graph; } // --------------------------------------------------------------- Remove a node from the graph. // Also removes incoming and outgoing edges. function removeNode(node) { // Remove incoming edges. Object.keys(edges).forEach(function (u) { edges[u].forEach(function (v) { if (v === node) { removeEdge(u, v); } }); }); // Remove outgoing edges (and signal that the node no longer exists). delete edges[node]; return graph; } // --------------------------------------------------------------- Report nodes that have been 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; } // --------------------------------------------------------------- What are the outgoing nodes adjacent to the given node. // Returns an empty array for unknown nodes. function adjacent(node) { return edges[node] || []; } // --------------------------------------------------------------- What are the incoming nodes? // Not very efficient, costs O(E) where E = number of edges. function inNodes(node) { let ns = []; Object.keys(edges).forEach(function (u) { edges[u].forEach(function (v) { if (v === node) { ns.push(u); } }); }); return ns; } // --------------------------------------------------------------- Distinct neighbouring nodes. function distinctNeighbours(node) { const ns = new Set(inNodes(node).concat(adjacent(node))); ns.delete(node); return [...ns]; } // --------------------------------------------------------------- Set the weight of the given edge. function setEdgeWeight(u, v, weight) { edgeWeights[encodeEdge(u, v)] = weight; return graph; } // --------------------------------------------------------------- Report weight of the given edge. // Returns 1 if no weight was previously set. function getEdgeWeight(u, v) { const weight = edgeWeights[encodeEdge(u, v)]; return weight === undefined ? 1 : weight; } // --------------------------------------------------------------- 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); adjacent(u).push(v); if (weight !== undefined) { setEdgeWeight(u, v, weight); } return graph; } // --------------------------------------------------------------- Add an undirected edge between nodes 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] = adjacent(u).filter(function (_v) { return _v !== v; }); } return graph; } // --------------------------------------------------------------- Is there an edge from node u to v? function hasEdge(u, v) { return adjacent(u).includes(v); } // --------------------------------------------------------------- Indegree for the given node. // Not very efficient, costs O(E) where E = number of edges. function indegree(node) { let degree = 0; function check(v) { if (v === node) { degree++; } } Object.keys(edges).forEach(function (u) { edges[u].forEach(check); }); return degree; } // --------------------------------------------------------------- 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 = ns.reduce( (acc, u) => ({ ...acc, [u]: ns.reduce((acc, v) => ({ ...acc, [v]: Number.MAX_VALUE }), {}) }), {} ); ns.forEach((u) => { costs[u][u] = 0; adjacent(u).forEach((v) => { costs[u][v] = getEdgeWeight(u, v); // costs[v][u] = getEdgeWeight(v, u); }); }); ns.forEach((k) => { ns.forEach((u) => { ns.forEach((v) => { costs[u][v] = Math.min(costs[u][v], costs[u][k] + costs[k][v]); }); }); }); 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; while (queue.length > 0) { const v = queue.shift(); 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() { if (!nodes().length) { return { diameter: 0, start: null, end: null }; } // For directed edge trees, the 2-DFS approach for finding diameter will need to traverse // back up the tree on second pass so we need to be able to reverse edge directions on this second pass. const maxCostNode = (n0, reverseEdgeDir = false) => { let maxCost = -Infinity; let maxNode = null; const traverse = reverseEdgeDir ? inNodes : adjacent; const dfs = (node, prev, prevCost) => { const currentCost = prevCost + (prev ? getEdgeWeight(prev, node) : 0); // add edge weight only if there's a previous node if (currentCost > maxCost) { maxCost = currentCost; maxNode = node; } traverse(node).forEach((nextNode) => { if (nextNode !== prev) { dfs(nextNode, node, currentCost); } }); }; dfs(n0, null, 0); return { node: maxNode, cost: maxCost }; }; if (isTree()) { // For trees find furthest node from root, then find furthest from that node. const { node: n1 } = maxCostNode(nodes()[0]); // Arbitrary starting node const { node: n2, cost: diameterLength } = maxCostNode(n1, true); return { diameter: diameterLength, start: n2, end: n1 }; // For directed edges, need to start at n2 } // For graphs with cycles, compute entire cost matrix const costs = costMatrix(); let diameter = 0; let nodePair = { start: null, end: null }; for (let u of Object.keys(costs)) { for (let v of Object.keys(costs[u])) { if (u !== v && costs[u][v] > diameter) { diameter = costs[u][v]; nodePair = { start: u, end: v }; } } } return { diameter: diameter, ...nodePair }; } // --------------------------------------------------------------- Dijkstra's Shortest Path // Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 658 // Variable and function names correspond to names in the book. function shortestPath(source, destination) { try { // Upper bounds for shortest path weights from source. const d = {}; // Predecessors. const p = {}; // Poor man's priority queue, keyed on d. let q = {}; function initializeSingleSource() { nodes().forEach(function (node) { d[node] = Infinity; }); if (d[source] !== Infinity) { throw new Error( "Source node not found when trying to calculate shortest path" ); } if (d[destination] !== Infinity) { throw new Error( "Destination node not found when trying to calculate shortest path" ); } d[source] = 0; } // Adds entries in q for all nodes. function initializePriorityQueue() { nodes().forEach(function (node) { q[node] = true; }); } // Returns true if q is empty. function priorityQueueEmpty() { return Object.keys(q).length === 0; } // Linear search to extract (find and remove) min from q. function extractMin() { let min = Infinity; let minNode; Object.keys(q).forEach(function (node) { if (d[node] < min) { min = d[node]; minNode = node; } }); if (minNode === undefined) { // If we reach here, there's a disconnected subgraph, and we're done. q = {}; return null; } delete q[minNode]; return minNode; } function relax(u, v) { const w = getEdgeWeight(u, v); if (d[v] > d[u] + w) { d[v] = d[u] + w; p[v] = u; } } function dijkstra() { initializeSingleSource(); initializePriorityQueue(); while (!priorityQueueEmpty()) { const u = extractMin(); if (u === null) return; adjacent(u).forEach(function (v) { relax(u, v); }); } } // Assembles the shortest path by traversing the // predecessor subgraph from destination to source. function path() { const nodeList = []; let weight = 0; let node = destination; while (p[node]) { nodeList.push(node); weight += getEdgeWeight(p[node], node); node = p[node]; } if (node !== source) { throw new Error("No path found when searching for shortest path"); } nodeList.push(node); nodeList.reverse(); nodeList.weight = weight; return nodeList; } dijkstra(); return path(); } catch (error) { console.warn(error); return []; } } // --------------------------------------------------------------- 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 ds = new DisjointSet(nodes().length); const nodeIndices = {}; nodes().forEach((n1, i) => { nodeIndices[n1] = i; }); const mstGraph = new Graph(); mstGraph.setLookup(lookup.lu); // Provide list of edges sorted from lowest to highest weight. const edges = []; nodes().forEach((n1, i) => { adjacent(n1).forEach((n2) => { if (nodeIndices[n1] < nodeIndices[n2]) { edges.push([nodeIndices[n1], nodeIndices[n2], getEdgeWeight(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(nodes()[i1], nodes()[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: id })), links: [] }; if (lookup.lu !== undefined) { serialized.lookup = JSON.stringify(lookup.lu); } serialized.nodes.forEach((node) => { const source = node.id; adjacent(source).forEach((target) => { serialized.links.push({ source: source, target: target, weight: getEdgeWeight(source, target) }); }); }); 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 visualization. function toDot(options) { const defaults = { showWeights: false, showEdges: true, showDirected: false, showTree: false, rankDir: "TB", nodeLabels: undefined, scale: 1, compact: false }; options = Object.assign({}, defaults, options); const compactSetting = options.compact ? `margin="0.05,0" width=0 height=0` : ""; const connector = options.showDirected ? " -> " : " -- "; const nLabels = options.nodeLabels ? serialize() .nodes.map((o) => o.id) .reduce( (nodeLabels, n) => options.nodeLabels[n] === undefined ? nodeLabels : nodeLabels + `${n} [label="${options.nodeLabels[n]}" ${compactSetting}];`, "" ) : ""; let edges; if (options.showTree) { const visited = new Set([nodes()[0]]); edges = []; breadthFirstSearch(nodes()[0]).forEach((n1) => adjacent(n1).forEach((n2) => { if (!visited.has(n2)) { edges.push({ source: n1, target: n2, weight: getEdgeWeight(n1, n2) }); visited.add(n2); } }) ); } else if (options.showDirected) { edges = serialize().links; } else { // If we are showing edges as undirected, we only need to show one of a -> b and b -> a edges = [ ...serialize().links.reduce((edges, link) => { const linkAB = link.source + "§" + link.target + "§" + link.weight; const linkBA = link.target + "§" + link.source + "§" + link.weight; 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: Number(w) }; }); } const eVis = options.showEdges === false ? " edge [style=invis]; " : ""; const compact = options.compact === true ? `node [${compactSetting}]` : ``; const dotCmd = dot`${ `${options.showDirected ? "digraph" : "graph"} { rankdir=${ options.rankDir }; ` + eVis + nLabels + compact + edges .map( (e) => `"${e.source}" ${connector} "${e.target}" ${ options.showWeights ? ` [label=${e.weight}];` : `;` }` ) .join("") + `}` }`; if (options.scale === undefined || options.scale === 1) { return dotCmd; } return md`

${dotCmd}`; } // The returned graph instance. return graph; }37:T8b9,`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: * `breadthFirstSearch` for breadth-first traversal with optional depth limit. * `diameter()` for finding the longest shortest-path * `betweenness()` for finding the centrality of every node. * `costMatrix` for the cost (sum of edge weights) between every pair of nodes in the graph. * [GraphViz dot](https://graphviz.org) output options to visualize the graph. * `mst()` for creating a minimum spanning tree. * `contract() for contracting a graph, removing 'corridor edges'` * `addUndirectedEdge(a, b [,w])` for adding undirected edges between two nodes with optional weight. * `inNodes(node)` for reporting the in-nodes for any given node. * can wrap a lookup data structure for multi-attribute nodes via `setLookup()` and `getLookup()`. * Minor refactoring. 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:[] 2f:{"id":"32277de66716aaaf","slug":null,"title":"GDS Graph","thumbnail":"49e3b8e7b5c25c76853ac31b4ed41e895e2facb91573182f4e68e995d0ccb899","access_level":"public","create_time":"$D2024-02-04T07:54:41.172Z","update_time":"$D2024-02-04T07:54:41.172Z","view_time":null,"first_public_time":"$D2024-02-04T07:54:41.172Z","has_unpublished_edits":null,"fork":{"id":"5879b6a3548073cb","slug":"gds-graph","title":"GDS Graph","owner":{"id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood"}},"stars":0,"starred":false,"owner":{"type":"team","id":"9784867a3e59436b","login":"linard-y","name":"","avatar_url":"https://avatars-next.observableusercontent.com/0ce44546efae24745b35d9327acbc99a3f3fdaeac3595375f92848f133b06ded","tier":"starter_2024"},"version":2059,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"c6e84137b8a39d94","login":"linard-y","name":"","avatar_url":"https://avatars-next.observableusercontent.com/0ce44546efae24745b35d9327acbc99a3f3fdaeac3595375f92848f133b06ded","tier":null}],"members":[{"type":"individual","id":"c6e84137b8a39d94","login":"linard-y","name":"","avatar_url":"https://avatars-next.observableusercontent.com/0ce44546efae24745b35d9327acbc99a3f3fdaeac3595375f92848f133b06ded","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":88,"value":"graph1.toDot({ showDirected: true })","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1382,"value":"$31","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"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* **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 'pass-through' nodes have been removed, being replaced by an edge that connects the remove node's two neighbours.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":1391,"value":"$32","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":1393,"value":"$33","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":1395,"value":"$34","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":1397,"value":"## Examples","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":19,"value":"### 1. Directed Acyclic Graphs","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":1413,"value":"graph1.toDot({ showDirected: true })","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":652,"value":"graph1.nodes()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":112,"value":"Depth-first node traversal order:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":108,"value":"graph1.depthFirstSearch()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":116,"value":"which is the opposite traversal of a topological order:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":118,"value":"graph1.topologicalSort()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":449,"value":"A breadth-first traversal:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":451,"value":"graph1.breadthFirstSearch(\"a\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":548,"value":"For large or deep graphs we may wish to limit the depth of the traversal:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":550,"value":"graph1.breadthFirstSearch(\"a\", 2)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":659,"value":"To retrieve the edges, serialise the graph and extract the edges from the serialised object:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":656,"value":"graph1.serialize().links.map((obj) => [obj.source, obj.target, obj.weight])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":649,"value":"For any node we can find its children with O(1) efficiency:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":123,"value":"graph1.adjacent(\"b\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":145,"value":"graph1.inNodes(\"e\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":159,"value":"graph1.shortestPath(\"a\", \"i\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":1880,"value":"graph1.diameter()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1485,"value":"To provide a custom view of the graph:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":66,"value":"### 2. Undirected cyclic graph","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":25,"value":"graph2.toDot({ showWeights: true, rankDir: \"LR\" })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":501,"value":"graph2.breadthFirstSearch(\"a\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1685,"value":"A minimum spanning tree:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":1687,"value":"graph2.mst().toDot({ rankDir: \"LR\", showTree: true })","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":665,"value":"Minimum cost (sum of weights) of traversing between every pair of nodes in the graph:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":667,"value":"graph2.costMatrix()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":242,"value":"Adjacent nodes to `c`:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":244,"value":"graph2.adjacent(\"c\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":254,"value":"Shortest path from `e` to `a` along with its total cost of traversal.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":256,"value":"graph2.shortestPath(\"e\", \"a\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":1776,"value":"{\n const { start, end } = graph2.diameter();\n return graph2.shortestPath(start, end);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":507,"value":"graph3.breadthFirstSearch(\"w\").map((n) => graph3.getLookup()[n].name)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1912,"value":"The path along the diameter of the graph:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":2052,"value":"graph3.betweenness()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":681,"value":"For directed graphs, the cost matrix may not be symmetrical:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":677,"value":"graph3.costMatrix()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":331,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":1963,"value":"graph4 = new Graph()\n .addEdge(\"a\", \"b\")\n .addEdge(\"b\", \"c\")\n .addEdge(\"c\", \"a\")\n\n .addEdge(\"d\", \"e\")\n .addEdge(\"d\", \"f\")\n .addEdge(\"d\", \"g\")\n .addEdge(\"f\", \"h\")\n .addEdge(\"f\", \"i\")\n\n .addEdge(\"k\", \"k\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1968,"value":"graph4.toDot()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":1972,"value":"graph4.nodes(true)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":703,"value":"### 5. 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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":808,"value":"function drawGeoGraph(graph, w = 600, h = 400) {\n const pts = graph.getLookup();\n const sp = graph.shortestPath(\"0\", \"\" + pts.length - 1);\n const path = sp.map((i) => pts[Number(i)]);\n const [xMin, xMax] = d3.extent(pts, ([x, y]) => x);\n const [yMin, yMax] = d3.extent(pts, ([x, y]) => y);\n const r = new Renderer(w, h)\n .fit(\n [\n [xMin, yMin],\n [xMax, yMax]\n ],\n w * 0.05 // 5% border\n )\n .strokeWidth(0.2)\n .pointSize(2)\n .textSize(6);\n pts.forEach(([x, y], i) =>\n graph\n .adjacent(i)\n .forEach((j) => (i < j ? r.line([pts[i], pts[j]]) : r.points([[x, y]])))\n );\n\n r.stroke().fill(\"black\");\n pts.forEach(([x, y], i) => r.text(i, x, y));\n\n r.fill(\"red\")\n .textSize(12)\n .stroke()\n .text(d3.format(\",.0f\")(sp.weight), xMax, yMax - 10);\n return r.strokeWidth(2).stroke(\"red\").line(path).render();\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":946,"value":"#### 5.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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":863,"value":"delaunay = d3.Delaunay.from(pts)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":805,"value":"#### 5.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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":872,"value":"drawGeoGraph(gabriel)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":934,"value":"#### 5.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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":940,"value":"drawGeoGraph(rng)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":922,"value":"#### 5.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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":1212,"value":"mst = rng.mst()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":956,"value":"drawGeoGraph(mst)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1327,"value":"The MST as a tree without regard to spatial position:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":1209,"value":"mst.toDot({ rankDir: \"LR\", showTree: true, compact: true })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":2019,"value":"mst.contract().toDot({ rankDir: \"LR\", showTree: true, compact: true })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"---\n\n### Appendix","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":7,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":327,"value":"import { Renderer } from \"@jwolondon/renderer\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":437,"value":"$37","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"}],"files":"$W38","stdlib":"1"}} 30:"$2f:body"