Wednesday, December 30, 2015

Linked List Data Structure with JAVA iterator

Introduction

Linked list is a data structure where nodes are kept in sequence as in a graph but in a linear manner.
As in the above graph what we all keep is a pointer/reference to the head of the list. This data structure can be used to Implement a Stack or a Queue very easily. Because we always have a pointer to the end and the start of the chain. We may also access other elements but it'd need us to iterate thus giving O(n) time complexity.

JAVA Iterator/ Iterable Interface

JAVA provides us with a nice interface which is the Iterator interface which let us use foreach or enhanced for loops. This is very important if we are to use Lamda expressions which is a handy feature in JAVA 8 release. You may be familiar with these if you are already an expert in python programming, where we use these Lamda expressions frequently to make clean code.

Once Iterator interface is implemented methods hasNext() and next() should be implemented giving us the ability to use aforementioned looping. This will be more clear with the code. I have included the codes of two JAVA files LinkedList.java and LLMain.java. We should make sure that we keep track of the current location of the pointer to support iterator. Also I have used a variable to keep if the looping has started. This is just for the implementation of the iterator. What is important is the concept.

The Itarable interface is enables us to create an object iterable. Which means and Iterator object can be obtained. This is if we use the Iterator design pattern. Which is apparently not necessary for our job.

JAVA Code

Make sure you don't import the JAVA LinkedList class :) Then no point!


Feel free to visit the original repository of algorithms at:
URL https://github.com/anuradhawick/Algorithms

Tuesday, December 29, 2015

Detect cycles in a graph using DFS

Introduction

In this post I'm going to talk how to detect if there is a cycle in a graph. Which means can there be more than one way of reaching any node from any other node in the graph. This is completely implemented using the DFS which I have already talked about in a previous blog post. So this will be short blog with only the basics.

In DFS we are using a stack data structure. At the same time we keep track of visited nodes to be ignored in case we find them later in the algorithms. This ignorance is the key point in detecting a cycle. DFS yields a tree out of the graph. Thus there cannot be cycles. Hence we ignore repeated nodes when we go deep through the neighbouring nodes of a graph.

Algorithm and Implementation 
 

Let us consider the above directed graph. Starting from A in a typical DFS we move through nodes as follows.

A->B->C->E->F
since F is a terminal node we have again E at the node.
A->B->C->E
Now the stack becomes something like this
A->B->C->D (Pop out E and put D) and continuing
A->B->C->B
A->B->C->C
now we pop out C (Remember we shall mark what we pop as visited)
now we have 
A->B->C
Bingo, we again pop out C which has already been discovered. Here we conclude that there is a cycle. What really means here is that we have a path to C from A B C E and we again reach C which makes the cycle. This is simple and operates in O(n) time, where n is the number of nodes.

Java implementation is as follows:




Feel free to visit the original repository of algorithms at:
URL https://github.com/anuradhawick/Algorithms

Wednesday, December 23, 2015

Prims Minimum Spanning Tree (MST)

Introduction

This is one of the most commonly used greedy algorithms in many fields. This algorithm tries to make a minimum cost Tree out of a given connected graph, otherwise no tree would exist but a Forest. Following are some applications of Prim's algorithm. There can also be performed by using the Kruskal's algorithms. I'll be talking about the Kruskal's algorithm in a later post. You may also refer to the blog post http://binary-maths.blogspot.com/2015/05/minimal-network-euler-107.html for Kruskal's algorithms as well.

Let's see how it works.
Say we have a graph represented by the adjacency matrix as follows

Graph g = { {0, 2, I, 6, I},
                    {2, 0, 3, 8, 5},
                    {I, 3, 0, I, 7},
                    {6, 8, I, 0, 9},
                    {I, 5, 7, 9, 0},
                  }
where I stands for Infinity or non-edges.
Graph in pictorial view may look like this.

            2        3
      (0)----(1)----(2)
         |      /   \       |
       6| 8 /       \5   |7
         |  /           \   |
       (3)----------(4)
                 9


Algorithm

What happens in the algorithm is we take a vertex and try to set parent for each neighbour if that edge has a lesser cost than the one already have to visit that particular vertex. For an example from 0 we can set parents of 1 as 0 and 3 as 0 and so on. Eventually the algorithm will end up selecting minimum cost incident edge for each of the vertices.

To start with keep an array to save the minimum cost to incident on a given vertex. This array keeps track of the edge that has minimum cost to reach the vertex from all the valid neighbours. In the beginning the array would look like this. The value of index is the vertex id.
minTree = { I, I, I, I, I}
we maintain another array to store parent vertex's index and to check whether a given node is visited already.
The algorithm starts with any vertex say 0. So we make the minTree[0] as 0 and proceed.
Now out of the minTree array get the vertex with min value. Which is 0. Mark as visited by setting visited[0]=true. parent[1]=0, parent[3]=0, minTree[1]=2 (cost of incident edge) and minTree[3]=6. We continue untill there are no unvisited vertices. Ultimately our tree will lie in the parent array as index and value as the edge vertices of the MST.

Code





Feel free to visit the original repository of algorithms at:





Floyd Warshall Algorithm

Introduction

This algorithm runs in O(n^3) time yet it gives shortest path between any two points. The algorithms simply looks the shortest path between two nodes passing a selected node. This operation takes place by using an adjacency matrix. Where the graph is represented using a matrix. Down the rows and through the columns nodes are represented. In the matrix distances are displayed. Distances are taken from row number to columns. See the following example graph with 3 nodes

this contains edges 0-2 = 5 and 1-2 = 10 only. Such a graph will be shown as 

Graph = {
{  0    INF   5},
{INF   0    10},
{INF INF   0}
}

Here we consider Rows as the source vertex and Columns as the target vertex.

Implementation

The algorithm consider a vertex and calculate all the paths through it.
In a vector notation this makes more sense. Say we have a path P(a,b) path a to b. What we do in the algorithm is consider all paths P(a,c) + P(c,b) = P(a,b) until we get min(P(a,b)). This can be implemented using 3 for(;;) loops as follows. With an adjacency matrix the work is so simple. Once done taking the path between any two points becomes peanuts.

Java Code



Feel free to visit the entire algorithms repository, I'm updating this daily: 

Dijkstra's Shortest Path

Introduction
This is one of the most common algorithms that is used to get the shortest path from a single source point. This is useful since we can get the shortest distance to all the other points reachable from a single source point.

Lets see how this algorithm works,
let us start from the node 0

First we initiate all the nodes to distance infinity while having the starting node at distance 0, which is obvious.
from 0 we start traversal. Now we update the distances to the nearest node. Now distances are as follows

to 1 = 1
to 2 = 6
to 0 = 0

since we already covered 0 we no more consider it in our algorithm
For the shortest path to any node we should have the shortest path to every other node. So what we have to do is continue the previously done procedure ahead. Now take the node with the minimum distance node, which is 1 which has a distance 1 from 0. Update its neighbours now. The once that are not covered. Now
to 2 = 1(distance to 1) + 4 (distance 1 to 2) = 5
so now we have updated the node 2
continuing the same the final result,
to 0 = 0 covered
to 1 = 1 covered
to 2 = 5
to 3 = 4
to 4 = 2

Now we continue the procedure for node 4 and update node 3 to be distance 3 (2 + 1). This continues with the remaining node 3 and 2 but the results don't change here since we already have the optima. This is a dynamic programming approach, thus the results does not hold always true. This algorithm fails for negative edges. Because it'll keep one jumping between two nodes without ending or giving an erroneous output.

Program Code

This can be easily implemented in java as follows

Tuesday, December 22, 2015

Depth First Search (DFS) Traversal



Introduction to DFS


DFS is the complete other side of BFS. In DFS the search is carried out in a way by traveling to the depth starting from one node. Let's consider the below example.
In the above graph the DFS would be like this if we start from node 1.
1->2->4->5->3
This happens like this. Once the node 1 is considered it has neighbours 2 and 3. So we select one of them, say 2. Applying the same we have left with only one neighbour to node 2 which is 4, and then 5 to node 4. Again we get node 2 as a neighbour of node 2, but we ignore since we already considered not 2.

For this to implement we are using a Stack data structure, which has push and pop operations.
Lets see how we can model the procedure by using a stack (S).
Iteration 1:
S = 1
we remove 1 and push it's neighbours (1 is marked as discovered)
S = 3, 2
do the same with 2 (Discovering 2)
S = 3,5,4
remove 4 and push neighbours (Discovering 4)
S = 3,5,5
remove 5 and push 2? no because we have already discovered 2 (Discover 5)
S = 3,5
We have already discovered 5, so nothing happens 
S = 3
remove 3, Discovering 3
S = null
Procedure ends here.

Implementation of DFS

This can be represented as a Pseudo code

function DFS(vertex)
    Stack s
    s.push(vertex)
    while(s is not empty):
        vertex = s.pop()
        if(vertex is not discovered):
            mark vertex as discovered
            for(each neighbour n of vertex):
                s.push(n)


This can be implemented using JAVA as follows. Graph is initiated with the number of Nodes (node id starting from 0). Then edges are added (eg: 1,2 is an edge and so on). Finally the runDFS(v) method is called passing the node to start. In this method if a graph has two parts disconnected the other part will not be discovered as we move on with neighbouring nodes. In which case we can call the runDFS(n) method to each node n of the graph.











Monday, December 21, 2015

Breadth First Search (BFS) Traversal

Introduction

Implementation of BFS is very important in path finding algorithms. This is simply analogous to the motion of water waves once a stone is dropped at a point.

 
As we can see in the above picture in BFS for each node the neighbours are discovered first. They the neighbours of neighbours are discovered. Thus the propgation is analogous to the ripple effect.
Let's see how that happens from the above simple tree starting from 1 as the vertex point.

we have 1 so discover its neighbours as 2, 3, 4
In the mean time we maintain a queue to keep the item to be visited next
Q = {2,3,4}
Now we take 2 out and discover its neighbours while updating Q
Q = {3,4,5,6}

Like wise we are continuing the procedure until the queue we started with gets empty. In a tree we are not required to remember visited nodes since there are no connection between nodes in the same level (5 and 6 are not connected, i.e no closed loops). But this is not the case for a graph. Thus we need to keep track of the visited nodes. For this we are using a HashMap in java. This is because we can quickly check if a node is visited ( in O(1) time).

Programming

The algorithm can be elaborated in Pseudo code as follows

function BFS(vertex):
    Q = queue()
    visited = hashmap()
    Q.add(vertex)
    while(Q.size > 0):
        n = Q.dequeue()
        for neighbours v of n:
            if( v not in visited):
                Q.add(v)
            else:
            continue
    visited.add(n)

Programmed Java code is as follows