Implementar una prueba de conexión indirecta para la clase de Java Gráfico

Question

Estoy escribiendo una clase en Java para representar una estructura de datos de gráfico. Esto es específico para un grafo no dirigido, no ponderado y su propósito es principalmente para pruebas de borde (es el nodo A conectado al nodo B, ya sea directa o indirectamente).

Necesito ayuda para implementar el método indirectEdgeTest. En el siguiente código, sólo he comentado este método y estoy volviendo falsa por lo que el código se compila como está.

he puesto algo de tiempo en subir con un algoritmo, pero me parece que no puede encontrar nada más simple que esto, y me temo que estoy haciendo que sea más complicado de lo que debe ser:

• prueba primero para una conexión directa
• si no existe ninguna conexión directa desde el nodo A al nodo b:
  • para cada borde i conectado al nodo A:
    • crear un nuevo gráfico que no contiene borde a -> i
    • test nuevo gráfico para la conectividad indirecta entre los nodos i y b

De cualquier pseudocódigo o código real de Java es bienvenido en sus respuestas. Aquí está el código que tengo:

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

Meriton crédito por su respuesta, pero he codificado la idea de trabajo en las clases de Java y una prueba de unidad, por lo que estoy suministrando una respuesta por separado aquí en caso de que alguien está en busca de código reutilizable.

Gracias Meriton. Estoy de acuerdo en que es importante hacer una distinción entre las pruebas de borde directo y pruebas de ruta, y que hay diferentes implementaciones de gráficos que son más adecuados para un determinado tipo de pruebas. En el caso de las pruebas de ruta, parece listas de adyacencia son mucho más eficientes que una representación de la matriz de adyacencia.

Mi código de abajo probablemente no es tan eficiente como podría ser, pero por ahora es resolver mi problema. Si alguien tiene que sugerir mejoras, por favor.

Para compilar: javac Graph.java

Para ejecutar: 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 2

Eh, ese enfoque suena terriblemente ineficiente. ¿Qué pasa con éste:

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

Además, el uso de una matriz de adyacencia es de uso cuestionable para traversal gráfica, ya que no se puede eficientemente iterar sobre los vecinos de un nodo en un gráfico escasa.

Si se utiliza con frecuencia ese método, y el gráfico cambia en raras ocasiones, se puede acelerar consultas por hacer la descomposición en regiones conectadas en la delantera, y almacenar para cada nodo de la región que pertenece. Entonces, dos nodos están conectados si pertenecen a la misma región.

Editar: Para aclarar sobre cómo mejor representan la gráfica. Para la prueba de borde directo, se prefiere una matriz de adyacencia. Para la prueba de ruta, una descomposición en regiones es. El último no es trivial para mantener actual como cambia el gráfico, pero puede haber algoritmos para esto en la literatura. Alternativamente, listas de adyacencia son manipulables por el recorrido gráfico y por lo tanto las pruebas de ruta, pero siguen siendo menos eficiente que grabar directamente la descomposición en regiones conectadas. También puede utilizar conjuntos de adyacencia para combinar la iteración vecino más eficiente en grafos dispersos con las pruebas de canto constante de tiempo.

Tenga en cuenta que también puede almacenar información de forma redundante, mantenimiento, para cada tipo de consulta, una estructura de datos independiente a medida.

Answer 3

Su solución va a funcionar, pero la mejor solución sería construir un árbol de expansión de la raíz "un" nodo. De esta manera es muy probable que tenga un solo árbol que considerar, en lugar de múltiples sub-gráficos que sólo faltan bordes particulares.

Una vez que consigue la idea , cómo ponerlo en práctica depende de usted. Suponiendo que se puede implementar el algoritmo de una manera razonable, sólo debería tener un árbol a buscar la conectividad, lo que acelerar las cosas considerablemente.