Implement an Indirect Connectivity Test for Java Graph class

Question

I'm writing a class in Java to represent a Graph data structure. This is specific to an undirected, unweighted graph and it's purpose is mainly for edge testing (is node A connected to node B, either directly or indirectly).

I need help implementing the indirectEdgeTest method. In the code below, I've only commented this method and I'm returning false so the code will compile as-is.

I have put some time into coming up with an algorithm, but I can't seem to find anything more simple than this, and I fear I'm making it more complicated than it needs to be:

- 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

Either pseudocode or actual Java code is welcome in your answers. Thanks for your help. Here's the code I have:

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

Your solution will work, but a better solution would be to construct a spanning tree from the root "a" node. This way you will eventually have only one tree to consider, instead of multiple sub-graphs that only are missing particular edges.

Once you get the idea, how you implement it is up to you. Assuming you can implement the algorithm in a reasonable manner, you should only have one tree to search for connectivity, which would speed things up considerably.

Answer 2

Erm, that approach sounds horribly inefficient. What about this one:

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

Also, using an adjacency matrix is of questionable use for graph traversal, since you can not efficiently iterate over a node's neighbours in a sparse graph.

If that method is frequently used, and the graph changes rarely, you can speed queries up by doing the decomposition into connected regions up front, and storing for each node the region it belongs to. Then, two nodes are connected if they belong to the same region.

Edit: To clarify on how to best represent the graph. For direct edge testing, an adjacency matrix is preferred. For path testing, a decomposition into regions is. The latter is not trivial to keep current as the graph changes, but there may be algorithms for this in the literature. Alternatively, adjacency lists are serviceable for graph traversal and thus path testing, but they remain less efficient than directly recording the decomposition into connected regions. You can also use adjacency sets to combine the more efficient neighbor iteration in sparse graphs with constant-time edge testing.

Keep in mind that you can also store information redundantly, keeping, for each kind of query, a tailored, separate data structure.

Answer 3

I credit meriton for his or her answer, but I've coded the idea into working Java classes and a unit test, so I'm supplying a separate answer here in case anyone is looking for reusable code.

Thanks meriton. I agree it's important to make a distinction between direct edge testing and path testing, and that there are different implementations of graphs that are better suited to a particular type of testing. In the case of path testing, it seems adjacency lists are much more efficient than an adjacency matrix representation.

My code below is probably not as efficient as it could be, but for now it is solving my problem. If anyone has improvements to suggest, please feel free.

To compile: javac Graph.java

To execute: 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.");
        }
    }
}