# Do the function “GetDiameter” in JGraphT cost much internal memory?

Here is the problem: Recently I would like to use JGraphT to get the diameter from a graph with 5 million vertices.But it shows that "out of memory java heap space" even I add -Xmx 500000m.How could I solve this issue? Thanks a lot!

Here is the part of my code:

``````public static void main(String[] args) throws URISyntaxException,ExportException,Exception {
Graph<Integer, DefaultEdge> subGraph = createSubGraph();
System.out.println(GetDiameter(subGraph));
}

private static Graph<Integer, DefaultEdge> createSubGraph() throws Exception
{

Graph<Integer, DefaultEdge> g = new DefaultUndirectedGraph<>(DefaultEdge.class);

int j;
String edgepath = "sub_edge10000.txt";
String newline = null;
String[] parts = newline.split(":");
}
bufr.close();

String[] parts = newline.split(":");
int origin=Integer.parseInt(parts[0]);
parts=parts[1].split(" ");
for(j=0;j<parts.length;j++){
int target=Integer.parseInt(parts[j]);
}
}
bufr.close();

return g;
}

private static double GetDiameter(Graph<Integer, DefaultEdge> subGraph)
{
GraphMeasurer g=new GraphMeasurer(subGraph,new JohnsonShortestPaths(subGraph));
return g.getDiameter();
}
``````

On Best Solutions

If n is the number of vertices of your graph, then the library internally creates an n by n matrix to store all shortest paths. So, yes, the memory consumption is substantial. This is due to the fact that internally the library uses an all-pairs shortest-path algorithm such as Floyd-Warshall or Johnson's algorithm.

Since you do not have enough memory, you could try to compute the diameter using a single-source shortest path algorithm. This will be slower, but will not require so much memory. The following code demonstrates this assuming an undirected graph and non-negative weights and thus using Dijkstra's algorithm.

``````package org.myorg.diameterdemo;

import org.jgrapht.Graph;
import org.jgrapht.alg.interfaces.ShortestPathAlgorithm;
import org.jgrapht.alg.interfaces.ShortestPathAlgorithm.SingleSourcePaths;
import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.builder.GraphTypeBuilder;
import org.jgrapht.util.SupplierUtil;

public class App {

public static void main(String[] args) {

Graph<Integer, DefaultWeightedEdge> graph = GraphTypeBuilder
.undirected()
.weighted(true)
.allowingMultipleEdges(true)
.allowingSelfLoops(true)
.vertexSupplier(SupplierUtil.createIntegerSupplier())
.edgeSupplier(SupplierUtil.createDefaultWeightedEdgeSupplier())
.buildGraph();

double diameter = Double.NEGATIVE_INFINITY;
for(Integer v: graph.vertexSet()) {
ShortestPathAlgorithm<Integer, DefaultWeightedEdge> alg = new DijkstraShortestPath<Integer, DefaultWeightedEdge>(graph);

SingleSourcePaths<Integer, DefaultWeightedEdge> paths = alg.getPaths(v);
for(Integer u: graph.vertexSet()) {
diameter = Math.max(diameter, paths.getWeight(u));
}
}

System.out.println("Graph diameter = " + diameter);
}

}
``````

If you do have negative weights, then you need to replace the shortest path algorithm with Bellman-Ford using `new BellmanFordShortestPath<>(graph)` in the above code.

Additionally, one could also employ the technique by Johnson to transform the edge weights to non-negative first by using Bellman-Ford and then start executing calls to Dijkstra. However, this would require non-trivial changes. Take a look at the source code of class `JohnsonShortestPaths` in the JGraphT library.