agouge / java-network-analyzer Goto Github PK

To solve #1, we need to first write a DFS.

To solve orbisgis/gdms-topology#17, we should implement Strahler using DFS.

In Dijkstra.java, we add a predecessor prematurely. We need to make sure that this is in fact a shortest path before adding the predecessor. This will require updating the logic found here and here and here

This would be useful as a check before running a Strahler number algorithm.

To try to speed up shortest path calculations, we need to look into using contraction hierarchies (CH) coupled with an appropriate bidirectional Dijkstra search algorithm.

Other Java Implementations

Note that there is already a CH implementation in GraphHopper but from what I can understand, it does not look easily adaptable to calculating centrality.

There also seems to be a CH implementation in OpenTripPlanner but I haven't really studied it.

Plan of attack

I think the easiest method would be to start by watching lessons 6 and 7 from the Efficient Route Planning course of the University of Freiburg. I could then implement my own version of CHs. Of course I will need to decide on #3 before I start the implementation.

@ebocher

Betweenness is currently calculated for nodes. We should also calculate it for edges.

It will be cool to push JNA to the OrbisGIS github repository.

We are currently able to exit a Dijkstra search once the destination(s) is(are) found. It would be nice to be able to exit Dijkstra once a given radius is passed.

In order to fix #33, it will be useful to save the shortest path tree after every iteration of Dijkstra. We can do this using a JGraphT Subgraph.

For now, we have been using GraphHopper as the underlying graph data structure for this project. It seems to be giving rather fast results.

On the jgrapht branch, we try converting the graph data structure to JGraphT. The calculations become significantly slower, but we need to consider the advantages of using JGraphT (or possibly another graph library) over GraphHopper.

@ebocher