Friday, November 21, 2014

Graph Search or Traversal Algorithms

Graph is a set of connected vertices {V} and edges {E}. A graph may be connected, disconnected, weighted or non-weighted. In other terms, Graph could also be a  tree with cycles. Graph Search or Traversal can be done in two ways as explained below:

1. Depth First Search
In this type of search, we begin at a vertex Vi and traverse through all vertices from Vi unto Vx depth wise, until there is no adjacent vertex which is unvisited. Then we backup all the way upto an unvisited vertex Vy and continue. We continue until there are no unvisited vertices left. It represents Backtracking in Algorithmic Problem Solving.



2. Breadth First Search
In this type of search, we begin at a vertex Vi and traverse each vertex Vj that is reachable from there. Then we continue in the same way at every vertex reachable from Vj. It creates a queue of vertices visited from a given vertex and then deletes each of them if visited or after visiting them. The process is terminated once there is no non-visited vertex left. It represents Dynamic Programming in Algorithmic Problem Solving.


Friday, November 14, 2014

Binary Search Tree Traversal Algorithms

I hereby post my version of the inorder, preorder and postorder code in c++. Please provide your valuable feedback or additions to the code.

I am also providing a simple explanation here along with the download for an explanation of how to perform these simple tree traversals. Please provide your comments on the documentation as well.

In  a Binary Search Tree, every node has the left subtree with elements lesser than itself and the right subtree withe elements greater than (or equal) to itself. In a BST, the tree can be traversed using the following mechanisms.

Inorder Tree Traversal - C++
For a set of elements, that are inserted as mentioned below, the inorder tree traversal algorithms is as follows. It is recursive in nature and can start at root always.

1. Traverse the Left Subtree
2. Print the Node
3. Traverse the Right Subtree

Postorder Tree Traversal - C++
Postorder is a similar algorithm in nature - except that the traversal order is different.

1. Traverse the Left Subtree
2. Traverse the Right Subtree
3. Print the Node

Preorder Tree Traversal - C++
Whenever we want to traverse the node before the two subtrees, we use pre-order traversal.

1. Print the Node
2. Traverse the Left Subtree
3. Traverse the Right Subtree


We use the following insertion order for all algorithms above: 9 7 6 1 3 5 4 2 8

You can run the C++ code to see the output yourself. It is left as an exercise (or direct code reuse) for the user.

Friday, November 7, 2014

JNI/Win32:java.lang.UnsatisfiedLinkError

I spent almost two whole days trying to solve this issue. I did everything possible from altering my c++ code (changing the return types) to compiling from command line rather than the IDE. Also, I tried a number of other steps like changing the classpaths, refactoring package names to changing names of the generated header files. Finally, I found the following resolution.

Whenever the C++ compiler (GCC) generates a DLL, it is exported in the following form:
Java_SomePackage_SomeClass_SomeNativeMethod@8

Where the integer suffix suggests the byte space required by the arguments. This sort of function call makes no sense to the JVM (while invoking someNativeMethod) and hence it leads to java.lang.UnsatisfiedLinkError. The resolution is to add the following flags while linking to generate unmangled names:
-Wl,--add-stdcall-alias

This will create an alias name (pure method call name) to the generated method. This allows the JVM to invoke the right method via JNI.

I almost gave up on this issue, before I finally found this resolution. The point to note here is that this happened to me only on Win32 - I had no issues running on the UNIX platform.