Implementieren eines indirekten Verbindungstest für Java Graph Klasse

Question

Ich bin eine Klasse in Java zu schreiben, um eine Graphdatenstruktur darstellen. Dies ist spezifisch für eine ungerichtete, ungewichtete Diagramm und seinen Zweck ist in erster Linie für die Kantenprüfung (ist der Knoten A mit dem Knoten B, die entweder direkt oder indirekt).

Ich brauche Hilfe, um das indirectEdgeTest Verfahren. In dem folgenden Code, habe ich diese Methode nur kommentiert und ich bin false zurückgibt, so wird der Code kompiliert, wie sie ist.

Ich habe einige Zeit in der kommenden mit einem Algorithmus setzen, aber ich kann nicht scheinen, nichts einfacher als das zu finden, und ich fürchte, ich mache es komplizierter, als es sein muss:

• Test zunächst für eine direkte Verbindung
• , wenn keine direkte Verbindung besteht vom Knoten A zum Knoten b:
  • i für jede Kante verbunden A Knoten:
    • ein neues Diagramm erstellen, die keine Kante a enthalten -> i
    • Test neue Graph für indirekte Verbindungen zwischen den Knoten i und b

So oder Pseudo-Code oder tatsächlicher Java-Code ist willkommen in Ihren Antworten. Hier ist der Code, den ich habe:

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 Kredit meriton für seine Antwort, aber ich habe die Idee in der Arbeits Java-Klassen und einen Komponententest codiert, so dass ich eine separate Antwort hier falls jemand Versorgung bin für wieder verwendbaren Code suchen.

Danke meriton. Ich bin damit einverstanden, es ist wichtig, eine Unterscheidung zwischen direkter Kantenprüfung und Pfadtest zu machen, und dass es verschiedene Implementierungen von Graphen, die besser auf eine bestimmte Art von Tests geeignet sind. Im Fall des Pfadtest scheint es Adjazenzlisten sind viel effizienter als eine Adjazenzmatrix Darstellung.

finden Sie unten Mein Code ist wahrscheinlich nicht so effizient, wie es sein könnte, aber jetzt ist es mein Problem ist zu lösen. Wenn jemand Verbesserungen zu der Annahme, wenden Sie sich.

So kompilieren: javac Graph.java

Zur Ausführung: 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, klingt dieser Ansatz schrecklich ineffizient. Was ist diese:

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

Auch ist eine Adjazenzmatrix mit fragwürdiger Verwendung für Graph Traversal, da kann man nicht effizient Iterierte über einen Nachbarn des Knotens in einem spärlichen Graphen.

Wenn das Verfahren häufig verwendet wird, und der Graph selten ändert, können Sie Abfragen beschleunigen, indem die Zerlegung in verbundene Bereiche vorne, und den Bereich für jeden Knoten zu speichern, um sie gehört. Dann werden zwei Knoten verbunden sind, wenn sie auf der gleichen Region gehören.

Edit: Um zu klären, wie man am besten die Grafik darstellen. Für die direkte Kantenprüfung wird eine Adjazenzmatrix bevorzugt. Für Pfadtest ist eine Zerlegung in Regionen. Letzteres ist nicht trivial Strom zu halten, wie die Grafik ändert, aber es kann für diesen in der Literatur sein Algorithmen. Alternativ sind Adjazenzlisten für Graph Traversal gewartet werden und somit Pfadtest, aber sie bleiben weniger effizient als direkt die Zersetzung in zusammenhängende Bereiche der Aufnahme. Sie können auch adjacency Sets zu kombinieren, um die effizientere Nachbar Iteration in spärlich Graphen mit konstanter Zeit Kantenprüfung verwenden.

Beachten Sie, dass Sie auch redundant Informationen speichern können, behalten, für jede Art von Abfrage, eine maßgeschneiderte, eigene Datenstruktur.

Answer 3

Ihre Lösung funktionieren wird, aber eine bessere Lösung wäre, einen Spanning-Tree von der Wurzel zu konstruieren „ein“ Knoten. Auf diese Weise werden Sie schließlich nur ein Baum, anstelle von mehreren Untergraphen zu betrachten, die nur bestimmte Kanten fehlen.

Nach dem get the idea , wie Sie implementieren es Ihnen liegt. Vorausgesetzt, dass Sie den Algorithmus in einer angemessenen Art und Weise implementieren können, sollten Sie nur einen Baum für die Konnektivität zu suchen, die Dinge beschleunigen würde erheblich.