2

I am learning algorithms and data structures from this awesome resource Algorithms. Rather than doing dry reading I am trying to re-write all the code myself so that I can learn coding as well as design decisions at the same time(like: what APIs to expose and how to do assertions etc.) so, below is my simplified code which is mostly copied from this version.

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Graph;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Queue;


public class CC {
  private int count;
  private boolean[] marked;
  private int[] id;

  public CC(Graph G) {
    marked = new boolean[G.V()];
    id = new int[G.V()];
    count = 0;
    for (int v = 0; v < G.V(); v++) {
      if (!marked[v]) {
        dfs(G, v);
        count++;
      }
    }
  }

  public int count() {
    return count;
  }

  public int id(int v) {
    return id[v];
  }

  private void dfs(Graph G, int u) {
    if (!marked[u]) {
      marked[u] = true;
      id[u] = count;
      for(int v : G.adj(u)) {
        dfs(G, v);
      }
    }
  }

  public static void main(String[] args) {
    In in = new In(args[0]);
    Graph G = new Graph(in);
    CC cc = new CC(G);

    // number of connected components.
    int M = cc.count();
    StdOut.println(M + " components");

    // Get number of vertices in each component.
    Queue<Integer>[] components = (Queue<Integer>[]) new Queue[M];
    for (int i = 0; i < M; i++) {
      components[i] = new Queue<Integer>();
    }
    for (int v = 0; v < G.V(); v++) {
      components[cc.id(v)].enqueue(v);
    }

    for (int i = 0; i < M; i++) {
      for (int v : components[i]) {
        StdOut.print(v + " ");
      }
      StdOut.println();
    }
  }
}

I am writing up some of the doubts I have and understanding them can let me write better code in future and understand the authors intent better(there might be some stupid question so please bear with me :p ):

  1. Instance variable G, why its always declared with capital?
  2. Can I do final Graph G to make sure its never reassigned anywhere?
  3. Why Queue and not simple ArrayList?(while printing all the vertices in the component).
  4. Public interfaces with names like V, I am always taught to write descriptive names. In what conditions these names are allowed?
  5. Why we need abstractions like StdOut when we already have library support like System.out?
4

You asked

Instance variable G, why its always declared with capital?

and

Public interfaces with names like V, I am always taught to write descriptive names. In what conditions these names are allowed?

I guess these two things have the same reason: the original algorithm description and the related sections in your text book has the form of a mathematical text. Mathmaticians often use one letters for variables, and capital letters for sets and set structures like graphs, so it is no surprise the one who implemented the algorithm just stuck to that convention. For such an algorithmic context this is ok, since you want to use the similar terms and abbreviations in your code as the ones used in your text book.

Can I do final Graph G to make sure its never reassigned anywhere?

Yes, you can. However, since G is only used as a local variable in more or less short functions, this does not add much value to the code, only additional "noise". See this SO post, read the two topmost answers, one is saying "yes, do it", and the other one "it is a waste of time". In your example above, I tend to the agree more to the second answer.

Why Queue and not simple ArrayList?(while printing all the vertices in the component)

Actually, it does not matter - using an ArrayList in the shown piece of code would neither simplify nor complicate the code. It seems just to be a matter of taste. From the way you asked you seem to be biased, thinking an ArrayList seem to be "more simple" than a Queue, but ask yourself why you think this and how the code will change when you replace one type by the other.

Why we need abstractions like StdOut when we already have library support like System.out

If you look into the initial comment section of the original Java class StdOut: it is described there precisely. The differences are related to the character set, float/double number formatting and flushing. Moreover, the earlier editions of the "Algorithms" book were not written using Java, but older languages like Pascal, C and C++, so providing an abstraction for standard output makes the book more language agnostic.

6
  • I may agree with you but don't you think publishing code example from such a trusted source the authors must have thought something. I am mean the code is to be read by millions of readers and there is no clarity on why Queue was preferred over ArrayList, sounds ridiculous isn't it? I need to wait for more concrete explanations :) – CodeYogi May 22 '16 at 17:37
  • @CodeYogi: you are overthinking this. The algorithm in this example simply needs a FIFO container for collecting the result nodes. Any kind of such container works, the authors picked a Queue, they could have chosen an ArrayList instead, it would have worked as well. Maybe they just picked it because the word Queue has less characters than ArrayList, so there is less to type, who knows? – Doc Brown May 22 '16 at 20:54
  • Why FIFO container? We just need to store the vertex for printing in the standard output, maybe because its needed to print them in the increasing order? – CodeYogi May 23 '16 at 3:16
  • @CodeYogi: why not? Using something which does not return the vertices in the same order the algorithm found them would occur pretty strange - that would be occur ridiculous. – Doc Brown May 24 '16 at 16:41
  • Got it! I have added one last point please do let me know if you have some clarification on it. – CodeYogi May 25 '16 at 3:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.