Roadmap

Done

Unweighted graphs:

• Certain centrality measures
  • Betweenness centrality - using Brandes' algorithm in A Faster Algorithm for Betweenness Centrality (2001).
  • Closeness centrality - using results from the calculation for betweenness

ToDo

Unweighted graphs:

• Other network parameters: See NetworkAnalyzer for a list of possibilities.
  • Parameters that should be very easy to compute:

Weighted graphs:

• Betweenness centrality
  • Both JGraphT-SNA and NetworkAnalyzer (also here) compute betweenness only for unweighted graphs using Brandes.
  • Modify Brandes' algorithm by replacing BFS with another one-to-many shortest paths algorithm to find (and count) all shortest paths (not just one). Options:
    1. Old-fashioned: Dijkstra (see the end of the Pseudocode section), A*, Floyd-Warshall, or Johnson (better for sparse graphs).
    2. More recent:
       • See the Fast and Exact Route Planning website for information on contraction hierarchies (CH). This recent technology (based on Robert Geisberger's thesis [Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks] thesisGeisberger (July 1, 2008; 70 pages), combined with a modified bidirectional Dijkstra search, is probably the fastest way to calculate all-pairs shortest paths. This research group already implemented CHs in C++.
         • The best Java implementation of CHs seems to be GraphHopper. The problem is that the GraphHopper implementation is giving slower results using CHs than JGraphT-SNA does using a simple Dijkstra search. The source code is not very well documented. It would probably be best to write my own implementation.
         • See video lectures 6 and 7 of the Efficient Route Planning course (summer 2012). In the corresponding exercises, students are asked to implement CHs.
         • Parallelized version: See Christian Vetter's paper Parallel Time-Dependent Contraction Hierarchies (July 13, 2009). In his diploma thesis [Fast and Exact Mobile Navigation with OpenStreetMap Data][] (March 1, 2010; 78 pages), Vetter developed the C++ mobile routing application MoNav based on CHs using OpenStreetMap data.
       • Also see the Route Planning in Transportation Networks research group for a long list of publications and recent advances.
       • See Route Planning in Road Networks and Dominik Schultes' thesis (February 7, 2008; 235 pages) of the same name for the following:
         • Highway hierarchies
         • Highway-node routing
         • Transit-node routing
• Other centrality measures and network parameters (just as for unweighted graphs).