Check if path exists directed graph, without using collection

Question

I have written code to find whether the path exists between source and destination in a directed graph. I have used BFS and instead of ArrayList or queue. I have written my own helper class.

Please let me know how the code can be improved.

public class Graph {

    private int numVertex;
    // Helper class, which can act like Adjacency List or Queue for BFS search.
    private HelperClass[] adjList;

    public Graph(int n) {
        numVertex = n;
        adjList = new HelperClass[n];
        for (int i = 0; i < n; i++) {
            adjList[i] = new HelperClass();
        }
    }

    public void setAdjacencyList(HelperClass[] adjList) {
        this.adjList = adjList;

    }

    // Assuming that source and destination will be in the range of vertices.
    public boolean isPathExists(int source, int destination) {
        if (source == destination)
            return true;
        // else do BFS until the destination is found or all the nodes are
        // visited.
        HelperClass hc = new HelperClass();
        boolean[] isVisited = new boolean[numVertex];
        hc.add(source);
        isVisited[source] = true;
        while (!hc.isEmpty()) {
            int current = hc.poll();
            if (current == destination) {
                return true;
            }
            int leftIndex = adjList[current].first;
            int rightIndex = adjList[current].last;
            while (leftIndex < rightIndex) {
                int temp = adjList[current].array[leftIndex++];
                if (!isVisited[temp]) {
                    hc.add(temp);
                }

            }
        }
        return false;
    }

    public static class HelperClass {
        // assuming the maximum array size will not be more than 10000.
        int[] array = new int[10000];
        int first = 0;
        int last = 0;

        public void add(int x) {
            array[last++] = x;
        }

        public int poll() {
            if (!isEmpty()) {
                return array[first++];
            } else {
                return -1;
            }
        }

        public boolean isEmpty() {
            return first == last ? true : false;
        }

    }

}

Answer 1

Performance

HelperClass used a fix amount memory, due to the predetermined array size. This looks like a waste.

Single responsibility principle

HelperClass is used in 2 different ways:

1. As a queue, that can grow at its end and shrink at its beginning

2. As an array to store the neighbors of each vertex

I suspect this dual use has lead to the terrible meaningless name of this class.

Instead of doing different things, it's recommended to design classes that do one thing and do it well. This is called the single responsibility principle, one of the first crucial considerations when creating a new class.

If you want to write your own queue, that's fine, but focus on its most important responsibility, which is efficient push, poll, isEmpty operations.

When your class has a single responsibility, naming becomes easier too, often obvious.

For the storage of neighbors, it's unclear what you really need. You haven't shared how they are initialized, so it's impossible to comment on that. A fixed array might be good enough, who knows.

Pointless Graph constructor

The constructor initializes the vertices empty, with no neighbors. That seems rather useless. Perhaps you want to move the functionality of the setAdjacencyList method inside the constructor.

Answer 2

HelperClass

That's a bad name. Why don't you use PathQueue (that's also a bad name, but whatever) or something - try to actually describe what it is.

It is also pretty silly to make such a massive array (is there a reason you assume that will be a good size?) and not to allow it to resize. A resizing array is pretty easy.

public static class InformativeName {
    int[] array = new int[10];
    int first = 0;
    int last = 0;
    private int capacity = 10;

    public void add(int x) {
        if (isFull()) {
            resize();
        }
        array[last++] = x;
    }

    public int poll() {
        if (!isEmpty()) {
            return array[first++];
        } else {
            return -1;
        }
    }

    public boolean isEmpty() {
        return first == last;
    }

    private boolean isFull() {
        return last >= (capacity - 1);
    }

    private void resize() {
        // If you can use this, do
        // array = Arrays.copyOf(array, capacity*2);
        // otherwise do this
        int[] temp = new int[capacity*2];
        System.arraycopy(array, 0, temp, 0, capacity);
        array = temp;
        capacity *= 2;
    }

}

You'll notice that I also changed the logic in isEmpty - as it turns out, first == last ? true : false is the exact same thing as first == last.

You can use whatever mechanism you want for resizing (doubling isn't a fantastic solution, and being full isn't necessarily a great metric) but this should be enough to get started on that.

I'm not a huge fan of array, first, and last being public, but I get why they're that way. I don't think that's a huge point, so I didn't change that.