Сохранение кратчайших путей в графе с использованием алгоритма Флойда Варшалла в Java - PullRequest
Новая
       29

Сохранение кратчайших путей в графе с использованием алгоритма Флойда Варшалла в Java

0 голосов
/ 26 мая 2018

Я пытаюсь написать метод Betweeness Centrality для неориентированного, невзвешенного (weight = 1) графика в Java.Я пошел по этому пути, найдя все кратчайшие пути в графе, а затем итерируя по этим путям и посчитав, как часто вершина является шагом в этом пути.Я использовал алгоритм Флойда Варшалла для нахождения кратчайших путей и использовал другой массив для восстановления путей, аналогично псевдокоду в Википедии.

Однако мои результаты неверныи я попытался выяснить, в чем проблема, но я не могу.Я просто опубликую весь код здесь для полноты картины, однако это грязно, поэтому я прошу прощения.Я прокомментирую биты, где, как мне кажется, возникнут проблемы. 

public void calculateBetweenessCentrality() {
    // Floyd warshall algorithm, storing paths with R
    int noPath = Integer.MAX_VALUE / 4;
    int[][] adjMatrix = getAdjacencyMatrix();
    int distances[][] = new int[numVertices][numVertices];
    int[][] R = new int[numVertices][numVertices];

    // Initialize the arrays, setting "-5000" as null instead. Possible error here?
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            if (adjMatrix[i][j] == 0) { 
                distances[i][j] = noPath;
                R[i][j] = -5000; // null
            }
            else {
                distances[i][j] = adjMatrix[i][j];
                R[i][j] = j;
            }

        }
    }
    // Do the algorithm, and save in R, possible error here?
    for (int k = 0; k < numVertices; k++) {
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                if (distances[i][j] > distances[i][k] + distances[k][j]) {
                    distances[i][j] = distances[i][k] + distances[k][j];
                    R[i][j] = R[i][k];
                }

            }
        }
    }

    // Go through R and construct the shortest paths, record the frequency for each node (indexs). Possible error here?
    HashMap<Integer, Integer> frequencies = new HashMap<>(); // Key = index, Value = frequency
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            ArrayList<Integer> path = findShortestPath(R, i, j);
            for (int p : path) {
                int freq = frequencies.containsKey(p) ? frequencies.get(p) : 0;
                frequencies.put(p, freq + 1);
            }
        }
    }

    HashMap<Integer, Integer> temp = new HashMap<Integer, Integer>(); // Instead of printing the vertex's adjacency matrix index value, get the actual value for displaying purposes.
    for (Entry<Integer, Integer> freq : frequencies.entrySet()) {
        temp.put(verticesIndexValue.get(freq.getKey()), freq.getValue());

    }
    System.out.println("Top 5 nodes: \nNode - Count");
    frequencies.entrySet().stream().sorted(Map.Entry.comparingByValue(Collections.reverseOrder())).limit(5)
            .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new))
            .forEach((node, frequency) -> System.out.println(node + " - " + frequency));

}

private ArrayList<Integer> findShortestPath(int[][] R, int u, int v) {

    ArrayList<Integer> paths = new ArrayList<>();

    if(R[u][v] == -5000)
        return paths;

    paths.add(u);
    while(u != v) {
        u = R[u][v];
        paths.add(u);
    }

    return paths;
}

График, на котором я тестирую это, взят из этого ввода здесь , где каждая линия является ребром.График в этой вставке создает два связанных компонента.Вывод, который я получаю для первого компонента, выглядит следующим образом: 

Top 5 nodes: 
Node - Count
11336782 - 11393
50393960 - 9047
627363 - 4079
849131 - 3799
5676102 - 3351

Ответ на самом деле заключается в том, что 50393960 является верхним узлом.Если кто-нибудь может, пожалуйста, направить меня туда, где я иду не так, я был бы очень признателен.Спасибо =)

1 Ответ

0 голосов
/ 27 мая 2018

Ваш код содержит ошибку в том месте, где он вычисляет частоты - в соответствии с определением центральности Betweenness при вычислении его для конкретной вершины V вы должны исключить кратчайшие пути, которые начинаются или заканчиваются вершиной V.По сути, это означает, что при итерации по кратчайшим путям вы не должны добавлять начальные и конечные вершины к частотам.Попробуйте вместо этого: 

HashMap<Integer, Integer> frequencies = new HashMap<>(); // Key = index, Value = frequency
for (int i = 0; i < numVertices; i++) {
    for (int j = 0; j < numVertices; j++) {
        ArrayList<Integer> path = findShortestPath(R, i, j);
        for (int p : path) {
            if (p == i || p == j) {
               continue;
            }
            int freq = frequencies.containsKey(p) ? frequencies.get(p) : 0;
            frequencies.put(p, freq + 1);
        }
    }
}
...