Musings, Thoughts and Cogitations on Java

Shortest Distance Graph Algorithms - How do they differ?

noreply@blogger.com (Manoj Kumar) — Fri, 11 Jul 2014 23:46:00 +0000

The shortest distance graph algorithms can be tricky. Which algorithm should be used when, whether it can work for negative edges or cycles, which one is the most efficient for the given problem - you should be asking these questions before deciding on a Shortest Distance Algorithms.

The implementation and pseudo code for the standard Shortest Distance Algorithms are easily available on the web but how these different algorithms differ is often not highlighted. In this post, I will focus on how different graph algorithms differ from each other.

These different algorithms differ in term of -

Single Source Shortest Path vs All Pair Shortest Path Algorithms. Single Source Shortest Path algorithm calculates the shortest distance from a given Source vertex to all other graph vertices. All Pair Shortest Distance algorithm calculates the shortest distance between all pairs of graph vertices.
Weighted graph - Can the algorithm work if edges have weights?
Negative weight edges - Will the algorithm work if there are negative weight edges?
Negative weight cycles - The shortest distance problem is not defined for a graph with a negative weight cycle. Because you can keep on going around that cycle and distance with keep on getting smaller. ~~So no algorithms will work in this case.~~(Update - as pointed out on Reddit, although Shortest Distance problem is not well defined if there are negative weight cycles, it is slightly incorrect to say that algorithms do not work in this case. e.g. Bellman Ford algorithm can be used to detect negative weight cycles in graphs).
Space and Time Complexity

Now let's look at the standard algorithms from these aspects.

Breadth First Search

Single Source Shortest Path algorithm
Does not work for weighted graphs. All edges should have equal or unit weight.
Does not work for Negative weight edges
Time Complexity - O(E + V)
Space Complexity - O(V)

Dijkstra

Single Source Shortest Path algorithm
Works well for Weighted graphs
Does not work for Negative weight edges
Time Complexity - O(E log(V) + V log(V)) using standard heaps, O(E + V log(V)) using Fibonacci Heaps.
Space Complexity - O(V)

Bellman Ford

Single Source Shortest Distance algorithm
Negative Edges - Yes
Time Complexity - O(EV)
Space Complexity - O(V)

Shortest Distance for Directed Acyclic Graphs(DAG)

Apparently if the graph is of type DAG (Directed Acyclic Graph), then there is another algorithm with better time complexity. It works for all cases where Bellman Ford works plus it has better time complexity.

Single Source Shortest Distance algorithm
Negative Edges - Yes
Time Complexity - O(E + V)
Space Complexity - O(V)

Floyd Warshall

All pairs shortest path algorithm
Works well for Weighted graphs
Works well with negative weight edges
Time Complexity - O(V^3)
Space Complexity - O(V^2)

Now let's try to use these differences to solve a problem. I was asked this problem in an interview and it is a very good problem to test understanding of different graph algorithms.

You've always been intrigued with the Six Degrees of Kevin Bacon game. Let's say if two actors have been in the same movie we call them 'friends' and if two actors have not been in the same movie, we say they are not 'friends'. Now choose any two actors at random -- we want to calculate the number of degrees of separation and the path between them. How do you go about this problem?
• Discuss your algorithm ideas. For each algorithm talk about the trade-offs.

Ok. Clearly this is a shortest distance problem.

What are the weights of the edges? All edges have unit weight. So BFS can be used.
Are there negative weight edges? No. All edges have weight 1. So Dijkstra can also be used. Between BFS and Dijkstra, BFS has better Time complexity O (E + V) vs O(E + V log(V) ) in Dijkstra. Space complexity is same for both O(V). Clearly between BFS and Dijkstra, BFS is better in this case.
This problem is best modeled as an undirected graph and can contain cycles. So DAG algorithm will not work.
But what about Floyd Warshall Algorithm. So do we need an All Pair Shortest Path algorithm here? Floyd warshall has time complexity of O(V^3) and space complexity of O(V^2) which is worse than BFS. Here we need to understand the problem better. Do we need to perform the distance calculation for a single pair of actors or there can be many looks we need to perform. If we need to do a one-off lookup, then clearly BFS is a better solution. However if we need to perform many lookups over a long period, then it make better sense to just run Floyd Warshal once, calculate all the distances and store the results and later use the stored result for each lookup.

Hope this articles helps you understand different shortest distance algorithms better. Please comment if you have any questions or feedback.

Concise Collection Initialization using Google Guava

noreply@blogger.com (Manoj Kumar) — Fri, 12 Oct 2012 19:49:00 +0000

One thing I really like with languages like python, ruby or perl is that they have succinct and elegant way to initialize the collections - Map, Set and Array.

Collection Literals project is supposed to bring concise initialization syntax to Java. But there is no hope for this until Java 8. There are some hackish ways to do inline initialization of collections particularly using Double Curly Brace Initialization but none of these is elegant and expressive.

Google provides an excellent api of their core libraries called Guava. This library provides some nice utility classes to perform initialization of collections.

For each collection type, Guava provides Utility Classes. e.g. for Lists, there are classes - Lists (utility class for operating with lists) and ImmutableList - (an Immutable version of List). Lets take a look at couple of examples -

Loading ....

References -

Reddit Discussion for this post

http://www.reddit.com/r/java/comments/11g46q/concise_collection_initialization_using_google/

Java - One liner to Configure Logging

noreply@blogger.com (Manoj Kumar) — Fri, 05 Oct 2012 11:00:00 +0000

Often while writing some quick test or doing a prototype, we want to use logging. But we do not want to spend any time writing a properties file and doing the whole setup.

However there is a quick way to get log4j ready to use in a single line.
Log4j provides a BasicConfigurator which can be used to quickly configure the logging.

Usage Example -

public class LoggingOneLiner1 {

 private static final Logger logger = Logger
   .getLogger(LoggingOneLiner1.class);

 public static void main(String[] args) {
  // Configure the logging - this does the whole setup
  BasicConfigurator.configure();

  // Optional Step - change the logging level to INFO from default DEBUG
  Logger.getRootLogger().setLevel(Level.INFO);

  logger.info("Its nice to to be able to configure logging in one line");
  logger.debug("I like quick and dirty java tricks");

 }

}

From the api docs of log4j -

The invocation of the BasicConfigurator.configure method creates a rather simple log4j setup.
This method is hardwired to add to the root logger aConsoleAppender. The output will be formatted using a PatternLayout set to the pattern "%-4r [%t] %-5p %c %x - %m%n".
Note that by default, the root logger is assigned to Level.DEBUG.

Reddit Discussion on this post -
http://www.reddit.com/r/java/comments/10zkhr/java_one_liner_to_configure_logging_using_log4j/

Speedup Your Collections with Improved Hashing Function from Java7

noreply@blogger.com (Manoj Kumar) — Fri, 28 Sep 2012 12:23:00 +0000

Java7 has introduced an improved hash function for Map and Map derived implementations (since 7u6). It is applicable for keys of type String.

Following collections can make use of this new hash function.

The new hash function improves the performance when there are large number of collisions.

It can be enabled by setting the System property jdk.map.althashing.threshold.
If jdk.map.althashing.threshold=k ,
This means that java will use alternative hashing function for maps with capacity greater than k entries.

Usage Example -
java -Djdk.map.althashing.threshold=512 MyAppMain

Why it is disabled by default and caveat before using -

This feature is disabled by default to ensure backward compatibility.
The iteration order of keys, values and entries will change after using the new Hash function. According to Java team, many applications have dependencies on iteration order and therefore they have decided to disable this by default.
If your application logic has dependencies on iteration order of Map/Set, then you should remove those dependencies before using new Hash function.
Ideally applications should not make any assumptions regarding iteration order and therefore it is a good time to refactor your code and utilize the new Hashing function.

References -

Reddit discussion for this post -

http://www.reddit.com/r/java/comments/10m5tg/speedup_your_collections_with_improved_hashing/

Prefer ThreadLocalRandom over Random

noreply@blogger.com (Manoj Kumar) — Fri, 21 Sep 2012 13:33:00 +0000

Java 7 has introduced a new random number generator - ThreadLocalRandom

Normally to generate Random numbers, we either do

Create an instance of java.util.Random OR
Math.random() - which internally creates an instance of java.util.Random on first invocation.

However in a concurrent applications usage of above leads to contention issues -

Random is thread safe for use by multiple threads. But if multiple threads use the same instance of Random, the same seed is shared by multiple threads. It leads to contention between multiple threads and so to performance degradation.

ThreadLocalRandom is solution to above problem. ThreadLocalRandom has a Random instance per thread and safeguards against contention.

From the api docs -

Usages of this class should typically be of the form: ThreadLocalRandom.current().nextX(...) (where X is Int, Long, etc). When all usages are of this form, it is never possible to accidently share a ThreadLocalRandom across multiple threads.

Usage Example -

//Generate a random number b/w 0 and 10.  0 <= R < 10
//Using Math.random()
int r1 = (int)Math.random()*10;
//Using Random
Random rand = new Random();
int r2 = rand.nextInt(10);
//Using ThreadLocalRandom
int r3 = ThreadLocalRandom.current().nextInt(10);

Update -
Reddit discussion on this post