Как я могу использовать алгоритм AStarShortestPath в JGraphT для расчета диаметра графа？ - PullRequest
Новая
       23

Как я могу использовать алгоритм AStarShortestPath в JGraphT для расчета диаметра графа？

0 голосов
/ 06 мая 2019

Я попытался написать несколько кодов для использования алгоритма AStarShortestPath с JGraphT для вычисления диаметра графа ，, но он даже не вычисляет один кратчайший путь. Вот некоторые из моих кодов для вычисления диаметра графа с миллионамивертикали: 

public static void main(String[] args) throws Exception {

    Graph<Integer, DefaultWeightedEdge> subGraph = createSubGraph();
    AStarAdmissibleHeuristic heuristic = new AStarAdmissibleHeuristic() {
        @Override
        public double getCostEstimate(Object o, Object v1) {
            return 4;
        }
    };

    double diameter = Double.NEGATIVE_INFINITY;
    double curr_diameter = Double.NEGATIVE_INFINITY;
    int i=0;

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

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

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

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

    int j;
    String edgepath = "sub_edge2000000.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;
}

Большое спасибо!

...