Alpha 4

What's New

• Dijkstra has been enhanced with a multi-destination A* heuristic
• Simulated annealing has had its mutation simplified and parameters tuned
• The PBF importer now imports all roads as bi-directional instead of uni-directional
  • This is incorrect, but less incorrect than previously because most roads are not 1-way (citation needed)

Full Changelog: alpha-3...alpha-4

Alpha 3

What's New

• Speed up API by only importing the graph once, and storing it in state #62
• Connect TSP to Dijkstra to OSM Monaco #72
• Extend web demo to TSP by @adnathanail in #79
• Add XGMML import by @adnathanail in #86
• Test Dijkstra on USA-road-d.NY by @adnathanail in #92
• Benchmark Dijkstra on OSM Monaco by @adnathanail in #57
• Pick Dijkstra implementation by @adnathanail in #55
• Test web API by @adnathanail in #64
• Priority queue updates by @adnathanail in #96

Bug fixes

• Fix distances on PBF import (long lat backwards) by @adnathanail in #73
• AM Digraph: Don't include edges with infinite weight in adj by @adnathanail in #74
• Stop GraphPath being backwards by @adnathanail in #77

Refactors

• New benchmark groupings by @adnathanail in #59
• Refactor Dijkstra into struct by @adnathanail in #66
• Centralise tests by @adnathanail in #69
• Create LatLng struct by @adnathanail in #76
• Rename dijkstra files to shortest_path by @adnathanail in #87
• Make function API's consistent by @adnathanail in #89* Move latlng and haversine into geography module by @adnathanail in #97
• Stop using dyn by @adnathanail in #98

Full Changelog: alpha-2...alpha-3

Alpha 2

Implementation

• Create graph interface, and interface both adjacency matrix and list data structures (for sparse vs connected graphs)
• Attach node ID's and node data to graphs, to allow modelling OSM data
• Route by long lat instead of node ID
• Connected components algorithm

I/O

• Read PBF files
• Write SVG files
• Create web interface demo

End to end

• Real-world routing: importing OSM data, getting the largest connected component, finding the closest nodes to long lats, running Dijkstra

Testing

• Benchmark TSP
• Comment benchmark results against master on all PR's, to track regression/improvement

Alpha 1

Implementations

• Custom graph data structure
• Dijkstra shortest path algorithm
• Hill climbing TSP solver

Testing

• Randomly generated graphs
• DIMCAS TSP test data
• Time-based benchmarking