BitSet out of memory Java

Question

I am using BitSet to keep track whether nodes in a Graph have been visited using DFS method. For this purpose I have created a BitSet[] array. The BitSets themselves can be between 100.000-500.000 entries.

This is the code I am using.

   public void tc() {
//        if (scc_cache_valid)
//           return;
        marked2 = new BitSet[node_count];
        for (int v = 0; v < node_count; v++) {
            //if (marked2[v] == null)
                marked2[v] = new BitSet(edge_count);
            System.out.println("aaa" + marked2[v].size());
            for (int w : children.get(v)) {
                if (!marked2[v].get(w))
                    dfs(v, w);
            }
        }
    }

    public void tc(int v) {
//        if (scc_cache_valid && marked2[v] != null)
//            return;

//        marked2 = new BitSet[node_count];
//        for (int v = 0; v < node_count; v++) {
        if (marked2[v] == null)
            marked2[v] = new BitSet(node_count);
        System.out.println(marked2[v].size());

        for (int w : children.get(v)) {
                if (!marked2[v].get(w))
                    dfs(v, w);
            }
//        }
    }

    public boolean reachable(int v, int w) {
        return marked2[v].get(w);
    }

    private void dfs(int v, int w) {
        marked2[v].set(w, true);
        System.out.println(marked2[v].length());

        for (int z : children.get(w)) {
            if (!marked2[v].get(z))
                dfs(v, z);
        }
    }

Unfortunately I am running out of heap. Is there a better (more memory efficient) solution to this problem ?

Thank You.

Answer 1

I think your DFS algorithm is incorrect.

• A classic DFS algorithm for a tree doesn't require a bitmap at all.
• A classic DFS algorithm for a DAG or a full graph requires a single bitmap with a one bit for each node in the graph. This assumes that there is a (dense) one-to-one mapping from nodes to integers; e.g. node numbers. If not, then it is conventional to use a HashSet<Node>.

In either case, the space requirement is O(N) rather than O(N^2).

A pseudo-code algorithm for the DAG / graph case is:

 dfs(root) = dfs0(root, new Set());
 dfs0(node, visited) = 
      if !visited.contains(node):
          visited.add(node)
          // do stuff for node
          foreach n in node.children:
              dfs0(n, visited)

Note: there is only one Set object used in the traversal.