CodeMarvels – Page 15 – A Coder’s Notebook.

Applications of DFS

Posted on August 26, 2013 by Sreekumar Kj

One of the applications of DFS is to find the number of connected components in a graph.In graph theory, a connected component of an undirected graph is a sub-graph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the super-graph.

Algorithm-

A depth first search that begins at some particular vertex v will find the entire connected component containing v (and no more) before returning.To find all the connected components of a graph, loop through its vertices, starting a new depth first search whenever the loop reaches a vertex that has not already been included in a previously found connected component.

Another application is to find if the given graph is a tree or not.A tree is an undirected graph which is connected and does not have cycles.

Properties of a tree-

1.The tree should have only one connected component ie. it is not a disconnected graph.
2.If the graph has N vertices and N-1 edges,then it is a tree.This condition ensures that no cycles are formed.

Algorithm-

For a graph to be a tree,both the above conditions must be satisfied.Number of components is found using the above algorithm and it should be 1.Then,the second relation must be verified.

Code-

[cpp]

#include<stdio.h>
#include<vector>
using namespace std;

vector<int>arr[10005];
int n,a,b,j=0,m;
int color[100005];

//counter counts the number of components

int counter;

void dfs(int node)
{
color[node]=2;//marking the visited nodes

for(int i=0;i<arr[node].size();++i)
{

if(color[arr[node][i]]==0)
{
dfs(arr[node][i]);
}
}
}

int main()
{
int t,p;
int i;
counter=0;
p=1;
j=0;

// n is the number of vertices
// m is the number of edges

scanf(“%d %d”,&n,&m);

//clearing the arrays and vectors

for(i=0;i<n;i++)
arr[i].clear();

for(i=0;i<n;++i){
color[i]=0;
}

while(j<m){

//a and b denote the starting and ending points of the edge

scanf(“%d %d”,&a,&b);

//maintaining the adjacency lists

arr[a-1].push_back(b-1);
arr[b-1].push_back(a-1);
j++;

}
//looping through the vertices

for(i=0;i<n;++i)
{
if(color[i]==0)
{
dfs(i);
counter++;
}
}

printf(“Number of components is %d\n”,counter);

if((m==n-1)&&(counter==1))printf(“IT IS A TREE\n”);

else printf(“NOT A TREE\n”);

return 0;
}
[/cpp]

Android Development

Databases in Android using SQLite – Part II

Posted on August 23, 2013 by Sreekumar Kj

In the last post I showed you how to create a database. We created a table inside it and inserted values. Although we could make sure that our database was successfully created, we had no way to confirm the same about our tables. In this post I’ll show you how to access the data from a database.

So create an activity and follow along. Complete Source Code is at the bottom

Set the Content View of the activity. Do not put any elements in the layout.
Switch over to the java file and write the below lines after the setContentView() method.
[java]
SQLiteDatabase db = openOrCreateDatabase(“NeroDB”, MODE_PRIVATE, null);
db.execSQL(“CREATE TABLE IF NOT EXISTS NeroTable(LastName VARCHAR, FirstName VARCHAR, Age INT(3));”);
db.execSQL(“INSERT INTO NeroTable VALUES(‘NeroLast1’, ‘NeroFirst1’, 20);”);
db.execSQL(“INSERT INTO NeroTable VALUES(‘NeroLast2’, ‘NeroFirst2’, 21);”);
db.execSQL(“INSERT INTO NeroTable VALUES(‘NeroLast3’, ‘NeroFirst3’, 22);”);
[/java]
Since, this post assumes that you have a fair idea of SQLite, you can change the name of the Database, table and the values inside the table to whatever you wish.
Now, we will access the data from our database. Notice that we have not yet closed the database, this being the reason.
Write the code below. I strongly recommend not to paste these lines, but to write them using the Auto-Complete feature of Eclipse editor. That way, in the suggestion, you can see the method signatures and it will help you understand what we are doing and also change a few values to your liking.
[java]
Cursor c = db.rawQuery(“SELECT * FROM NeroTable;”, null);
while(c.moveToNext()){
Log.v(“NeroLog”, c.getString(c.getColumnIndex(“FirstName”)));
}
[/java]
Now, we will drop the Table and delete the database. We are doing this because if we do not, every time we run the application, the three rows will be inserted into the table. You can choose to let it be and not drop the table and the database. In case you do want to, write the below lines.
[java]
db.execSQL(“DROP TABLE NeroTable;”);
this.deleteDatabase(“NeroDB.db”);
[/java]
Remember to close the database irrespective of whether or not you did the above step.
[java]
db.close();
[/java]
Now execute the application in an emulator.
Once it runs successfully, switch over to the DDMS section. If you wrote the exact lines as I have you will find Logs with the tag NeroLog and the values as the first name column values in the database. This is how you make sure that your table has been created and the values have been inserted.

Understanding the Code

Cursor :- Cursor is analogous to a pointer in most programming languages, It points to the beginning of the set of rows returned from a query.
rawQuery(String SQL, String [] SelectionArgs) :- This method returns a Cursor and is similar to execSQL(). It provides a way to provide selection arguments to an SQL query. I will talk about selection arguments in a later post.
moveToNext() :- Since a cursor points to the beginning of rows, this function provides a way to sequentially access each row.
Log.v :- Verbose Log. Creates a Log with the provided tag and message in the DDMS LogCat.
getColumnIndex :- This is a way to access the column by name of the row currently pointed to by Cursor.
deleteDatabase() :- This method is used to delete the database.

COMPLETE SOURCE CODE

[java]
package com.nero.myfirstapp;

import android.media.MediaPlayer;
import android.os.Bundle;
import android.preference.PreferenceManager;
import android.app.Activity;
import android.app.AlertDialog;
import android.app.Dialog;
import android.app.ProgressDialog;
import android.content.DialogInterface;
import android.content.Intent;
import android.content.SharedPreferences;
import android.database.Cursor;
import android.database.sqlite.SQLiteDatabase;
import android.util.Log;
import android.view.LayoutInflater;
import android.view.Menu;
import android.view.MenuItem;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;
import android.widget.Toast;

public class Main extends Activity {

@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);

SQLiteDatabase db = openOrCreateDatabase(“NeroDB”, MODE_PRIVATE, null);
db.execSQL(“CREATE TABLE IF NOT EXISTS NeroTable(LastName VARCHAR, FirstName VARCHAR, Age INT(3));”);
db.execSQL(“INSERT INTO NeroTable VALUES(‘NeroLast1’, ‘NeroFirst1’, 20);”);
db.execSQL(“INSERT INTO NeroTable VALUES(‘NeroLast2’, ‘NeroFirst2’, 21);”);
db.execSQL(“INSERT INTO NeroTable VALUES(‘NeroLast3’, ‘NeroFirst3’, 22);”);
Cursor c = db.rawQuery(“SELECT * FROM NeroTable;”, null);
while(c.moveToNext()){
Log.v(“NeroLog”, c.getString(c.getColumnIndex(“FirstName”)));
}
db.execSQL(“DROP TABLE NeroTable;”);
this.deleteDatabase(“NeroDB.db”);
db.close();
}
}
[/java]

Android Development

Databases in Android using SQLite – Part I

Posted on August 16, 2013 by Sreekumar Kj

In this post I will show you how to integrate SQLite and Java in your Android Application. If you do not have a fair idea of SQLite, I would suggest you to take a look at my previous post and follow the instructions.

Create an Activity and start programming. Complete Source Code is at the bottom.

Set the Content View of the activity. Do not put any elements in the layout.
Switch over to the java file and write the below lines after the setContentView() method.
[java]
SQLiteDatabase db = openOrCreateDatabase(“NeroDB”, MODE_PRIVATE, null);
db.execSQL(“CREATE TABLE IF NOT EXISTS NeroTable(LastName VARCHAR, FirstName VARCHAR, Age INT(3));”);
db.execSQL(“INSERT INTO NeroTable VALUES(‘NeroLast1’, ‘NeroFirst1’, 20);”);
db.execSQL(“INSERT INTO NeroTable VALUES(‘NeroLast2’, ‘NeroFirst2’, 21);”);
db.execSQL(“INSERT INTO NeroTable VALUES(‘NeroLast3’, ‘NeroFirst3’, 22);”);
db.close();
[/java]
Since, this post assumes that you have a fair idea of SQLite, you can change the name of the Database, table and the values inside the table to whatever you wish.
Save your activity and execute it on the emulator.
It is apparent that you have no way of knowing whether the database and the table were successfully created and whether the values were inserted into it.
This is where DDMS comes into play. Switch over to the DDMS section and you should see the File Explorer section just above the LogCat and Console. This is an explorer for the files in the SD card of the emulator. Remember that the emulator must be running in order for you to browse the files.
Navigate to data/data/<yourapplicationname>/databases. Here you should see a database file with the name of the database. If it is there, your database was successfully created. If not, something went wrong and you should check your code.

Remember that your application may encounter exceptions that require you to Force Close you application. In such cases refer to the LogCat in the DDMS and it should point you exactly to what exception was encountered. Also, you should know that since the exception may be encountered in on of the SQL queries, your Database and the table might have been successfully created and the exception occured thereafter.

Understanding the Code

SQLite Database db :- This is an instance of SQLite Database that we are creating.
openOrCreateDatabase(String Name, int mode, CursorFactory Factory) :- This functions opens the database if there exists a database by the name provided. If not, it creates one and opens it. Mode is provided in order to let the system know the accessibility of the database. By MODE_PRIVATE, we tell the system that this database is private to our application. CursorFactory is beyond the scope of this post. We do not need to use it and hence it is provided a value of null.
execSQL() :- This function allows us to write the SQL query as a string and execute it. Remember that there are other ways to write queries in which pure SQL will not be used.
close() :- This function closes the database. Recall that we had used the openOrCreateDatabase to open the database. Closing the database is essential to prevent leak.

COMPLETE SOURCE CODE

Main.java

[java]
package com.nero.myfirstapp;

public class Main extends Activity {

@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);

[/java]

Android Development

Android development: Introducing SQLite

Posted on August 10, 2013 by Sreekumar Kj

As you start to develop complex applications containing multiple activities and providing multiple functionality, often times you would want to store structured data in your application. Android provides a mechanism to do this using Databases.
The SQL that is used with Android system is SQLite. Just like MySQL is used with PHP and Microsoft SQL Server with ASP.NET, SQLite is used with Android System.

SQLite is an open source database that supports standard relational database features like SQL syntax and transactions.
SQLite supports a variety of data types like Text, Integer, Real etc. Text is similar to Strings in most Programming Languages.
SQLite is embedded in every Android device eliminating the need for any setup procedure.
All one needs to do in order to work with SQLite databse is to write SQL queries to create and update the database.
All the Databases contained within your application will be saved in the directory DATA/data/<yourappname>/databases/filename.

This tutorial series is concerned with Android Application Development and although databases are a major sections I will not be concentrating on SQLite but on integrating SQLite with Android. Nevertheless, there are some very good tutorials on the internet that can come in handy while learning SQLite. Below are a few :-

For the scope of this tutorial series, a fair knowledge of SQLite should be enough. Further posts will assume the following :-

You have a fair idea of SQLite and it’s working.
You can write well formed SQL queries.
You have a fair idea of the how the values are returned for the queries.

In the next post I’ll show you how to integrate SQLite and Java for the purpose of Android Development.
Happy learning SQLite.

Algorithms

Longest Common Subsequence

Posted on August 9, 2013 by Sreekumar Kj

Given two sequences,the task is to find the length of longest sub-sequence present in both of them. A sub-sequence is a sequence that appears in the same relative order, but not necessarily contiguous.For example- “abc”,”fit”,”abfi”,etc are sub-sequences of “abcfit”.A string of length n has 2^n different possible sub-sequences.

Example-

String 1- “BATTING” Length-7
String 2- “BOWLING” Length-7

Longest Common Sub-sequence- “BING” Length-4

Brute Force-

Generate all sub-sequences of both given sequences and find the longest matching sub-sequence.It has an exponential time complexity.

Efficient Algorithm-
lcs(i,j)=
              if (X[i]==Y[j])
             1+lcs(i-1,j-1)
              else
              max(lcs(i-1,j),lcs(i,j-1))

where X[],Y[] are strings.

Recursive Solution-

[cpp]

//char X[0,1…m-1],Y[0,1,…n-1] contains the strings
//lcs(m,n) is called initially.

int lcs(int a,int b)
{
if (a == 0 || b == 0)
return 0;

if (X[a-1] == Y[b-1])
return 1 + lcs(a-1,b-1);
else
return max(lcs(a,b-1), lcs(a-1,b));
}

[/cpp]

This problem has overlapping as well as optimal substructure property.Thus,dynamic programming can be applied.A temporary array L[ ][ ] is constructed to store the intermediate results.

DP solution-

[cpp]

int lcs(int m,int n)
{
int L[m+1][n+1];
int i,j;

// L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]

for (i=0; i<=m; i++)
{
for (j=0; j<=n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;

else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;

else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}

//L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1]

return L[m][n];
}

[/cpp]
This program has a time complexity of O(m*n) where m,n are lengths of the string which is much better than exponential time complexity.

Algorithms

Activity Selection Problem

Posted on August 5, 2013 by Sreekumar Kj

Activity selection problem is an example of greedy algorithm.Greedy algorithms look for simple, easy-to-implement solutions to complex, multi-step problems by deciding which next step will provide the most obvious benefit.The advantage of using a greedy algorithm is that solutions to smaller sub-problems of the problem can be straightforward and easy to understand.The disadvantage is that it is entirely possible that the most optimal short-term solutions may lead to the worst long-term outcome.

Problem-

Given n activities with their start and finish times,we have to find the maximum number of activities that can be performed by a single person,assuming that a person can only work on a single activity at a time.

Algorithm-

1) Sort the activities according to their finishing time
2) Select the first activity from the sorted array and print it.
3) Do following for remaining activities in the sorted array.
a) If the start time of this activity is greater than the finish time of previously selected activity then select this activity and print it.

Example-

start[]={1,5,7,1}

finish[]={7,8,8,8}

The maximum set of activities that can be executed by a single person is {0,2} where 0,2 are the activity numbers.

start[] = {1, 3, 0, 5, 8, 5}

finish[] = {2, 4, 6, 7, 9, 9}

The maximum set of activities that can be executed by a single person is {0, 1, 3, 4}.

Code-

[cpp]
#include <cstdio>
#include <algorithm>
using namespace std;

pair< int, int > a[100000];

//a[].first denotes the finish time
//a[].second denotes the starting time

int main()
{
int i, n, last;

//n denotes the number of activities

scanf(“%d”, &n);

for(i = 0; i < n; i++)
{
scanf(“%d %d”,&a[i].second,&a[i].first);
}
//using sort function for an array of pairs sorts
// it according to the first one.
//sorting according to finish time
sort(a, a + n);

last = -1;//initialization
for(i = 0; i < n; i++)
{
if(a[i].second>= last) //step 3
{
//printing the activity number which is selected
printf(“%d “,i);
last = a[i].first;
}
}

return 0;
}

[/cpp]

Android Development

Android dev tutorial: Shared Preferences Screen in Android

Posted on August 3, 2013 by Sreekumar Kj

Now that we are familiar with what Shared Preferences are and how they work, its time to actually look into one of the main applications of the Shared Preferences – the Shared Preferences Screen most commonly used as the Settings screen of many applications to remember the user preferences.

So start up your Main activity and start coding. Complete Source Code is at the bottom.

In the layout for you main activity, have a button that launches another activity which will be the Preferences Screen.
Create another activity Second.java. Remember to choose PreferenceActivity as the parent class for this activity and not the regular Activity.
Much like we set the content view of a normal activity, we need to provide this activity with a layout.
Go ahead and create an XML file second.xml. In the resource type choose Preference and not Layout. Leave the root element as PreferenceScreen.

Go ahead and write the following code inside the <PreferenceScreen></PreferenceScreen> tags.

<CheckBoxPreference
        android:key="first"
        android:title="first option"
        android:summary="This is the first option" />

<CheckBoxPreference
        android:key="second"
        android:title="second option"
        android:summary="This is the second option" />

Remember that the android:key attribute that is present here is the key for the key-value pair that is present in the SharedPreferences. While accessing the value you will have to refer to it via this key.
Switch over to Second.java and paste the below code after super.OnCreate(Bundle savedInstanceState)
[java]
addPreferencesFromResource(R.xml.second);
[/java]
In the above method, we have provided a layout for the activity. It is obvious that we have not used setContentView() method. For now it’ll be sufficient for you to know that in order to provide a PreferenceScreen a layout, we make use of addPreferenceFromResource() method. It takes care of all the saving and rewriting of values in SharedPreferences.
Switch over to the MainActivity.java file, get a reference to the button and set the onClickListener() method to call the activity Second.class, with the help of an intent.
Save your work and execute it on am emulator/device

Remember that the saving of values to SharedPreferences and rewriting the values, are done by Android on its own since the activity we have created inherits PreferenceActivity.
Now, to access the values in the SharedPreferences, add the below lines wherever you need it.
[java]
SharedPreferences settings = PreferenceManager.getDefaultSharedPreferences(this);
boolean first = settings.getBoolean(“first”, false);
[/java]
Remember that the method signature of the method above is getBoolean(key, defValue). So we need to provide the name of the key exactly. Recall that in second.xml we have given the value of first to the android:key attribute of our first CheckBoxPreference. Here we use the same value to get the value from the Shared Preferences.

COMPLETE SOURCE CODE

MainActivity.java

[java]
package com.nero.myfirstapp;

import android.media.MediaPlayer;
import android.os.Bundle;
import android.preference.PreferenceManager;
import android.app.Activity;
import android.app.AlertDialog;
import android.app.Dialog;
import android.app.ProgressDialog;
import android.content.DialogInterface;
import android.content.Intent;
import android.content.SharedPreferences;
import android.view.LayoutInflater;
import android.view.Menu;
import android.view.MenuItem;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;
import android.widget.Toast;

public class Main extends Activity {

@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);

SharedPreferences settings = PreferenceManager.getDefaultSharedPreferences(this);
boolean first = settings.getBoolean(“first”, false);

Button but = (Button) findViewById(R.id.button1);
but.setOnClickListener(new OnClickListener() {

@Override
public void onClick(View v) {
Intent intent = new Intent(MainActivity.this, Second.class);
startActivity(intent);
}
});
}
}

[/java]

Second.java

[java]
package com.nero.myfirstapp;

import android.app.Activity;
import android.os.Bundle;
import android.preference.PreferenceActivity;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;
import android.widget.TextView;

public class Second extends PreferenceActivity {
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
addPreferencesFromResource(R.xml.second);

}
}

[/java]

second.xml

<?xml version="1.0" encoding="utf-8"?>
<PreferenceScreen xmlns:android="http://schemas.android.com/apk/res/android" >

    <CheckBoxPreference
        android:key="first"
        android:title="first option"
        android:summary="This is the first option" />

    <CheckBoxPreference
        android:key="second"
        android:title="second option"
        android:summary="This is the second option" />

</PreferenceScreen>

Android Development

Android dev primer: Shared Preferences – An Introduction

Posted on July 31, 2013 by Sreekumar Kj

When you are into creating complex Android Applications, you will want the user to be able to customize the settings of your application according to his needs. Although not always, this is mostly where Shared Preferences are required in applications.

What are Shared Preferences?
When you need to save information across launches of your application with ease, you will be doing it with the help of Shared Preferences. It provides a way to preserve certain specific information even when your application is closed. It must however be remembered that it is definitely not the only way to do it. It is preferred over most other methods because it is predefined in Android for specifically this task alone.

In this post I’ll demonstrate the working of Shared Preferences. We will have an EditText in our activity. Once we write something in the EditText and close the application, in the subsequent launch of the application, the EditText will hold the same value. This is only the introduction as to how to use shared preferences and I will post about how to use it for cusomizable settings of an application. So start up an activity and follow along. Complete Source Code is at the bottom.

In the layout create an EditText.
Switch over to the java file and declare this EditText inside the class and outside all methods. We will be making it universally accessible because we will use it in more than one methods, as you will see shortly.
Inside the onCreate() method, get a reference to the EditText.
Now write the following lines in the onCreate() method.
[java]
SharedPreferences text = getSharedPreferences(“mypref”, 0);
et.setText(text.getString(“prefvalue”, “”));
[/java]
It is strongly advisable that you do not try to copy paste these lines and write them on your own. In the auto-complete suggestions of Eclipse IDE you will find small descriptions of the method signature and information about what this method does. It is necessary that you try and remember the function names.
Now, just like we’ve overridden the onCreate() method, we will override the onStop() method. This method is called when the activity is closed. Just as you start writing the onStop() method, make use of the auto-complete feature of Eclipse and well formatted method stub will appear.
Write the following lines inside the onStop() method.
[java]
super.onStop();
SharedPreferences text = getSharedPreferences(“mypref”, 0);
SharedPreferences.Editor editor = text.edit();
editor.putString(“prefvalue”, et.getText().toString());
editor.commit();
[/java]
Save your work and execute it on an emulator/device.

Understanding the Code

SharedPreferences holds the required information in the form of key-value pairs. Each key uniquely identifies a unit information or data.
While getting a reference to the SharedPreferences, we have made use of the function getSharedPreferences(String name, int mode). We have provided a name of mypref to the SharedPreference and a mode of zero. Remember that if a SharedPreference instance by this name does not exist already, Android creates one by this name.
To set the text of the EditText, we have made use of an overloaded version of setText() method. The signature for this method is setText(String key, String defValue). Here the key is the key for the key-value pair, as described in the first point. We have given it a value of prefvalue to it. defValue is the default value that appears if there does not yet exist a key-value pair where the key name is key, i.e prefvalue in this case.
Now, in order to store the text in the EditText in the SharedPreferences, we override the onStop() method because it is only when the activity is about to be closed that we need to save the text. We get a reference to the SharedPreferences by the name of mypref.
In order to be able to write something to the SharedPreferences we need a SharedPreference Editor. This is just like any other editor that allows writing of data.
With this editor, we now save the data to SharedPreferences by the help of putString(String key, String value) method. Remember, the key here should be the same as the one in the setText() method inside the onCreate() method, i.e. prefvalue in this case, the reason being that only then can the data we are saving, be uniquely identified.
Once we have told the editor what edits are required to be made, we want the editor to actually commit those changes on SharedPreferences, hence the commit() method.

COMPLETE SOURCE CODE

[java]
package com.nero.myfirstapp;

import android.media.MediaPlayer;
import android.os.Bundle;
import android.app.Activity;
import android.app.AlertDialog;
import android.app.Dialog;
import android.app.ProgressDialog;
import android.content.DialogInterface;
import android.content.Intent;
import android.content.SharedPreferences;
import android.view.LayoutInflater;
import android.view.Menu;
import android.view.MenuItem;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;
import android.widget.Toast;

public class Main extends Activity {

EditText et;

@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
et = (EditText) findViewById(R.id.editText1);

SharedPreferences text = getSharedPreferences(“mypref”, 0);
et.setText(text.getString(“prefvalue”, “”));
}

@Override
protected void onStop() {
super.onStop();
SharedPreferences text = getSharedPreferences(“mypref”, 0);
SharedPreferences.Editor editor = text.edit();
editor.putString(“prefvalue”, et.getText().toString());
editor.commit();
}

}

[/java]

Algorithms

Dijkstra’s Algorithm

Posted on July 29, 2013 by Sreekumar Kj

Given a network of cities and the distances between them,the task is to find the shortest path from a city(source) to all other cities connected to it.The network of cities with their distances is represented as a weighted digraph.It is also known as single-source,shortest path problem.

Algorithm-

N is the number of vertices labeled {0,1,2,3….N-1} of the weighted digraph.cost[0:N-1][0:N-1] is the cost matrix of the graph.If there is no edge from i to j,then cost[i][j]=INT_MAX.If i equals j,then cost[i][j]=0.
Vertex 0 is the source.
V is the set of N cities
T={0}; //T is initialized by adding the source vertex

//distance[] is initialized to the cost of the edges connecting vertex i with the source vertex 0.
for(i=1 to N)
{
distance[i]=cost(0,i);
}

for(i=0 to N-2)
{
Choose a vertex u in V-T such that distance[u] is a minimum;
Add u to T;

for each vertex w in V-T
{
distance[w]=minimum(distance[w],distance[u]+cost[u,w]);
}
}

Its time complexity is O(N^2) where N is the number of cities.

Code-

[cpp]

for(i=0;i<n;i++)
{
b[i]=0;
distance[i]=cost[0][i];
}
//b[i]=1 if i is in set T and b[i]=0 if it is in set V-T.

b[0]=1;//T is initialized
z=1;//counter initialized to 1

while(z!=n)
{
min=INT_MAX;

for(i=0;i<n;i++)
{
if((b[i]==0)&&(distance[i]<min))
{
min=distance[i];
u=i;
}
}
b[u]=1;
z++;
for(w=0;w<n;w++)
{
if((cost[u][w]!=0) && (b[w]==0) && (distance[u]!=INT_MAX) && (distance[u]+cost[u][w]<distance[w]))
{
distance[w]=distance[u]+cost[u][w];
}
}

}

//printing the shortest distances
for(i=0;i<n;i++)
printf(“%d “,distance[i]);

[/cpp]

Example-

If the cost matrix is-

@ denotes INT_MAX

0 20 @ 40 110
@ 0 60 @ @
@ @ 0 @ 20
@ @ 30 0 70
@ @ @ @ 0

The output is-

distance[0]=0
distance[1]=20
distance[2]=70
distance[3]=40
distance[4]=90

Android Development

Android Dev Primer: Adding Camera Functionality in Android

Posted on July 29, 2013 by Sreekumar Kj

Often, in your Android application, you will want to incorporate photos that the user takes from his camera. Just like audio and video, it is possible and rather fairly easy to include camera functionality in your Android application.

In this post I will show you how to take the user to the default camera application from our application, click a photo and then return that photo to our application. We can then make use of that photo any way we want. So start up an activity and start coding. Also remember that when it comes to testing camera related features, we are going to do this on an actual Android Device and not an emulator for obvious reasons. Complete Source Code is at the bottom.

For the layout of the activity, have a Button and an ImageView. I would advise you to make the ImageView stretch through the entire width and height of the layout, left after placing the button. We would be placing the photo taken from the camera here.
Switch over to the Java file and declare both, the Button and the ImageView in there. Remember to declare the ImageView inside the class and not inside the onCreate() method. This is because we will be using it in other methods as well.
Inside the onClick() method of the Button, write the following
[java]
Intent intent = new Intent(android.provider.MediaStore.ACTION_IMAGE_CAPTURE);
startActivityForResult(intent,0);
[/java]
Now, we need to get the clicked photo back from the camera to our application. For this we will override the onActivityResult() method of the Android.Activity class. Write the following code just after the onCreate() method.
[java]
protected void onActivityResult(int requestCode, int resultCode, Intent data){
super.onActivityResult(requestCode, resultCode, data);
Bitmap bm = (Bitmap)data.getExtras().get(“data”);
iv.setImageBitmap(bm);
}
[/java]
Save your work and execute it on an Android device.
When you hit the button and get into the camera application, click a photo and you will be redirected to the original application with the photo you just clicked placed in the ImageView in your activity.

Understanding the Code

Let’s take some time and try to understand the code we just wrote

The Intent we used while calling the camera application is quite understandable. If you have read my previous posts, you will know what we use an intent for. The argument for the intent however, is a string constant that tells the Android system that we want to use the camera application – android.provider.MediaStore.ACTION_IMAGE_CAPTURE.
android.provider refers to the content provider of Android. I will write about this in a later post.
MediaStore is the part of the content provider that we want to refer to.
ACTION_IMAGE_CAPTURE is the actual string we want.
Normally, while using Intents, we call the method startActivity(). Here, you can see, we have called startActivityForResult(Intent intent, int requestCode). Since, we need the result of the following Activity back in this activity, so we use the above method.
requestCode is useful when we have several requests being made from the activity. This helps us to uniquely identify the request.
Bitmap is used because the data that has been sent back to our activity has a Bitmap object. Hence we use the setImageBitmap() method.
data.getExtras().get(“data”) : The data passed to our Activity from the Camera is in the form of Extras. The name of the data is data.
An interesting thing to know here, is that we do not need to add permissions for the use of camera in our Manifest file. Why? Because once we a re switching to the default camera application, we are letting it do all the work. The permissions are granted for the Camera Application. However, if you would, sometime want to build you own camera UI, you will need to access the raw camera surface. In that case you will need to include the android.permission.CAMERA in your manifest file.

COMPLETE SOURCE CODE

[java]
package com.nero.myfirstapp;

import android.media.MediaPlayer;
import android.os.Bundle;
import android.app.Activity;
import android.app.AlertDialog;
import android.app.Dialog;
import android.app.ProgressDialog;
import android.content.DialogInterface;
import android.content.Intent;
import android.view.LayoutInflater;
import android.view.Menu;
import android.view.MenuItem;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;
import android.widget.Toast;
import android.graphics.Bitmap

public class Main extends Activity {

@Override
ImageView iv;
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
Button but = (Button) findViewById(R.id.but);
iv = (ImageView)findViewById(R.id.imageView1);

but.setOnClickListener(new OnClickListener() {

@Override
public void onClick(View arg0) {
Intent intent = new Intent(android.provider.MediaStore.ACTION_IMAGE_CAPTURE);
startActivityForResult(intent,0);
}

});

}
protected void onActivityResult(int requestCode, int resultCode, Intent data){
super.onActivityResult(requestCode, resultCode, data);
Bitmap bm = (Bitmap)data.getExtras().get(“data”);
iv.setImageBitmap(bm);
}
}

[/java]