Mettre en œuvre un test indirect de connectivité pour la classe Java Graphique

Question

J'écris une classe en Java pour représenter une structure de données graphique. Ceci est spécifique à une non-orienté, le graphique non pondérée et son but est principalement pour les essais de bord (noeud A est relié au noeud B, soit directement, soit indirectement).

je besoin d'aide mise en œuvre de la méthode indirectEdgeTest. Dans le code ci-dessous, je n'ai commenté cette méthode et je retourne faux de sorte que le code compile en l'état.

J'ai mis un peu de temps en venir avec un algorithme, mais je ne peux pas sembler trouver quelque chose de plus simple que cela, et je crains que je fais plus compliqué qu'il doit être:

• premier test pour une connexion directe
• si aucune connexion directe existe depuis le noeud d'un noeud à b:
  • i pour chaque arête reliée au noeud a:
    • créer un nouveau graphique qui ne contient pas de bord a -> i
    • nouveau test graphique pour la connectivité indirecte entre les nœuds i et b

Soit le code Java ou pseudo-réel est le bienvenu dans vos réponses. Voici le code que j'ai:

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 I de crédit pour sa réponse, mais je l'ai codé l'idée en cours de travail Java et un test unitaire, donc je fournir une réponse distincte ici au cas où quelqu'un est à la recherche de code réutilisable.

Merci Meriton. Je suis d'accord, il est important de faire une distinction entre les essais de bord direct et les tests de chemin, et qu'il existe différentes implémentations de graphiques qui sont mieux adaptés à un type particulier de test. Dans le cas des tests de chemin, il semble listes de contiguïté sont beaucoup plus efficaces qu'une représentation matricielle de contiguïté.

Mon code ci-dessous est probablement pas aussi efficace qu'il pourrait l'être, mais pour l'instant il est de résoudre mon problème. Si quelqu'un a des améliorations à suggérer, s'il vous plaît ne hésitez pas.

Pour compiler: javac Graph.java

Pour exécuter: 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, cette approche semble terriblement inefficace. Qu'en est celui-ci:

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

En outre, en utilisant une matrice de contiguïté est d'utilisation douteuse pour le graphique traversal, puisque vous ne pouvez pas efficacement itérer sur les voisins d'un nœud dans un graphe clairsemé.

Si cette méthode est fréquemment utilisée, et le graphique change rarement, vous pouvez accélérer les requêtes par faire la décomposition en régions connectées à l'avant, et à stocker pour chaque noeud de la région elle appartient. Ensuite, deux noeuds sont connectés si elles appartiennent à la même région.

Edit: Pour clarifier sur la façon de mieux représenter le graphique. Pour les essais de bordure directe, une matrice de contiguïté est préférée. Pour les tests de chemin, une décomposition en régions est. Ce dernier n'est pas trivial de se tenir au courant que le graphique change, mais il peut y avoir des algorithmes pour cela dans la littérature. Sinon, les listes de contiguïté sont utilisables pour le graphique et donc traversal tests de chemin, mais ils restent moins efficaces que l'enregistrement directement la décomposition dans des régions connectées. Vous pouvez également utiliser des ensembles de contiguïté pour combiner l'itération voisin plus efficace dans les graphiques clairsemés avec des essais de bord à temps constant.

Gardez à l'esprit que vous pouvez également stocker des informations de manière redondante, tenue, pour chaque type de requête, une mesure, la structure de données séparée.

Answer 3

Votre solution fonctionne, mais une meilleure solution serait de construire un arbre allant de la racine « un » noeud. De cette façon, vous finirez par avoir un seul arbre à considérer, au lieu de sous-graphes multiples qui ne manquent bords particuliers.

Une fois que vous get idée, comment l'implémenter est à vous. En supposant que vous pouvez mettre en œuvre l'algorithme de manière raisonnable, vous ne devriez avoir un arbre à la recherche de la connectivité, ce qui permettrait d'accélérer considérablement les choses.