Реализовать Косвенный Тест Связности для класса Java Graph

Question

Я пишу класс на Java для представления структуры данных Graph.Это характерно для неориентированного невзвешенного графа и предназначено в основном для тестирования ребер (подключен ли узел A к узлу B напрямую или косвенно).

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

Я потратил некоторое время на разработку алгоритма, но не могукажется, найти что-то более простое, чем это, и я боюсь, что я делаю это более сложным, чем нужно:

- test first for a direct connection
- if no direct connection exists from node a to node b:
    - for every edge i connected to node a:
        - create a new graph that does not contain edge a -> i
        - test new graph for indirect connectivity between nodes i and b

В ваших ответах приветствуется либо псевдокод, либо реальный код Java.Спасибо за вашу помощь.Вот код, который у меня есть:

class Graph {

    // This is for an undirected, unweighted graph
    // This implementation uses an adjacency matrix for speed in edge testing 

    private boolean[][] edge;
    private int numberOfNodes;

    public Graph(int numNodes) {

        // The indices of the matrix will not be zero-based, for clarity,
        // so the size of the array will be increased by 1.

           edge = new boolean[numNodes + 1][numNodes + 1];
           numberOfNodes = numNodes;
    }

    public void addEdge(int a, int b) {
        if (a <= numberOfNodes && a >= 1) {
            if (b <= numberOfNodes && b >= 1) {
                edge[a][b] = true;
                edge[b][a] = true;
            }
        }
    }

    public void removeEdge(int a, int b) {
        if (a <= numberOfNodes && a >= 1) {
            if (b <= numberOfNodes && b >= 1) {
                edge[a][b] = false;
                edge[b][a] = false;
            }
        }
    }

    public boolean directEdgeTest(int a, int b) {

        // if node a and node b are directly connected, return true 

        boolean result = false;
        if (a <= numberOfNodes && a >= 1) {
            if (b <= numberOfNodes && b >= 1) {
                if (edge[a][b] == true) {
                    result = true;
                }
            }
        }
        return result;
    }

    public boolean indirectEdgeTest(int a, int b) {

        // if there exists a path from node a to node b, return true 

            // implement indirectEdgeTest algorithm here.

            return false;
    }
}

Answer 1

Хм, такой подход звучит ужасно неэффективно.Как насчет этого:

void walk(Node orgin, Set<Node> visited) {
    for (Node n : origin.neighbours) {
        if (!visited.contains(n)) {
            visited.add(n);
            walk(n, visited);
        }
    }
}


boolean hasPath(Node origin, Node target) {
    Set<Node> reachables = new HashSet<Node>();
    walk(origin, reachables);
    return reachables.contains(target);
}

Кроме того, использование матрицы смежности сомнительно для обхода графа, так как вы не можете эффективно выполнять итерацию по соседям узла в разреженном графе.

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

Редактировать: Чтобы уточнить, как лучше всего представить график.Для прямого тестирования ребер предпочтительна матрица смежности.Для тестирования пути разложение на регионы есть.Последнее не тривиально, чтобы поддерживать актуальность при изменении графика, но в литературе могут быть алгоритмы для этого.Альтернативно, списки смежности пригодны для обхода графа и, следовательно, для проверки пути, но они остаются менее эффективными, чем прямая запись разложения на связанные области.Вы также можете использовать наборы смежности для объединения более эффективной итерации соседей в разреженных графах с тестированием ребер в постоянном времени.

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

Answer 2

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

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

Мой код ниже, вероятно, не так эффективен, как мог бы, но сейчас он решает мою проблему. Если у кого-то есть предложения по улучшению, пожалуйста, не стесняйтесь.

Для компиляции: javac Graph.java

Выполнить: java GraphTest

class Graph {

    private java.util.ArrayList<Node> nodeList;
    private int numberOfNodes;

    public Graph(int size) {
        nodeList = new java.util.ArrayList<Node>(size + 1);
        numberOfNodes = size;

        for (int i = 0; i <= numberOfNodes; i++) {
            nodeList.add(new Node());
        }
    }

    public void addEdge(int a, int b) {
        if (a >= 1 && a <= numberOfNodes) {
            if (b >= 1 && b <= numberOfNodes) {
                nodeList.get(a).addNeighbour(nodeList.get(b));
                nodeList.get(b).addNeighbour(nodeList.get(a));
            }
         }
    }

    public void walk(Node origin, java.util.Set<Node> visited) {
        for (Node n : origin.getNeighbours()) {
            if (!visited.contains(n)) {
                visited.add(n);
                walk(n, visited);
            }
        }
    }

    public boolean hasPath(Node origin, Node target) {
        java.util.Set<Node> reachables = new java.util.HashSet<Node>();
        walk(origin, reachables);
        return reachables.contains(target);
    }

    public boolean hasPath(int a, int b) {

        java.util.Set<Node> reachables = new java.util.HashSet<Node>();
        Node origin = nodeList.get(a);
        Node target = nodeList.get(b);
        walk(origin, reachables);
        return reachables.contains(target);       
    }
}

class Node {

    private java.util.Set<Node> neighbours;

    public Node() {
        neighbours = new java.util.HashSet<Node>();
    }

    public void addNeighbour(Node n) {
        neighbours.add(n);
    }

    public java.util.Set<Node> getNeighbours() {
        return neighbours;
    }
}

class GraphTest {

    private static Graph g;

    public static void main(String[] args) {

        g = new Graph(6);

        g.addEdge(1,5);
        g.addEdge(4,1);
        g.addEdge(4,3);
        g.addEdge(3,6);

        printTest(1, 2);
        printTest(1, 4); 
        printTest(6, 1);   
    }

    public static void printTest(int a, int b) {

        System.out.print("Are nodes " + a + " and " + b + " connected?");
        if (g.hasPath(a, b)) {
            System.out.println(" YES.");
        } else {
            System.out.println(" NO.");
        }
    }
}

Answer 3

Ваше решение будет работать, но лучшим решением будет создание связующего дерева из корневого узла "а".Таким образом, в конечном итоге у вас будет только одно дерево для рассмотрения, а не несколько подграфов, в которых отсутствуют только определенные ребра.

Как только вы поймете идею , то как ее реализоватьвы.Предполагая, что вы можете реализовать алгоритм разумным образом, у вас должно быть только одно дерево для поиска связности, что значительно ускорит процесс.