Shortest path calculation algorithm

[bartossh]

New geo::algorithm module to calculate shortest path between two given points based on given MultiLineString struct.

Let's implement it in two separate steps for two separate features.

1. First function is going to take MultiLineString and calculate (return) VertexString that will hold information about Coordinate and vertex graph. Each given Vertex than has its index and graph. Graph is a vector with GraphRelation's. GraphRelaton holds index of other Vertex that actual Vertex is connected to and travel cost between both Vertexes.

• Vertex: struct Vertex { coordinates: Coordinate, graphs: Vec<GraphRelation>, }

• GraphRelation: struct GraphRelation { vertex_index: usize, cost: f64, }

• VertexString: pub struct VertexString { cost_calc_type: Cost, vector: Vec<Vertex>, }

• Cost enum enum Cost { EUCLIDEAN, HAVERSINE, ..., }

• I have been implementing this here : vertex idea I have implemented only haversine formula.

• But I think your lib has mostly everything I would like to have and even more. Maybe there will be possibility to add proposed feature to your lib.

• Travel cost can be implemented using any of available algorithm as there is an variety of them.

• distance calculation is than going to take struct MultiLineString that implements trait CostCalculation. CostCalculation returns f64 or type Distance that is f64. CostCalculation will contain all functions to calculate cost. Passed Cost enum will determinate which function is to be be used for travel cost calculation .

• nice to have: recalculate distance cost, that will simply apply given function to each Vertex graph_relation recalculating all graph costs.

2. Second function is going to be Dijkstra shortest path algorithm that is taking VertexString, start Coordinate and finish Coordinate, then returns LineString. Returned LineString is shortest path calculated by algorithm. Shortest Path:

• can be applied to any VertexString,
• algorithm do not know anything about travel cost, it uses pre-calculated cost in Vertex graph
• can be implemented for VertexString as pub fn djikstra_shortest_path(&self, start: &Coordinate, stop: &Coordinate) -> LineString
• nice to have: function to find closest point on VertexString for given Cooedinate and return closest Vertex index or / and Vertex. Don't know at this point, this is for the future I think.

Example struct based issue

We have line_string: LineString, point_start: Coordinate, point_stop: Coordinate

let multi_lines: MultiLineString = MultiLinesString::from(line_string);
let haversine = DistanceCost::HAVERSINE;
let vertex_string: VertexString = VertexString::new(multi_lines, haversine);
let shortest__path: LineString = DijkstraPath::new(vertex_string, point_start, point_stop);

I would be glad to do pull request for this proposal. Thx.

[frewsxcv]

Sounds good to me! I think this would be a great addition to the library! Sorry this response took so long 😬

[bartossh]

Great. What do You think to implement Vertex first? And to write some test, then We will discuss implementation of shortest path algorithm ?

[frewsxcv]

relevant pr https://github.com/georust/geo/pull/366

[PayasR]

Do you need help with this?

[michaelkirk]

@PayasR - #366 was opened a while ago. I've just left some comments there to see if they're still interested in getting their implementation merged - it's been a while.

[PayasR]

Great, thanks! Though I'm still thinking, does this actually belong here, given that there are crates like fast_paths that are specifically designed for this algorithm?

[michaelkirk]

Fair question.

I think finding shortest path is a likely problem for someone doing other stuff with the geo crate, so it makes sense to make it easy for people using the geo crate to do shortest path calculations with geo-types.

1. One approach would be to include the algorithm directly, like #366 attempts.
2. An alternative approach might be to add a dependency on fast_paths, and delegate to its implementation (maybe behind a feature flag?)
3. Another approach might be to try to upstream a "geo-types" feature to fast_path.

If I were to work on this myself, I'd probably start with approach 2 or 3.

[PayasR]

If we choose (2), we'll need to be careful with the choice of library we delegate to. fast_paths implements both bidirectional dijkstra's and Contraction Hierarchies (CH). CH works incredibly well for networks that have a 'hierarchy', (roads networks have highways, local roads, ... ) but might actually perform worse than regular bidirectional dijkstra's on random graphs.

Another, probably more widely adopted alternative would be petgraph, which provides standard dijkstra's implementations (not bidirectional, though), but gives access to a whole host of other algorithms as well (A*, k-shortest paths, ...).

The choice ultimately boils down to three questions: what is the scope of the project, what are the graph algorithms that could be useful in the future, and what is 'acceptable' performance?

[PayasR]

Now that #366 is closed, where do we head next?