The avatar for @jwolondon
Jo Wood
Professor of Visual Analytics interested in design, geovisualization, visual storytelling and computational thinking.
Public
Edited
Dec 25, 2023
Paused
2 forks
Importers
6 stars
utilities
RendererSpatial JSON ViewerGeoJSON GeneratorGrid map allocationGridded Region EditorCensus 2021 ExplorerUK Election 2024: Boundary DataAlpha shapesPolyLabelProjectionData TidierHello Colour MixingHello modern colour spaces
GDS Graph
Seeded Random NumbersAOC UtilitiesCalculating Stream Order from Open Rivers dataCurved Text MarkInteractive Time Range Input
Also listed in…
Ξ🎄Advent of Code
Insert cell
Insert cell
graph1 = Graph()
.addEdge("a", "b")
.addEdge("a", "c")
.addEdge("b", "d")
.addEdge("b", "e")
.addEdge("b", "f")
.addEdge("c", "g")
.addEdge("e", "h")
.addEdge("e", "i")
Insert cell
graph1.toDot({ showDirected: true })
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
graph1.toDot({ showDirected: true })
Insert cell
Insert cell
graph1.nodes()
Insert cell
Insert cell
graph1.depthFirstSearch()
Insert cell
Insert cell
graph1.topologicalSort()
Insert cell
Insert cell
graph1.breadthFirstSearch("a")
Insert cell
Insert cell
graph1.breadthFirstSearch("a", 2)
Insert cell
Insert cell
graph1.serialize().links.map((obj) => [obj.source, obj.target, obj.weight])
Insert cell
Insert cell
graph1.adjacent("b")
Insert cell
Insert cell
graph1.inNodes("e")
Insert cell
Insert cell
graph1.shortestPath("a", "i")
Insert cell
Insert cell
graph1.diameter()
Insert cell
Insert cell
{
const labels = {
a: "Root",
d: "d (leaf)",
f: "f (leaf)",
g: "g (leaf)",
h: "h (leaf)",
i: "i (leaf)"
};
return graph1.toDot({
showDirected: true,
rankDir: "BT",
nodeLabels: labels
});
}
Insert cell
Insert cell
Insert cell
graph2 = Graph()
.addUndirectedEdge("a", "b", 7)
.addUndirectedEdge("a", "c", 9)
.addUndirectedEdge("a", "f", 14)
.addUndirectedEdge("b", "c", 10)
.addUndirectedEdge("b", "d", 15)
.addUndirectedEdge("c", "d", 11)
.addUndirectedEdge("c", "f", 2)
.addUndirectedEdge("d", "e", 6)
.addUndirectedEdge("e", "f", 9)
.addUndirectedEdge("e", "e", 5)
Insert cell
graph2.breadthFirstSearch("a")
Insert cell
Insert cell
graph2.mst().toDot({ rankDir: "LR", showTree: true })
Insert cell
Insert cell
graph2.costMatrix()
Insert cell
Insert cell
{
const ew = (n1, n2) =>
graph2.hasEdge(n1, n2)
? `Weight from ${n1} to ${n2} is ${graph2.getEdgeWeight(n1, n2)}`
: `No edge from ${n1} to ${n2}`;
return [ew("a", "b"), ew("a", "d"), ew("b", "b"), ew("e", "e")];
}
Insert cell
Insert cell
graph2.adjacent("c")
Insert cell
Insert cell
graph2.shortestPath("e", "a")
Insert cell
Insert cell
{
const { start, end } = graph2.diameter();
return graph2.shortestPath(start, end);
}
Insert cell
Insert cell
Insert cell
Insert cell
graph3 = Graph()
.addEdge("h", "c", 5)
.addEdge("a", "h", 3)
.addUndirectedEdge("b", "h", 2)
.addUndirectedEdge("b", "d", 1)
.addUndirectedEdge("b", "e", 6)
.addEdge("c", "e", 2)
.addEdge("d", "a", 3)
.addEdge("e", "f", 1)
.addEdge("e", "w", 4)
.addEdge("f", "d", 4)
.addEdge("w", "f", 1)
.setLookup({
h: { x: 1, y: 4, name: "Home" },
a: { x: 0, y: 1, name: "A" },
b: { x: 1, y: 2, name: "B" },
c: { x: 3, y: 4, name: "C" },
d: { x: 3, y: 0, name: "D" },
e: { x: 4, y: 3, name: "E" },
f: { x: 6, y: 2, name: "F" },
w: { x: 9, y: 3, name: "Work" }
})
Insert cell
Insert cell
graph3.breadthFirstSearch("w").map((n) => graph3.getLookup()[n].name)
Insert cell
Insert cell
{
const { start, end } = graph3.diameter();
return graph3.shortestPath(start, end).map((n) => graph3.getLookup()[n].name);
}
Insert cell
Insert cell
graph3.betweenness()
Insert cell
Insert cell
graph3.costMatrix()
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
graph4.nodes(true)
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
function drawGeoGraph(graph, w = 600, h = 400) {
const pts = graph.getLookup();
const sp = graph.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(2)
.textSize(6);
pts.forEach(([x, y], i) =>
graph
.adjacent(i)
.forEach((j) => (i < j ? r.line([pts[i], pts[j]]) : r.points([[x, y]])))
);

r.stroke().fill("black");
pts.forEach(([x, y], i) => r.text(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();
}
Insert cell
Insert cell
Insert cell
Insert cell
{
const graph = Graph();
graph.setLookup(pts);
pts.forEach((_, i) =>
[...delaunay.neighbors(i)].forEach((j) =>
graph.addEdge(
i,
j,
Math.hypot(pts[i][0] - pts[j][0], pts[i][1] - pts[j][1])
)
)
);
return drawGeoGraph(graph);
}
Insert cell
Insert cell
gabriel = {
const dist = (a, b) => Math.hypot(a[0] - b[0], a[1] - b[1]);
const mid = (a, b) => [(a[0] + b[0]) / 2, (a[1] + b[1]) / 2];
const gg = Graph();
gg.setLookup(pts);
pts.forEach((_, i) =>
[...delaunay.neighbors(i)].forEach((j) => {
if (delaunay.find(...mid(pts[i], pts[j]), i) === i) {
gg.addEdge(i, j, dist(pts[i], pts[j]));
}
})
);
return gg;
}
Insert cell
Insert cell
Insert cell
rng = {
const dSq = (a, b) =>
(a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);
const rnGraph = new Graph();
rnGraph.setLookup(pts);

gabriel.nodes().forEach((n1) => {
const nodes = gabriel.adjacent(n1);
gabriel.adjacent(n1).forEach((n2) => {
const dEdge = dSq(pts[n1], pts[n2]);
nodes.concat(gabriel.adjacent(n2));
if (
nodes
.map((n) => Math.max(dSq(pts[n], pts[n1]), dSq(pts[n], pts[n2])))
.filter((d) => d < dEdge).length === 0
) {
rnGraph.addEdge(n1, n2, gabriel.getEdgeWeight(n1, n2));
}
});
});
return rnGraph;
}
Insert cell
Insert cell
Insert cell
mst = rng.mst()
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell

Purpose-built for displays of data

Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
Learn more