Speeding up this Tarjan's algorithm

Question

I'm implementing an algorithm that traverses a graph of nodes (after a given input) and outputs 3 things:

1. Number of Strongly connected components
2. Size of the largest strongly connected component

3. (And here I think is the step that slows down my algorithm) The number of SCC's that are ONLY connected between them.

   This means that, for every node in that SCC, none of them has a path to other nodes outside the SCC. Only other nodes outside of the SCC connect to them. Like they are isolated inside the SCC.

   If this isn't clear, please tell me so I can rephrase.

Here's the code and how to use it:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class Tarjan {
 int time;
 static int N;
 static int P;
 List<Integer>[] graph;
 int[] lowlink;
 boolean[] used;
 List<Integer> stack;
 List<List<Integer>> components;
 int maxSize = 0;
 private int getMaxSize() {
 return maxSize;
 }
 public List<List<Integer>> scc(List<Integer>[] graph) {
 int n = graph.length;
 this.graph = graph;
 lowlink = new int[n];
 used = new boolean[n];
 stack = new ArrayList<Integer>();
 components = new ArrayList<List<Integer>>();
 for (int u = 0; u < n; u++)
 if (!used[u])
 dfs(u);
 return components;
 }
 void dfs(int u) {
 lowlink[u] = time++;
 used[u] = true;
 stack.add(u);
 boolean isComponentRoot = true;
 for (int v : graph[u]) {
 if (!used[v])
 dfs(v);
 if (lowlink[u] > lowlink[v]) {
 lowlink[u] = lowlink[v];
 isComponentRoot = false;
 }
 }
 if (isComponentRoot) {
 List<Integer> component = new ArrayList<Integer>();
 while (true) {
 int k = stack.remove(stack.size() - 1);
 component.add(k);
 lowlink[k] = Integer.MAX_VALUE;
 if (k == u)
 break;
 }
 int size = component.size();
 if (size > this.maxSize)
 maxSize = size;
 components.add(component);
 }
 }
 public static void main(String[] args) {
 BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
 try {
 String s = read.readLine();
 String[] parts = s.split(" ");
 String part1 = parts[0];
 String part2 = parts[1];
 N = Integer.parseInt(part1);
 P = Integer.parseInt(part2);
 } catch (IOException e) {
 e.printStackTrace();
 }
 int counter = 0;
 @SuppressWarnings("unchecked")
 List<Integer>[] g = new List[N];
 for (int i = 0; i < g.length; i++) {
 g[i] = new ArrayList<Integer>();
 }
 while (counter < P) {
 String s;
 try {
 s = read.readLine();
 String[] parts = s.split(" ");
 String part1 = parts[0];
 String part2 = parts[1];
 int x = Integer.parseInt(part1);
 int y = Integer.parseInt(part2);
 g[x - 1].add(y - 1);
 } catch (IOException e) {
 e.printStackTrace();
 }
 counter++; 
 }
 Tarjan t = new Tarjan();
 List<List<Integer>> components = t.scc(g);
 System.out.println(components.size());
 /* Check note 1 below that explains this part of the algorithm */
 int isolatedScc = 0;
 int contains = 1;
 for (List<Integer> sccList : components) {
 int i;
 contains = 1;
 for (i = 0; i < g.length; i++) {
 if (sccList.contains(i))
 continue;
 else {
 for (Integer nodeInScc : sccList) {
 List<Integer> nodesConnectedToTheNodesInSCC = g[nodeInScc];
 if (nodesConnectedToTheNodesInSCC.contains(i)) {
 contains = 0;
 break;
 }
 }
 }
 }
 if (contains == 1)
 isolatedScc++;
 }
 System.out.println(t.getMaxSize());
 System.out.println(isolatedScc);
 }
}

To test the program, simply run it. It will wait for your input. The first two number you input will define the number of nodes and the number of connection. The rest of the lines define the connections between nodes.

5 4
1 2
1 3
2 3
4 1

In this example we have: number of nodes: 5. Number of connections between nodes: 4 The rest of the lines are the 4 connections between the 5 nodes.

Note 1:

This is the part of the algorithm that I think slows it down a lot. Basically what I'm doing here is, for every node in the SCCS, check any node that isn't inside that SCC and check any of them has a connection to any node outside of the SCC (that is, a path between that node to the node outside of the SCC). If so, then break. If it reaches the end of the loop, than that situation doesn't happen. So increase a counter

Is there any possible way I can speed up this thing? I compiled it with jdk1.6.

• Nobody moving away from SE: Your sentences This means that, for every node in that SCC, none of them has a path to other nodes outside the SCC. Only other nodes outside of the SCC connect to them. seem to contradict each other. Please clarify this.
• luispcosta: Uh, im not native english so i have a had a hard time explaining that xD. What i want to mean is, an SCC where the nodes ONLY connect to the inside that SCC. Its like they are isolated. Other nodes (outside of that SCC) can reach them, but the nodes of that SCC can ONLY reach eachother (like in cycle).
• G. Bach: I don't understand the third point, either. And when you say "connection", I assume you mean "edge"?
• Nobody moving away from SE: @riotvan: It will be hard to discuss if even the basic understanding is missing. But still you could try drawing images that explain what you mean.
• luispcosta: i.imgur.com/fYZCCPM.png This is what i want to do. The nodes in the SCC on red, have edges only to them selfs, not to any node outside the SCC. This is want i want to calculate. The number of groups where this happens

Answer 1

Generics

Java Generics will not accept the declaration: List<Integer>[] You cannot have an array of a generically typed component. There are ways to make it neater, but, you should be using List<List<Integer>> in a general case.

Variable names

Variables like n, t, N, P, u, etc. are not helpful. They make the code hard to read and understand. Use descriptive variable names. It helps. A lot!

Variable Scope

Static non-final variables are almost always a sign of bad ObjectOriented design:

static int N;
static int P;

These should be final instance variables on your class, or something, but setting them in the main method and using them in an instance method is backward. It also means you can only have one (working) instance of your graph.

Object Structure

Your class is not a class.... it is a procedural mashup. You have a procedural system for setting up your graph (which is contained in two Lists), and then you create a TarJan instance for no particular reason other than that the methods are not static.... You then delegate some work to the TarJan instance, pull the results back in to the main method, and then procedurally complete the process.

This is a poor design.

The graph should be self-contained in a single instance object, and its data structure should all be internal.

Java Functions should also have a single-responsibility defined in the function: do one thing, and one thing well.

Your main method should look more like:

public void main (String[] args) {
 Graph graph = buildGraphFromStdIn();
 System.out.println("Component Count: " + graph.getComponentCount());
 System.out.println("Largest SCC Size: " + graph.getLargestComponentSize());
 ....
}

Performance

Performance should normally come after functionality. At the moment, your code needs a fix-up with respect to conventions and style. As you go through the code mobing things in to neat compartments, you will likely find the performance improves simply because you structure things better, and notice where things go wrong.

At the moment, it is pretty hard to see what is happening, so I am not particularly inclined to dig though it and guess what's going wrong (performance wise).

• luispcosta: Yeah i know about that, but for this assignment, i just have to submit a simple code like this. The design or the architecture wont be evaluated.
• RoToRa: @riotvan Just because the architecture won't be evaluated doesn't mean you have to write badly structured code.