Implementare un indiretto test di connettività per la classe Java Graph

Question

Sto scrivendo una classe in Java per rappresentare una struttura di dati grafico. Questo è specifico per una, grafo pesato non orientato ed è scopo è principalmente per i test bordo (nodo A è collegato al nodo B, direttamente o indirettamente).

Ho bisogno di aiuto attuazione del metodo indirectEdgeTest. Nel codice qui sotto, ho commentato solo questo metodo e sto tornando falso in modo che il codice verrà compilato così com'è.

io ho messo un po 'di tempo in arrivo con un algoritmo, ma non riesco a trovare niente di più semplice di questo, e temo che sto facendo più complicato di quello che deve essere:

• primo test per una connessione diretta
• se non esiste collegamento diretto dal nodo A al nodo b:
  • per ogni spigolo ho collegato al nodo A:
    • creare un nuovo grafico che non contiene bordo di una -> i
    • Test nuovo grafico per la connettività indiretta tra i nodi i e b

In entrambi i pseudocodice o codice effettivo Java è il benvenuto nelle vostre risposte. Ecco il codice che ho:

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

I Meriton di credito per la sua risposta, ma ho codificato l'idea in lavorazione classi Java e un test di unità, quindi sto fornendo una risposta separata qui nel caso qualcuno è alla ricerca di codice riutilizzabile.

Grazie Meriton. Sono d'accordo che è importante fare una distinzione tra test bordo diretto e test percorso, e che vi sono diverse implementazioni di grafici che sono più adatti per un particolare tipo di test. In caso di prova di percorso, sembra liste di adiacenza sono molto più efficiente di una rappresentazione matrice di adiacenza.

Il mio codice qui sotto non è probabilmente il più efficiente come potrebbe essere, ma per ora sta risolvendo il mio problema. Se qualcuno ha i miglioramenti da suggerire, non esitate.

Per compilare: javac Graph.java

Per eseguire: 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

Erm, che l'approccio suona terribilmente inefficiente. Che dire di questo:

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

Inoltre, utilizzando una matrice di adiacenza è di uso discutibile per grafico attraversamento, dal momento che non è possibile in modo efficiente iterare sopra i vicini di un nodo in un grafo sparse.

Se questo metodo è usato frequentemente, e il grafico cambia raramente, è possibile velocizzare le query da fare la scomposizione in regioni collegati davanti, e memorizzare, per ogni nodo della regione a cui appartiene. Poi, due nodi sono collegati se appartengono alla stessa regione.

Modifica: Per chiarire sul modo migliore di rappresentare il grafico. Per il test diretto bordo, una matrice di adiacenza è preferito. Per il test percorso, una decomposizione in regioni è. Quest'ultimo non è banale per mantenere corrente come cambia il grafico, ma ci possono essere algoritmi per questo in letteratura. In alternativa, liste di adiacenza sono funzionali per grafico attraversamento e quindi test percorso, ma rimangono meno efficiente di registrazione direttamente la decomposizione in regioni collegate. È anche possibile utilizzare i set di adiacenza di combinare più efficiente iterazione prossimo in grafi sparsi con test bordo a tempo costante.

Tieni presente che è anche possibile memorizzare le informazioni in modo ridondante, conservazione, per ogni tipo di query, una su misura, struttura di dati separati.

Answer 3

La soluzione funziona, ma una soluzione migliore sarebbe quella di costruire un albero di copertura dalla radice "a" nodo. In questo modo vi troverete infine avere un solo albero di prendere in considerazione, invece di più sotto-grafici che solo mancano bordi particolari.

Una volta ottiene l'idea , modalità di implementazione spetta a voi. Supponendo che è possibile implementare l'algoritmo in modo ragionevole, si dovrebbe avere un solo albero per la ricerca per la connettività, che sarebbe accelerare le cose in modo considerevole.