A Quick tip on Data Structure for DFS/BFS

Breadth-First Search and Depth-First Search are two very common graph traversal algorithms for any Graph.

There are two ways of representing graph - Adjacency Matrix and Adjacency Lists.  Well, this link gives more ways of representing a Graph.  But, let us not get into that.

Both DFS and BFS requires us to iterate over the children of a node.  This will be done for almost all nodes.

• Iterating through all children is O(n) in Adjacency Matrix.
• It is O(branches) in Adjacency Lists.

In a sparsely connected Graph, O(branches) is much smaller than O(n).  So, if we need to do a DFS, we should always choose Adjacency Lists over Adjacency Matrix.

Create an Android Activity as a popup

For the most of your popup needs, Android's Dialog should be good enough.  To popup some message, use AlertDialog.  Always use AlertDialog.Builder to build a new AlertDialog.  If you need a custom set of controls in the main message, use AndroidDialog.Builder's setView() method to set appropriate layout.

Now, if we need to popup a special kind of Activity that a Dialog cannnot solve, we can still do that.  But using Activity as a popup has a few problems.  In this post, I would like to discuss some of the approaches that I had taken to solve the problems.

How to disable back button in Android

Android phones come with a back button to go to previous activity.

http://docs.xamarin.com/static/guides/android/application_fundamentals/activity_lifecycle/Images/image4.png


There can be workflows where you may not want to go to previous Activity unless certain action is completed.  Sometimes, the current workflow may be in unstable state.  Sometimes, going back may not make any sense in the workflow.

The simple way to avoid using back button is to implement

onBackPressed() event in the activity.

If you are using a old version of Android, you may have to override onKeyDown.

public boolean onKeyDown(int keyCode, KeyEvent event)

Just check for (keyCode == KeyEvent.KEYCODE_BACK).

-----

This leads to another button that may close the Application - the Home button.  Home button takes you to Android device home.  Should that be overridden too?

It is unwise to override Home button.  Instead of trying to handle Home button's press, the Application's workflow should be designed to handle Home button is press during its execution. Here is a www.stackoverflow.com discussion on this topic.

Happy coding

Find the longest shortest-path between any two points in a graph

Given a graph, G, with edges E with weights W and vertices V.  You will have a path between two connected vertices.  Of the multiple paths between two vertices there should be one of the path that has the minimum weight.  Take the shortest path between every two points and return the one that has the maximum value.

This is a classic case of Floyd-Warshall algorithm.  The algorithm finds the shortest path between every two vertices in a graph.  We can use this to find all distances and then finally, find the maximum path.

Floyd-Warshall algorithm takes every pair of vertices in a graph and computes the distance of path through a third vertex.  This gives shortest path between any two vertices.  The complexity of the algorithm is O(|V|3)

A more efficient solution: We can calculate the path from a vertex V1 such that it is shortest path between V1 and one of the vertex and is longer than shortest path between any other vertex.  See this post for an algorithm.  Then, we can iterate through every vertex and find the longest path with every vertex as the root.  Once we have the list of all longest shortest-path, we can find the one that has the max value and return it.


find maxDepthInGraph(G)
{
  V <- G.vertices()
  E <- G.edges()

  for every vertex v in V:
    depth[v]=do breadth-first-search(v) and get the longest-  shortest-path

  maxDepth = -1
  for every vertex v in V:
    if maxDepth < depth[v]:
      maxDepth = depth[v]

  return maxDepth
}

Find the longest route from a vertex to any other vertex in a graph

Given a graph, G, with vertices, V, and edges, E, and V1 is one of the vertices in the graph, find the path in G such that it is the shortest path between V1 and a vertex and the path is greater than the shortest path between V1 and any other vertex in the graph.

For example, take this graph

In this graph, given V1 = node 4; the path that should result is 4 -> 1 -> 3 -> 5.  The reason is that, the path 4-1-3-5 is the shortest path between 5 and 4 and it is the path that is longer than shortest paths between node 4 and any every other vertices.

Solution: We need to do a Breadth-First Search.

1) Take V1 as the root node.  Then take all its children in a queue.

2) Do this till there is no more nodes in the queue:
2.a) If the children has been processed before, ignore it.
2.b) Otherwise, if the depth is the highest yet found, note down the path and depth for next iteration.
3) When all nodes are processed, return the highest yet depth and path. 

Orlando Trip

I had not been to any long-distance trips lately.  So, my wife and I decided to go to Orlando, Florida.  I thought I would share some of my experience with all of you.

1. Orlando's hotels cost a lot.  For example, we got a decent place to stay at Chicago for around $40.  The same in Orlando would have costed us some $100.  The place we chose was for $40 - which meant, it was below our expectations.  There were insects in the bathroom.  The AC was old - did not work as we intended it to work.  The wash basin happened to be outside the bathroom.  I personally was not satisfied.
2. Then we went to Disney World - Hollywood Studios.  I went there expecting a lot of rides and stuff.  Unfortunately, most of the things available were shows.  The website is right - they have very little number of rides.
3. The Island of Adventure in Universal Resort was great.  I thoroughly enjoyed it.  It had so many rides and stuff.

My recommendation:

1. Choose a good hotel.  You must estimate the cost of your hotel to be about twice as much as what you pay in a normal place.
2. Choose Universal for theme parks, if you need adventure.  Choose Disney World, if you dont like that much of adventure.

There are other places like Sea World, etc.  I did not go there.  So, I have no idea about those places.

Fight of narratives

I am mostly a passive reader in Quora.  But something kept cropping up again and again under the topic of "Tamil Nadu, India", or "Chennai, Tamil Nadu, India".  It is that why do Tamils hate North Indians.

http://www.quora.com/Chennai-Tamil-Nadu-India/Why-tamil-people-have-hatered-feelings-for-out-siders-Why-they-hate-north-indians-specially-Why-outsiders-cant-feel-homely-in-chennai-which-they-feel-in-Banglore-Mumbai-Hyderabad-and-rest-of-the-cities

http://www.quora.com/Tamil-Nadu-India/Why-do-Tamils-hate-Hindi-and-the-people-in-Tamil-Nadu-reluctant-to-learn-Hindi

I was totally surprised because I have been totally indifferent about the person's place or origin.  Most of the people who I know do not harbour any hatred for North Indians.  So, why do people ask these questions?  I had been thinking about these questions for a while now.  And these are the results of my reasoning.

India as a narrative

Traditional nations are made up of people who were almost homogeneous - almost all Germans speak German and are Christians and are white, almost all of the US is White, Christian, and speak English.  Think of it this way, there is a majority who get to frame the rules of the land and live happily - and minority fight for equal rights, and nowadays have succeeded quiet a bit.

India, on the other hand, is a minority-majority country.  The language spoken by the the largest numbers is Hindi which is a mother-tongue for just 40% of the population.  India is 80% Hindu - but there are multiple streams of Hinduism.  You can practically find all shades of skin color in India.  Ramachandra Guha, says it beautifully - India is like a salad bowl.  We have many sub-cultures living amongst us.  So, how did India manage to stay together, given there is so much of differences?

The answer, I feel, is narratives.  I come from deep-south of India.  Here, the idea of India is that we have four southern states - where we (Tamils) and other Indians live in; then there are some regions in north - where people speak Hindi - and where a few other Indians live.  The narrative in the north India is, we have a bunch of Hindi-speaking states, bordered with Hindi-speakable states.  There are a few people in the fringe regions in the South.  There is another narrative in West India (by Thackreys) - which is not gaining ground.

These narratives are very powerful.  They put the people holding the narratives at the center of Indian nation (in their minds).  Thus they feel India is "theirs".  But then, there are multiple narratives - each of which puts different peoples as the backbone of India.  So, almost all Indians live in their respective thought-bubbles - thinking that they are Indians.

Pakistan separated from India because in their narrative, they did not see India as "theirs" - so they separated.

Narrative-bust

These narratives get busted when an Indian step out into a region that does not comply to their narrative.  The way s/he reacts to narrative-bust is unique to the sub-culture that s/he belongs to.

It seems North Indians are more active on Quora than South Indians - which explains these rant-like questions about Tamils.

How do you fade in and fade out text in Android?

I had a requirement to make text blink in my Android application.  This came in prety handy:

http://stackoverflow.com/questions/3450839/blinking-text-in-android-view

ViewFlipper is a control available in Android to flip through many controls.  Define all controls within ViewFlipper in layout.  Then call startFlipping() to make ViewFlipper flip.

Now, there is another control called ViewSwitcher.  According to Android docs - "ViewAnimator that switches between two views, and has a factory from which these views are created. You can either use the factory to create the views, or add them yourself. A ViewSwitcher can only have two child views, of which only one is shown at a time."

From what I understand, use ViewSwitcher like you would use themes.  Use ViewFlipper like movie names is displayed in http://www.marcustheatres.com/.