Created
December 24, 2019 21:45
-
-
Save Tristramg/7a7662a46cfa9828b53820430e299c01 to your computer and use it in GitHub Desktop.
vanillla js of https://observablehq.com/@tristramg/freespico
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<!DOCTYPE html> | |
<html> | |
<head> | |
<title>Freespico</title> | |
<script src="https://d3js.org/d3-dsv.v1.min.js"></script> | |
<script src="https://d3js.org/d3-fetch.v1.min.js"></script> | |
</head> | |
<body> | |
<h1>Freespico</h1> | |
<button onclick="compute()">Find route</button> | |
<script src="./index.js"></script> | |
</body> | |
</html> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const stationsUrl = "https://static.observableusercontent.com/files/e1fb588052b52626891024d699f6c08bae67eabb208f3e3aa61194858681a77abfa314fc1a0107de975bfa6d9c3c726799550bbd4530dfbe7694c310411ea6d6" | |
const edgesUrl = "https://static.observableusercontent.com/files/ad26fee976a7f10c4b5c5a6f6fc3b050fe114ec0c4f9326bbd62b09281b975ee8039ff786ea3e1c658546ce8daf58a81bbdda4df7c2dba89d043c2be097e6900" | |
let stations = {} | |
let edges = {} | |
d3.dsv('\t', stationsUrl, d3.autoType).then(s => { | |
stations = s | |
d3.dsv(';', edgesUrl, d3.autoType).then(e => { | |
edges = e | |
console.log('loggin') | |
compute() | |
}) | |
}) | |
function bellman(edges, nodes, from, to){ | |
console.log("Starting") | |
const nodesCount = 2600 | |
const dist = new Float32Array(nodesCount) | |
const pred = new Uint16Array(nodesCount) | |
const duration = new Float32Array(nodesCount) | |
for (let i = 0; i < nodesCount; i++) { | |
dist[i] = Infinity | |
pred[i] = i | |
duration[i] = Infinity | |
} | |
dist[from] = 0 | |
duration[from] = 0 | |
for (let i=0; i < nodesCount; i++) { | |
for (const edge of edges) { | |
// if (edge.vmax < 230 || !paramètres.eviterLGV) { | |
const edge_duration = edge.longueur * 60 / edge.vmax | |
if (dist[edge.ido] + edge.longueur < dist[edge.idf]) { | |
pred[edge.idf] = edge.ido | |
dist[edge.idf] = dist[edge.ido] + edge.longueur | |
duration[edge.idf] = duration[edge.ido] + edge_duration | |
} | |
// Edges are symetrical | |
if (dist[edge.idf] + edge.longueur < dist[edge.ido]) { | |
pred[edge.ido] = edge.idf | |
dist[edge.ido] = dist[edge.idf] + edge.longueur | |
duration[edge.ido] = duration[edge.idf] + edge_duration | |
} | |
} | |
} | |
// } | |
const result = [] | |
let current = to | |
do { | |
result.push(current) | |
current = pred[current] | |
} while (pred[current] != current) | |
console.log("done") | |
return { | |
nodes: result.reverse(), | |
distance: dist[to], | |
duration: duration[to], | |
} | |
} | |
function compute() { | |
bellman(edges, stations, 12, 100) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment