JGraphT Good Performance/Storage with Millions of Dynamic Nodes/Edges

810 views Asked by At

I'm trying to find the shortest path in a graph with a million nodes. On average, there are likely 20 directed edges per node, so it's quite sizeable.

In addition to this, is there a way to adjust the edge weights in real-time (dynamically)?

What I mean is I want to be able to route the graph by a time parameter. Depending on that time parameter, it will multiply edge weights by some amount.

You may have this data:

  • Node A
  • Node B
  • Edge 1 (A to B) having weight 5
  • Edge 2 (also from A to B) having weight 3

I may call a function:

graph.getShortestPath(A, B, 8) // From node A to B at 8am
graph.getShortestPath(A, B, 16) // From node A to B at 4pm

The time parameter would influence the edge weights. Eg. when an edge is traversed, I would like to identify the location of that edge and multiply its weight by a factor dependent on the time parameter.

Is there a simple JGraphT example in Java (or even better, Kotlin) that would illustrate this?

1

There are 1 answers

1
Joris Kinable On BEST ANSWER

Time dependent routing on such a large graph is no easy task, especially not if you are looking for dynamic updates. This would require highly sophisticated algorithms and storage approaches. Not surprisingly, there's a whole range of academic literature on this topic.

For jgrapht, first read the user guide. Next, have a look at the various Shortest Path Algorithms that are currently included in jgrapht. For examples on how to use them, see the test classes. You probably want to use one of the Contraction Hierarchy algorithms. You pay an initial cost to perform the initialization of the algorithm, but subsequent shortest path queries on large graphs are really fast. For faster storage of your graph, you might want to try the optimized sparse graph representation in the jgrapht-opt package.

Currently none of the algorithms provide some incremental mechanism to deal with dynamic weight changes. Moreover, time-dependent algorithms are currently not included. What you could do is create several time snapshots of your graph, e.g. a snapshot of the travel speeds every 15 minutes. When computing a shortest path for a route that starts at say 9.05, you would use the 9.15 snapshot to approximate the travel time. For snapshots, use the AsWeightedGraph view through which you can provide different weighted views of the same underlying graph.