Dijkstra's algorithm on an RGG / Mark McClure

I'm a professor of mathematics at the University of North Carolina Asheville. I've also done a fair amount of consulting work over the years focusing on scientific and data visualization. I'm happy to be part of the first Observable Ambassador's cohort.

Workspace

Public

Edited

Dec 2, 2022

3 forks

48 stars

// This function just draws the picture; there's no real computation here.

function draw_network_viz() {

let svg = d3.create("svg").attr("width", w).attr("height", h);

let link = svg.append("g").attr("id", "links");

link

.selectAll("line.link")

.data(G.links)

.join("line")

.attr("class", "link")

.attr("id", (d) => d.cy_data.id)

.attr("stroke", "black")

.attr("stroke-width", 1)

.attr("stroke-opacity", 0.1)

.attr("x1", (d) => d.source.x)

.attr("y1", (d) => d.source.y)

.attr("x2", (d) => d.target.x)

.attr("y2", (d) => d.target.y);

let node = svg.append("g").attr("stroke", "#fff").attr("stroke-width", 1.5);

node

.selectAll("circle")

.data(G.nodes)

.join("circle")

.attr("class", (o) => (o.valence == G.max_valence ? "hub" : "port"))

.attr("id", (d) => d.cy_data.id)

.attr("cx", (d) => d.x)

.attr("cy", (d) => d.y)

.attr("r", (o) => 6 * (o.valence / G.max_valence) ** 1)

.attr("fill", "black");

node

.selectAll("circle.hub")

.nodes()

.forEach(function (c, i) {

if (i == 0) {

d3.select(c).attr("r", 8).attr("fill", "red").raise();

} else {

d3.select(c).attr("class", "port");

}

});

svg

.on("touchmove", (evt) => evt.preventDefault())

.on("pointerenter pointermove", function (evt) {

node

.selectAll("circle.port")

.attr("r", (o) => 6 * (o.valence / G.max_valence) ** 1)

.attr("fill", "black");

link

.selectAll("line")

.attr("stroke", "black")

.attr("stroke-width", 1)

.attr("stroke-opacity", 0.1);

let [x, y] = d3.pointer(evt);

let closest = qt.find(x, y);

if ((closest.x - x) ** 2 + (closest.y - y) ** 2 < 1000) {

let p = di.pathTo(`#n${closest.index}`);

let shortest_path = {

nodes: p.nodes().map((n) => n.id()),

edges: p.edges().map((e) => e.id())

};

let len = shortest_path.nodes.length;

shortest_path.nodes.forEach((id, i) =>

svg

.select(`#${id}`)

.attr("r", i == 0 ? 8 : 5)

.attr("fill", i == 0 ? "red" : i == len - 1 ? "green" : "blue")

);

shortest_path.edges.forEach((id) =>

svg

.select(`#${id}`)

.attr("stroke-width", 2)

.attr("stroke", "blue")

.attr("stroke-opacity", 1)

);

}

})

.on("pointerleave", function () {

node

.selectAll("circle.port")

.attr("r", (o) => 6 * (o.valence / G.max_valence) ** 1)

.attr("fill", "black");

link

.selectAll("line")

.attr("stroke", "black")

.attr("stroke-width", 1)

.attr("stroke-opacity", 0.1);

});

return svg.node();

}

qt = d3

.quadtree()

.x((d) => d.x)

.y((d) => d.y)

.addAll(G.nodes)

.extent([

[0, 0],

[w, h]

])

cy = {

let nodes = G.nodes.map((n) => ({ data: { id: `n${n.index}` } }));

let edges = G.links.map(function (e) {

let source_node = `n${e.source.index}`;

let target_node = `n${e.target.index}`;

return {

data: {

source: source_node,

target: target_node,

id: `${source_node}--${target_node}`,

length2: e.length2

}

};

});

return cytoscape({

elements: {

nodes: nodes,

edges: edges

}

});

}

di = cy.elements().dijkstra({

root: `#n${G.root_node.index}`,

weight: (e) => e._private.data.length2

})

// The network is represented by the following random geometric graph.

G = {

new_graph;

let N = Math.round(800 * s);

let seed = 0.1234;

seed = Math.random();

let random_source_x = d3.randomLcg(seed);

let random_source_y = d3.randomLcg(seed / 2);

let random_x = d3.randomUniform.source(random_source_x)(0, w);

let random_y = d3.randomUniform.source(random_source_y)(0, h);

let pts = d3.range(N).map(() => [random_x(), random_y()]);

let nodes = pts.map((p, i) => ({

x: p[0],

y: p[1],

index: i,

cy_data: { id: `n${i}` }

}));

let R = 4000;

let links = nodes

.map((node, i) => nodes.slice(i + 1).filter((n) => dist2(node, n) < R))

.map((a, i) =>

a.map((o) => ({

source: nodes[i],

target: nodes[o.index],

length2: Math.sqrt(dist2(nodes[i], nodes[o.index])),

cy_data: { id: `n${i}--n${o.index}` }

}))

)

.flat();

nodes.forEach(

(o) =>

(o.valence = links.filter(

(l) => l.source.index == o.index || l.target.index == o.index

).length)

);

let max_valence = d3.max(nodes.map((o) => o.valence));

let root_node = nodes.filter((o) => o.valence == max_valence)[0];

let G = { nodes, links, max_valence, root_node };

return G;

function dist2(o1, o2) {

return (o1.x - o2.x) ** 2 + (o1.y - o2.y) ** 2;

}

s = r ** 2

r = w / 1000

w = width < 1100 ? width : 1100

h = 0.625 * w

cytoscape = require("cytoscape")

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