[FIXED] How to speed up Depth First Search method?

Issue

I'm trying to do a Depth First Search of my graph, and something is slowing it down quite a lot and I'm not sure what.

Here is my Bag code:

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Bag<Item> implements Iterable<Item> {
    private Node<Item> first;    // beginning of bag
    private Node<Item> end;
    private int n;               // number of elements in bag
    public int label;
    public int edges;

    public static class Node<Item> {
        private Item item;                  
        private Node<Item> next;
        public int label;
        public int edges;
    }

    public Bag() {
        first = null;                           // empty bag initialized
        end = null;
        n = 0;
    }
    
    public void add(Item item) {
        if (n==0) {
            Node<Item> head = new Node<Item>();     // if bag is empty
            first = head;
            end = head;
            head.item = item;           // new node both first and end of bag
            edges++;
            n++;
        }
        else {
            Node<Item> oldlast = end;           // old last assigned to end of node
            Node<Item> last = new Node<Item>();
            last.item = item;
            oldlast.next = last;                // new node added after old last
            end = last;
            n++;                                    // size increased
            edges++;
        }
    }

    public Iterator<Item> iterator()  {
        return new LinkedIterator(first);           // returns an iterator that iterates over the items in this bag in arbitrary order
    }


    public class LinkedIterator implements Iterator<Item> {
        private Node<Item> current;

        public LinkedIterator(Node<Item> first) {
            current = first;                                            // iterator starts at head of bag
        }

        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();             // if there is next item, current is moved to next
            Item item = current.item;
            current = current.next; 
            return item;                                        // item is returned
        }
    }
}

Here is my driver:

import java.util.ArrayList;
import java.util.Random;

public class Driver {
    
    public static ArrayList<Integer> randomNum(int howMany) {
        ArrayList<Integer> numbers = new ArrayList<Integer>(howMany);   
        Random randomGenerator = new Random();
        while (numbers.size() < howMany) {
            int rand_int = randomGenerator.nextInt(10000);
            if (!numbers.contains(rand_int)) {
                numbers.add(rand_int);
            }
        }
        return numbers;
    }
    
    public static void main(String[] args) {
        ArrayList<Integer> num = randomNum(100);
        Graph G = new Graph(num);
        System.out.println("The length of longest path for this sequence with graph is: " +  G.dfsStart(num));
    }
}

I send an ArrayList of random integers to my dfsStart method from the driver, which looks at all the different paths for each starting node in my graph. my DepthFirstSearch method calls the getAdjList for each starting node to find its neighbors using my Bag adj, and then works its way down each path before backtracking.

Here is my Graph code, containing my longest path method:

import java.util.ArrayList;
import java.util.NoSuchElementException;

public class Graph {

    public final int V;                     // initializing variables and data structures
    public Bag<Integer>[] adj;
    public int longestPath;
    
    public Graph(ArrayList<Integer> numbers) {
        
        try {
            longestPath = 0;
            this.V = numbers.size();
            adj = (Bag<Integer>[]) new Bag[V];                      // bag initialized
            for (int v = 0; v < V; v++) {
                adj[v] = new Bag<Integer>();                            
            }
            for (int i = 0; i < V; i++) {
                adj[i].label = numbers.get(i);
                int j = (i + 1);
                while (j < numbers.size()) {
                    if (numbers.get(i) < numbers.get(j)) {
                        addEdge(i, numbers.get(j));
                    }
                    j++;
                }
            }
        }
        catch (NoSuchElementException e) {
            throw new IllegalArgumentException("invalid input format in Graph constructor", e);
        }
    }

    
    public void addEdge(int index, int num) {                                           
        adj[index].add(num);            
    }

    public int getIndex(int num) {
        for (int i = 0; i < adj.length; i++) {
            if (adj[i].label == num) {
                return i;
            }
        }
        return -1;
        
    }
    
    public Bag<Integer> getAdjList(int source) {
        Bag<Integer> adjList = null;
        for (Bag<Integer> list : adj) {
            if (list.label == source) {
                adjList = list;
                break;
            }
        }
        return adjList;
    }
    
    public int dfsStart(ArrayList<Integer> numbers) {
        for (int i=0;i<numbers.size();i++) {
            // Print all paths from current node
            depthFirstSearch(numbers.get(i),new ArrayList<>(300));
        }
        return longestPath;
    }
    
    public void depthFirstSearch(int src, ArrayList<Integer> current) {
        current.add(src);
        Bag<Integer> srcAdj = getAdjList(src);
        if (srcAdj.size() == 0) {
            // Leaf node
            // Print this path
            longestPath = Math.max(longestPath, current.size());
        }
        for (int links : srcAdj) {
            depthFirstSearch(links, current);
        }
        current.remove(current.size()-1);
    }

}

I believe the suggestion below helped get rid of the error, but it is still unbelievably slow when trying to find the longest path in a graph of more than 150 vertices.

Solution

Even for a small dense graph there can be many unique paths from a src node. I tested for this input [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25] there are 16777216 unique paths from all nodes. So you can expect OOM for bigger inputs. one way is to update the longestPath as soon as a path is found instead of adding it to the list.

Change this to later.

addtoCount(current.size());

to

longestPath = Math.max(longestPath, current.size());

Make sure longestPath is global and initialized to 0 before every test case.

Answered By - Turtle

Answer Checked By - Robin (PHPFixing Admin)