Given a directed graph, find out whether there is

Question

I'm trying to solve this problem and i'm fairly new to graphs. I tried BFS to figure this out but i'm not getting the right answer.

What am i doing wrong? Also, is there a better way of doing this, other than the approach i am using.

public static boolean isThereARoute(int[][] graph ,gNode n1 , gNode n2 ) {
    // where can we move? - anywhere where the value of x and y is 1 - else can't move
    // Start with node 1 and then traverse either BFS or DFS to see if the n2 is in the path anywhere

    // using BFS.

    //mark the ones where we can move as true
    boolean[][] canMove= new boolean[graph.length][graph[0].length]; 
    for(int i = 0;i<canMove.length;i++){
        for(int j =0;j<canMove[0].length;j++){
            if(graph[i][j]==-1){
                canMove[i][j] = false;
            }else{
                canMove[i][j] = true;
            }
        }
    }



    // create a queue
    Deque<gNode> queue = new LinkedList<gNode>();
    // insert the first node into the queue
    queue.add(n1);


    while(!queue.isEmpty()){
        gNode top = queue.poll();
        int x = top.x1;
        int y = top.y1;
        // only check the ones where we can go

        if( ( top.x1>=0 && top.x1<= graph.length-1) && (top.y1>=0 && top.y1<= (graph[0].length-1)) ){

            if(canMove[top.x1][top.y1]){

                if((top.x1 == n2.x1) && (top.y1 == n2.y1)){
                    // found our node;
                    return true;
                }

                // else haven't found any - add the nodes to the queue // allowed diagonals as well// therefore for each node 
                // there can be 8 neighbors
                queue.add(new gNode(x-1,y));
                queue.add(new gNode(x,y-1));
                queue.add(new gNode(x+1,y));
                queue.add(new gNode(x,y+1));
                queue.add(new gNode(x-1,y-1));
                queue.add(new gNode(x-1,y+1));
                queue.add(new gNode(x+1,y+1));
                queue.add(new gNode(x+1,y-1));

            }

        }

    }

    return false;
}

And for the check-

        int[][] graphD = new int[][]{

        {-1, 1,-1,-1,-1},
        {-1,-1, 1,-1,-1},
        {-1,-1, 1, 1,-1},
        {-1,-1,-1,-1,-1},
        { 1,-1, 1,-1,-1}
    };

    ArrayList<gNode> nodes = new ArrayList<gNode>();
    nodes.add(new gNode(0,0));//node A
    nodes.add(new gNode(1,1)); // node B
    nodes.add(new gNode(2,2)); // node C
    nodes.add(new gNode(3,3)); // node D
    nodes.add(new gNode(4,4)); // node E

    /**
     *  A->b
     * B->C
     * C->C
     * C->D
     * E-A
     * 
     */ 

    System.out.println(" is A -B connected?"+isThereARoute(graphD, nodes.get(0), nodes.get(1)));
    System.out.println(" is A -D connected?"+isThereARoute(graphD, nodes.get(0), nodes.get(3)));
    System.out.println(" is C -A connected?"+isThereARoute(graphD, nodes.get(3), nodes.get(0)));
    System.out.println(" is A -E connected?"+isThereARoute(graphD, nodes.get(0), nodes.get(4)));
    System.out.println(" is C -C connected?"+isThereARoute(graphD, nodes.get(2), nodes.get(2)));

Answer 1

I would say that BFS is the right algorithm to apply here, so it's just a problem with your BFS code. It looks like you're confused about how graphs are represented in an Adjacency Matrix.

            if((top.x1 == n2.x1) && (top.y1 == n2.y1)){
                // found our node;
                return true;
            }

This is checking if a specific entry in the adjacency matrix (an edge) has been reached, but you're just supposed to be checking if a given node is reachable.

You should change your gNode representation to use a single index (or just drop it and use an int instead), and do your BFS from the first node based off the adjacency matrix values.

If you need some additional help with understanding the algorithm / data structures, this page seems like a good reference: Adjacency matrices, BFS, DFS.

Answer 2

Approach to this can be.

1. BFS (most simple and efficient too)
2. Transitive closure (found using Floyd-Warshall algorithm).

Answer 3

I'm not good at debugging more than 10-20 lines of code if I'm not really familiar with the language. However, I can tell you that there is a better overall approach to tell if there is a path between two nodes x and y, instead of just BFS or DFS starting from x. Namely, you can do BFS starting from x in the forward direction, and simultaneously do BFS from y in the reverse direction. I.e. starting with k=1, you find all vertices you can reach moving forward from x using a path of <= k edges, and you find all vertices you can reach moving reverse-direction from y using <= k edges, and you apply basic BFS principle to increase k by 1. For each k, you hash the vertices you can reach from x, and hash the vertices you can reach from y, and if you get a match w between the two sets then w is a midpoint in a path from x to y, so a path exists. The reason why this is preferable to BFS starting from x is that if your path from x to y has length K, then BFS starting at x will find all nodes reachable in K steps, which may be a huge set (worst-case exponential in K). But if you do it the way I proposed, then you can terminate when you reach k >= K/2, and the 2 sets of vertices reachable in K/2 steps will often be much smaller than a set of vertices reachable in K steps. So, when a path exists, you will typically find it much faster the way I proposed.