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

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). It would probably be best to write my own implementation. 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 Fast and Exact Route Planning 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 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 are already implemented in GraphHopper. The problem is that the GH implementation is giving slower results using CHs than JGraphT-SNA using a simple Dijkstra search.
         • See video lectures 6 and 7 of the 2012 Efficient Route Planning course (summer 2012). In the corresponding exercises, students are asked to implement CH.
         • Parallelized version: See Christian Vetter's paper Parallel Time-Dependent Contraction Hierarchies (2009).
       • 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