I have used jgrapht to analyse some graph problems. Now I am working with big graph (with more than ten millions nodes ) and use CH algorithm.
What troubles me is the precomputation of CH is so long, nearly 2 hours. And I found the preprocessed data is saved in ContractionHierarchy as below.
public static class ContractionHierarchy<V, E> {
private Graph<V, E> graph;
private Graph<ContractionVertex<V>, ContractionEdge<E>> contractionGraph;
private Map<V, ContractionVertex<V>> contractionMapping;
public Graph<V, E> getGraph() {
return this.graph;
}
public Graph<ContractionVertex<V>, ContractionEdge<E>> getContractionGraph() {
return this.contractionGraph;
}
public Map<V, ContractionVertex<V>> getContractionMapping() {
return this.contractionMapping;
}
ContractionHierarchy(Graph<V, E> graph, Graph<ContractionVertex<V>, ContractionEdge<E>> contractionGraph, Map<V, ContractionVertex<V>> contractionMapping) {
this.graph = graph;
this.contractionGraph = contractionGraph;
this.contractionMapping = contractionMapping;
}
public void unpackBackward(ContractionEdge<E> edge, LinkedList<V> vertexList, LinkedList<E> edgeList) {
if (edge.bypassedEdges == null) {
vertexList.addFirst(((ContractionVertex)this.contractionGraph.getEdgeSource(edge)).vertex);
edgeList.addFirst(edge.edge);
} else {
this.unpackBackward((ContractionEdge)edge.bypassedEdges.getSecond(), vertexList, edgeList);
this.unpackBackward((ContractionEdge)edge.bypassedEdges.getFirst(), vertexList, edgeList);
}
}
public void unpackForward(ContractionEdge<E> edge, LinkedList<V> vertexList, LinkedList<E> edgeList) {
if (edge.bypassedEdges == null) {
vertexList.addLast(((ContractionVertex)this.contractionGraph.getEdgeTarget(edge)).vertex);
edgeList.addLast(edge.edge);
} else {
this.unpackForward((ContractionEdge)edge.bypassedEdges.getFirst(), vertexList, edgeList);
this.unpackForward((ContractionEdge)edge.bypassedEdges.getSecond(), vertexList, edgeList);
}
}
}
So I wonder is there any way to export ContractionHierarchy to files so that I can use it next time without compile the precomputation and query directly.