Стоит ли функция «GetDiameter» в JGraphT много встроенной памяти? - PullRequest
Новая
       17

Стоит ли функция «GetDiameter» в JGraphT много встроенной памяти?

0 голосов
/ 29 апреля 2019

Вот проблема: недавно я хотел бы использовать JGraphT, чтобы получить диаметр из графика с 5 миллионами вершин. Но он показывает, что «из памяти Java куча» даже я добавляю -Xmx 500000m. Как я могу решитьЭта проблема?Большое спасибо!

Вот часть моего кода: 

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";
    FileReader fr = new FileReader(edgepath);
    BufferedReader bufr = new BufferedReader(fr);
    String newline = null;
    while ((newline = bufr.readLine())!=null) {
        String[] parts = newline.split(":");
        g.addVertex(Integer.parseInt(parts[0]));
    }
    bufr.close();

    fr = new FileReader(edgepath);
    bufr = new BufferedReader(fr);
    while ((newline = bufr.readLine())!=null) {
        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]);
            g.addEdge(origin,target);
        }
    }
    bufr.close();

    return g;
}

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

1 Ответ

1 голос
/ 29 апреля 2019

Если n - это число вершин вашего графа, то библиотека внутренне создает матрицу n на n для хранения всех кратчайших путей.Так что да, потребление памяти значительно.Это связано с тем, что внутренне библиотека использует алгоритм кратчайшего пути из всех пар, такой как алгоритм Флойда-Варшалла или Джонсона.

Поскольку у вас недостаточно памяти, вы можете попытаться вычислить диаметр, используя алгоритм кратчайшего пути из одного источника.Это будет медленнее, но не потребует столько памяти.Следующий код демонстрирует это, предполагая неориентированный граф и неотрицательные веса и, таким образом, используя алгоритм Дейкстры.

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();

        Integer a = graph.addVertex();
        Integer b = graph.addVertex();
        Integer c = graph.addVertex();
        Integer d = graph.addVertex();
        Integer e = graph.addVertex();
        Integer f = graph.addVertex();

        graph.addEdge(a, c);
        graph.addEdge(d, c);
        graph.addEdge(c, b);
        graph.addEdge(c, e);
        graph.addEdge(b, e);
        graph.addEdge(b, f);
        graph.addEdge(e, f);

        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);
    }

}

Если у вас есть отрицательные веса, вам нужно заменить алгоритм кратчайшего пути на Bellman-Ford, используя new BellmanFordShortestPath<>(graph) в приведенном выше коде.

Кроме того, можно также использоватьметодика Джонсона, чтобы сначала преобразовать веса ребер в неотрицательные, используя Беллмана-Форда, а затем начать выполнять вызовы Дейкстры.Однако это потребует нетривиальных изменений.Посмотрите на исходный код класса JohnsonShortestPaths в библиотеке JGraphT.

...