Friday, February 24, 2012

Longest Path Algorithm Implemented in Python

Here I write down the longest path algorithm implementation I did in Python language. Since finding the longest path algorithm is considered as an intractable problem, you will notice that when the number of vertexes in the graph increases the time to find the longest path increases in an exponential way.

The input graph to the program is given as a separate configuration file which also I have shown separately.

longest_path.py file
1:  #!/usr/bin/python  
2:  import string  
3:  import time  
4:    
5:  # represents a vertex in the graph  
6:  class Vertex:  
7:       def __init__(self, name):  
8:            self.name = name           # name of the vertex  
9:            self.visited = 0          # access flag 1=visited, 0=not visited  
10:     
11:     
12:  # represents an edge in the graph  
13:  class Edge:  
14:       def __init__(self, v, u, length):  
15:            self.start = v  
16:            self.end = u  
17:            self.length = length  
18:    
19:    
20:  # read a text file and generate the graph according to declarations  
21:  def generateGraph(V, E):  
22:    
23:       file = open("graph_def_v11", "r")  
24:       line = file.readline()  
25:       line = line[:-1]  
26:       while line:  
27:            taglist = string.split(line)  
28:            if taglist[0] == 'vertex':  
29:                 V.append(Vertex(taglist[1]))  
30:            elif taglist[0] == 'edge':  
31:                 E.append(Edge(taglist[1], taglist[2], string.atoi(taglist[3])))  
32:                 E.append(Edge(taglist[2], taglist[1], string.atoi(taglist[3])))  
33:            line = file.readline()  
34:            line = line[:-1]            
35:       file.close()  
36:    
37:    
38:  # returns the edges list of vertex v  
39:  def pickEdgesList(v, E):  
40:       vu = []  
41:       for edge in E:  
42:            if edge.start == v.name:  
43:                 vu.append(edge)  
44:       return vu  
45:    
46:  def pickVertexByName(V, A):  
47:       for vertex in V:  
48:            if vertex.name == A:  
49:                 return vertex  
50:    
51:  def LP(V, E, A):  
52:       #print("in LP")  
53:       dist = 0  
54:       maxa = 0  
55:       v = pickVertexByName(V, A)  
56:       v.visited = 1  
57:       vu = pickEdgesList(v, E)  
58:       for edge in vu:  
59:            u = pickVertexByName(V, edge.end)  
60:            if u.visited == 0:  
61:                 dist = edge.length + LP(V, E, u.name)  
62:                 if dist > maxa:  
63:                      maxa = dist  
64:       v.visited = 0  
65:       return maxa  
66:    
67:    
68:  def main():  
69:       print('Starting Longest Path Algorithm...')       
70:       t1 = time.time()  
71:       # graph elements  
72:       V = []  
73:       E = []  
74:       generateGraph(V, E)       
75:       maxa = LP(V, E, 'a')  
76:       print 'max=', maxa  
77:       t2 = time.time()  
78:       print t2-t1  
79:    
80:    
81:  main()  


The content of the graph configuration file which is saved as graph_def is as follows.

1:  vertex a  
2:  vertex b  
3:  vertex c  
4:  vertex d  
5:  ------------  
6:  edge a b 1  
7:  edge a c 1  
8:  edge a d 1  
9:  edge b c 1  
10:  edge b d 1  
11:  edge c d 1  

You can run this program on a Linux machined by typing the following line on the terminal,

python longest_path.py

cheers!

Dijkstra's Shortest Path Algorithm implemented in Python

For an assignment work I had to implement the shortest path algorithm and the longest path algorithm recently. Since the implementation language was our choice I used Python to implement it since I was thinking to learn Python for a long time. I took this assignment as an opportunity to learn Python.

Here I write down the source codes of the dijkstra's shortest path algorithm I implemented in Python. This may not be the best way to code it. But this is what my poor Python skills returned. However now I have a considerable exposure in the language and therefore hope I will use it in better ways in the future.

The input graph to the program is given as a separate configuration file which also I have shown.

shortest_path.py file

1:  #!/usr/bin/python  
2:  import string  
3:  import time  
4:    
5:  # represents a vertex in the graph  
6:  class Vertex:  
7:       def __init__(self, name):  
8:            self.name = name         # name of the vertex  
9:            self.dist = 1000         # distance to this vertex from start vertex  
10:            self.prev = None        # previous vertex to this vertex  
11:            self.flag = 0           # access flag  
12:     
13:     
14:  # represents an edge in the graph  
15:  class Edge:  
16:       def __init__(self, u, v, length):  
17:            self.start = u  
18:            self.end = v  
19:            self.length = length  
20:    
21:    
22:  # read a text file and generate the graph according to declarations  
23:  def generateGraph(V, E):  
24:       file = open("graph_def", "r")  
25:       line = file.readline()  
26:       line = line[:-1]  
27:       while line:  
28:            taglist = string.split(line)  
29:            if taglist[0] == 'vertex':  
30:                 V.append(Vertex(taglist[1]))  
31:            elif taglist[0] == 'edge':  
32:                 E.append(Edge(taglist[1], taglist[2], string.atoi(taglist[3])))  
33:                 E.append(Edge(taglist[2], taglist[1], string.atoi(taglist[3])))  
34:            line = file.readline()  
35:            line = line[:-1]            
36:       file.close()  
37:    
38:    
39:  # returns the smallest vertex in V but not in S  
40:  def pickSmallestVertex(V):  
41:       minVertex = None  
42:       for vertex in V:  
43:            if vertex.flag == 0:  
44:                 minVertex = vertex  
45:                 break  
46:       if minVertex == None:  
47:            return minVertex  
48:       for vertex in V:  
49:            if vertex.flag == 0 and vertex.dist < minVertex.dist:  
50:                 minVertex = vertex  
51:       return minVertex  
52:    
53:    
54:  # returns the edges list of vertex u  
55:  def pickEdgesList(u, E):  
56:       uv = []  
57:       for edge in E:  
58:            if edge.start == u.name:  
59:                 uv.append(edge)  
60:       return uv  
61:    
62:    
63:  def findShortestPath(V, E, S, A):  
64:       # set A vertex distance to zero  
65:       for vertex in V:  
66:            if vertex.name == A:  
67:                 vertex.dist = 0  
68:    
69:       u = pickSmallestVertex(V)  
70:       while u != None:  
71:            u.flag = 1  
72:            uv = pickEdgesList(u, E)  
73:            v = None  
74:            for edge in uv:  
75:                 # take the vertex v  
76:                 for vertex in V:  
77:                      if vertex.name == edge.end:  
78:                           v = vertex  
79:                           break  
80:                 if v.dist > u.dist + edge.length:  
81:                       v.dist = u.dist + edge.length  
82:                      v.prev = u  
83:            u = pickSmallestVertex(V)  
84:    
85:    
86:  def printGraph(V, E):  
87:       print('vertices:')  
88:       for vertex in V:  
89:            previous = vertex.prev       
90:            if previous == None:  
91:                 print(vertex.name, vertex.dist, previous)  
92:            else:  
93:                 print(vertex.name, vertex.dist, previous.name)  
94:       print('edges:')  
95:       for edge in E:       
96:            print(edge.start, edge.end, edge.length)  
97:    
98:    
99:  def main():  
100:       print('Starting Dijkstra\'s Algorithm...')       
101:       t1 = time.time()  
102:       # graph elements  
103:       V = []  
104:       E = []  
105:       S = []  
106:       generateGraph(V, E)       
107:       #printGraph(V, E)  
108:       findShortestPath(V, E, S, 'a')  
109:       #printGraph(V, E)  
110:       print 'dummy '  
111:       t2 = time.time()  
112:       print t2-t1  
113:    
114:    
115:  main()  
116:    

The content of the graph configuration file which is saved as graph_def is as follows.


1:  vertex a  
2:  vertex b  
3:  vertex c  
4:  vertex d  
5:  ------------  
6:  edge a b 1  
7:  edge a c 1  
8:  edge a d 1  
9:  edge b c 1  
10:  edge b d 1  
11:  edge c d 1  

You can run this program on a Linux machined by typing the following line on the terminal,

python shortest_path.py

The longest path program implementation will be given as a separate post.

cheers!

Tuesday, February 7, 2012

Adding a custom device driver to Contiki OS

While working on various project works on sensor networks, we had a requirement to attach our own devices with sensor motes for different purposes. To do it we have to write low level drivers which will access the pins of the MCU and perform various tasks. If our applications are running on Contiki operating system, then we have to add our drivers to Contiki. In this post, I write the methodology we followed to do it.        
    This may not be the proper way of adding device drivers for Contiki. However this is the way we did it. Lets say we have two driver files named as my_driver.c and my_driver.h which are some drivers for Tmote Sky platform. The C file contains some functions of the driver and the header file contains the prototypes of the functions in C file. The contents of these files may be like follows. (please note that this example function calls the LED driver functions without doing something its own. Depending on your application it may contain some low level codes)

my_driver.c content

1:  #include "dev/leds.h"  
2:  void driver_function(){  
3:       leds_on(LEDS_RED);  
4:  }  

my_driver.h content

1:  void driver_function();  

 First we should copy these two files to Contiki/core/dev/ directory. Then open the Makefile.sky file which resides in the Contiki/platform/sky directory. There's an entry in this file which specify some C file names separated by spaces. Append our drivers C file name to this entry.

    Now open the file contiki-sky-main.c which resides in the same directory (Contiki/platform/sky) and add the following header file inclusion to it.

1:  #include "dev/my_driver.h"  

Now our driver is correctly placed inside the Contiki source code and therefore we can use it in our applications. To test this functionality, call the driver_function() within the Hello-World example application in Contiki/examples/hello-world directory and run it on MSPSIM simulator by issuing the following command.

make TARGET=sky hello-world.mspsim

    If every things went fine, the simulators red LED should be switched on by our drivers driver_function().



Friday, January 27, 2012

Dr. Kalam was here...


Few days ago, a famous scientist and former president of India Dr. Abdul Kalam visited our university (University of Colombo). He delivered a nice lecture in here which was really inspiring. Even though I had so many works to do on that day, I thought I should attend the lecture somehow and now I'm so happy about that decision.

When I went to the Faculty of Graduate Studies where the lecture was scheduled to be delivered, there was a huge number of students and faculty members from almost all the faculties and institutions of University of Colombo. Since the auditorium was already full, the organizers had to arrange some other lecture halls with television sets to show the lecture live to the students who couldn't get into the auditorium.

After those halls too completely filled with students, they put another television set outside the building to allow the rest of the students see the lecture. I was one of them. When Dr. Kalam entered to the university from the main entrance gate, he was warmly welcomed by our vice chancellor and other staff members. While Dr. Kalam was walking towards the auditorium, he waved his hand at students who were standing outside building. He was a little man with a great personality.

He talked mainly about the importance of education. He remembered the great teachers who have shaped him to reach the today's position from his childhood. I really like the way Dr. Kalam was speaking. He said something that impressed me so much. He asked us to be like flowers. A flower blooms silently and spread its fragrance to all the beings equally. When its task is completed, it fall to the ground and die silently and peacefully. This is the way the life of a great man should be.

After the lecture I searched on the web to find some more information about Dr. Abdul Kalam and I found a website of him where lots of resources available. Most of the inspiring lectures he had done before are available to read in that website. I like the lecture he has delivered at University of Moratuwa too.

Wednesday, December 7, 2011

Using example blick application in TinyOS

TInyOS comes with some example applications to try out before we write a single NesC code. You can find them in the directory /opt/tinyos-2.1.1/apps. In this post I write down how to try the example blink application provided by TinyOS on a MicaZ mote.

If you still haven't installed TinyOS in your Ubuntu system do it. My previous post may help on this. This is the steps I follow to try the blink application.

1) Plug the MIB510 program board to power supply and switch it on. Plug a MicaZ mote to the program board via its 51pin connector.
MIB510 program board
MicaZ mote



2) Open the file located at /opt/tinyos-2.1.1/support/make/Makedefaults and add the following two lines to it,

DEFAULT_PROGRAM=mib510
MIB510=/dev/ttyUSB0


3) Now in the terminal give the following two commands to burn the example blink application to MicaZ mote.

cd /opt/tinyos-2.1.1/apps/Blink
sudo make micaz install


After the MicaZ motes flash memory is written with the app, you will see that three LEDs on the MIB510 program board are blinking. That is the output of the blink program which come to the program board since they are connected. If you remove the MicaZ mote from the program board, put batteries on it and switch it on, you will see the program output as blinking LEDs on the mote.

Installing TinyOS in Ubuntu 10.10




Even though almost all the works I was doing in sensor networks are implemented using Contiki OS, recently I had to install TinyOS and play with it as a course work. Therefore for the first time I used TinyOS and it seems OK. Even though NesC is a little bit painful than pure C used in Contiki, I think I can adapt to it.

I thought to write down the steps I followed to install TinyOS in my machine before my memory get overwritten by something new. There are different variations of TinyOS available and its installation is little bit complicated. This is the way I did as I was instructed. Here I have set up the required tool chains for AVR micro-controller based platforms. There may be different packages required to compile for different other platforms.

1) There are some repositories we have to put in our sources.list file to install TinyOS. Therefore add the two lines shown below to the sources.list file (/etc/apt/sources.list) of your Ubuntu system.





2) If you don't have synaptic package manager in your system, now it's better to install it before going further,

sudo apt-get update
sudo apt-get install synaptic 

3) Now in the terminal issue the following command to install TinyOS, (this step may take some time)

sudo apt-get install tinyos-2.1.1

4) The next step is to install avr-libc package. But there's problem. When you follow the previous step, some of the tools comes with avr-libc gets installed an therefore some package inconsistency problems may occur. Therefore its better to remove those unnecessary additional packages came with TunyOS installation.

sudo apt-get remove avr-binutils-tinyos avr-gcc-tinyos

5) Now lets install avr-libc package,

sudo apt-get install avr-libc

6) Now open .bashrc file of your home directory and add the following line.
To open the file,

 sudo gedit .bashrc

Add the following line to the end of that file, save and close.

source /opt/tinyos-2.1.1/tinyos.sh

7) Now python-dev package is required. So, we install it by issuing the command,

sudo apt-get install python-dev

8) Python version of the system is written in a configuration file of TinyOS. Therefore we have to edit it to make it have the current python version. To find it enter the following in the terminal,

python --version

There we can see the version of python. Open the configuration file by issuing the following command,

sudo gedit /opt/tinyos-2.1.1/support/make/sim.extra


There's a line in that file which starts as PYTHON_VERSION. Change it to have the correct python version in your system.



Now we have installed TinyOS in our system. I will write a separate post about burning an example TinyOS application to a mote.


Friday, November 11, 2011

System Proxy Problem in Ubuntu 11.10

Recently I installed Ubuntu 11.10 in a computer in our lab. Since we have to go through a proxy server in our university to access Internet, I set the system proxy for it.















But when I try to update the system or even try to install new software, it seemed the Internet connection was not working properly. After trying different things, I realized that the system proxy settings that I apply system wide is not worked properly. However when I set proxy settings in the Firefox web browser, it could go Internet. All the other things of the system that goes through the proxy settings didn't work.

After searching over the web I realized that this is a bug in Ubuntu 11.10 version that the system proxy is not applying system wide. The only option is to set the proxy manually without using the GUI. I found this from a forum in the web.

This is how to set proxy manually.

First open a command line and type this,

sudo gedit /etc/apt/apt.conf.d/02proxy

In the gedit editor enter the following lines,

1:  Acquire::http::Proxy "http://192.248.16.90:3128/";  
2:  Acquire::ftp::Proxy "ftp://http://192.248.16.90:3128/";   

You have to replace the "address" field and "port" field with the actual IP address and port number of the proxy server. Then save and close the editor. Now you should be able to update the system and install software from the software center.