Eulerian Trail

Remember the puzzle your friends gave you when you were a kid "Traverse the graph without lifting your pencil" ? Had you known about the "Eulerian Trails" then, you could have dazzled your friends. A more advanced version of the puzzle would be "Draw the longest trail on the graph without lifting your pencil". So how do you handle this?

In Graph Theory, Eular showed the necessary conditions for a graph to be traversed as such. Such a trail or path which traverses the entire graph is called an "Eulerian Tail". To say this more mathematically "A trail which visits every edge exactly once is an Eulerian Trail". If the Eulerian Trail ends at the point where it was started, then the trail becomes a closed circuit which would be named as an "Eulerian Circuit". A graph which has an Eulerian Circuit is an "Eulerian Graph". If the graph does not have an Eulerian Circuit but just an Eulerian Trail which does not end at the point where it was started, then the graph is called "Semi-Eulerian". Got it so far?

So the bottom line is, "a trail which can be drawn to traverse the entire graph without lifting the pencil will exist if and only if the graph is Eulerian or Semi-Eulerian".

Euler gives the necessary conditions for a graph to be Eulerian or Semi-Eulerian.

• Every vertex in the graph must have an even degree, for the graph to be Eulerian.
• If the graph has two odd vertices, Then the graph is Semi-Eulerian where the Eulerian trail will start from one odd vertex and end at the other.
• If there are more than two odd vertices, then the graph does not have an Eulerian tail.

What Eular says is logically correct because,

• If a vertex has an even degree, then that vertex will not be a dead end where you would get stuck when traversing, because when you enter such a vertex there is always a way to exit. So you can visit every edge connected to that vertex.
• If all the vertices in the graph are even, then you can traverse the entire graph and come back to the vertex where you started.
• If you meet an odd vertex on your way traversing the graph, then could get stuck there, unless of course this vertex is the end of the Eulerian trail, because in an odd vertex, the number of edges to exit the vertex will be one less than the number of edges to enter the vertex. (Just like Hotel California, "You can checkout any time you like, but you can never leave" :P)
• Logically, if you start the Eulerian trail from one odd vertex, you wont end your trail there, and neither will you at an even vertex, but you will end the trail in another odd vertex.
• So obviously if you have more than two odd vertices, some of the edges connected to those odd vertices will be not be visited. In such a case, the graph will not be Eulerian.

There is a special property in Non-Eulerian graphs. That is, the number of odd vertices is always even. To understand this logically, lets take the smallest graph you can draw which is a single line. Here you have two odd vertices. When you create larger graphs by adding edges to this smaller graph,

• if the vertex to which you connect the new edge, is odd, it will become even.
• If you don't connect the other end of the new edge to any vertex in the graph, like the edge (6,4) in the bellow graph, then the total number of odd vertices in the graph won't change.
• If you connect the other end to an odd vertex it will become even too, in which case the total number of odd vertices will be reduced by 2.
• If the other end is connected to an even vertex, then that vertex will become odd and the total number of odd vertices will be unchanged.

If you apply this logic to the case where you connect the first end of the new edge to an even vertex, you'll see that to total number of odd vertices will always be even.

Get the idea? For more information, read the Wikipedia article Eulerian Path.

Now lets do some coding. :)

First lets assume a graph like this is represented as an "Adjacency List". In Java we can create an Adjacency List as follows, assuming vertices are numbered with integers.


When such a graph is given, it should be checked if it's Eulerian , Semi-Eulerian or Non-Eulerian. We can use the Eulers' conditions to decide that. Check this piece of code.


If the graph is not Eulerian, we can make it Semi-Eulerian so that we can find the longest trail to visit the maximum number of edges without lifting the pencil.

To do this we have to remove the minimum number of edges from the graph such that the graph becomes Semi-Eulerian. The following code shows how a Non-Eulerian graph is converted to a Semi-Eulerian graph when the set of odd vertices is given. Here the edges will be removed such that the number of odd vertices in the set be reduced to 2. So here 2 odd vertices will be chosen from the set such that the path connecting the the 2 chosen odd vertices will be the shortest. This will make sure that the number of edges removed to make the 2 chosen odd vertices even, be minimal. This procedure is continued until you get 2 odd vertices in the graph. For this we need a shortest path finding algorithm. I'm using the famous Breadth First Search algorithm for its simplicity. Explaining BFS is out of the scope of this post. Here is the code.


Get the code for BFS from here.

Excellent!! Now we have a graph which has an Eulerian trail. Now we have to find it :). How ?? Simple !! Hierholzer's algorithm provides a simple yet effective solution. The idea is straight forward.

• If the graph is Eulerian, start from any vertex, if its Semi-Eulerian start from one of the odd vertices.
• When an edge is visited, add the vertices to the path and remove the edge from the graph, so that it won't be visited again.
• If the graph is Semi-Eulerian you might come to the other odd vertex without traversing the entire graph where as if the graph is Eulerian, you might come to the starting vertex without traversing the whole graph. Here, the unvisited edges make up an Eulerian graph. 
• In this case, look for vertices which are already in the path with non visited edges. Start traversing from one of them until you come back to that vertex.  If you still have edges left continue the same process recursively until you run out of edges.
• You have to keep track of the path accordingly. 

Check the code below. This algorithm returns the Eulerian Trail.

Hope this would come in handy. GL & HF :D

Tell me what you chat with' Ill tell you who you are

So as I mentioned earlier in my previous post I was hoping to participate in Google Summer of Code 2009 and I started working on this sip-communicator project with higher expectations. I was so in to this and I studied a lot of materials to learn some technologies such as OGSI, XML and about various IM protocols. Some stuff I had to work with were completely new to me and I had never worked with IM protocols before. But anyway with time I gained some knowledge and experience to get the basic understanding about the project. So I got the Sip-communicator source code in eclipse and started coding. It was fun but time consuming. After analyzing the code and some playing around with it, I managed to get the basic implementation of the project done. I could see the name tag of the application software the other party is using on my GUI. But sadly after all these efforts the results were announced and I was not selected, but anyway everything happens for the good :). The next day I mailed my would-have-been mentor Yana Stamcheva. He said I was ranked second and the project was given out to the first.( Brett Geren was the accepted student. Congratulations!! ).

I though I should blog about what I did regarding this project. So if anybody is interested it might be a little help.:)

OK! so hears how I did it,

First I analyzed the data packets being received by Sip-Communicator (SC). I analyzed them by editing the SC code and using Wireshark (Its a good tool if you want to try capture packets). This is how I edited the code to test.

There is a package called net.java.sip.communicator.impl.protocols.* . And in it there are classes OperationSetBasicInstantMessagin....Impl. This ... represents the relevant protocol. These classes are extended from AbstractOperationSetBasicInstandMessaging abstract class. These classes are responsible for stuff dealing with incoming and outgoing IM messages of relevant protocols. So in OperationSetBasicInstantMessagingJabberImpl.java class there is an inner class called SmackMessageListner. This acts as a listener to incoming messages of Jabber(XMPP) protocol. This inner class implements org.jivesoftware.smack.PacketListner interface which provides the basic functionality of this protocol. So the object packet in this inner class represents the incoming data packet. Likewise other classes like this there will be similar inner classes. So the method toXml() in this interface will return the xml representation of the data packet. So now we can analyze the packet. I hope its clear. :)

This is the xml tag representing the user agent. from="jeewamp@gmail.com/gmail.7E1F24EA". Here /gmail.### means I used gmail chat. If its Google Talk it would be /Talk.###.

Now about the real coding.

For XMPP i used the inner class SmackMessageListner and it fires a messagerecieved event.

First i added a new constructor in public class MessageReceivedEvent

public String agent="";

public MessageReceivedEvent(Message source, Contact from, long timestamp,String pagent)
{
this(source, from, timestamp, CONVERSATION_MESSAGE_RECEIVED);
agent=pagent;
}

and added this method

public String getAgent()
{
return agent;
}

Then in public class OperationSetBasicInstantMessagingJabberImpl i added this method to get the user agent as a String (not perfect)

private String getUserAgent(String from){
String userAgent="";
StringTokenizer tokanize1=new StringTokenizer(from,"/");
tokanize1.nextToken();
userAgent=tokanize1.nextToken();
return userAgent;
}

in SmackMessageListener inner class in public void processPacket(Packet packet) i added

String agent=getUserAgent(packet.getFrom()); and added this

MessageReceivedEvent msgReceivedEvt
= new MessageReceivedEvent(
newMessage, sourceContact , System.currentTimeMillis(),agent);

fireMessageEvent(msgReceivedEvt);

So now the listeners to this event can retrieve the name of the agent

In public void messageReceived(MessageReceivedEvent evt) of public class ContactListPane listens to this event. so in this method i added(there is a final object chatPanel)

chatPanel.addLogo(evt.getAgent());

so in ChatPanel.java class the following method is there.

public void addLogo(String agent){
this.getChatWindow().setUserAgentLogo(agent);
}

this is the method that sets the logo of the user agent in the chat window.

so i modified public class ChatWindow accordingly

First I edited the constructor

public ChatWindow(){

.......

userAgentLogoPanel.setVisible(chatToolbarVisible);

northPanel.add(userAgentLogoPanel, BorderLayout.WEST);


}

and added this method

public void setUserAgentLogo(String agent)
{
this.userAgentLogoPanel.setLogo(agent);

}

and added this inner class

private class UserAgentLogoPanel extends JLayeredPane
{
private final JLabel agentNameLabel=new JLabel();

public UserAgentLogoPanel()
{
this.setLayout(null);

this.setPreferredSize(
new Dimension(  ChatContact.AVATAR_ICON_WIDTH + 10,
ChatContact.AVATAR_ICON_HEIGHT));

this.add(agentNameLabel, 1);
this.agentNameLabel.setBounds(4, 0, 200, 20);

}

public void setLogo(String agent)
{

this.agentNameLabel.setText(agent);

}

}

So when this is done you can see the name of the user agent the other party using. This is how it appears in my GUI.

I hope this would help someone.

Hello world!! I started blogging today :)

This is my first blog post. I was planning to write a blog for about a year, but was too lazy to start, or lets say didn't have free time to do it :). Today I will write about the GSoC project I'm working on.

I am hoping to be a Google summer of code student this year and I applied for this cool project of www.sip-communicator.org. Its called "Tell me what you chat with, Ill tell you who you are". Interesting name huh? What I basically have to do is to hack in to the protocol stacks and retrieve the information about the user agent which sent the message in a particular session, and show it on the chat window. I have been working for some time on this project, reading documentation, tutorials , studying about various IM protocols, examining data packets using wireshark etc. It has been fun though it was a little bit time consuming.

I did some coding on my project and as Mr Saliya my algorithms teacher suggested, I thought I should update my blog to show my progress. After doing some research on sip-communicator I managed to do some coding. I did this only for xmpp protocol, and when I receive a message the name of the user agent will be displayed as a text  on the chat window. The user agent is shown in text. In this photo "gmail' means the message came as a gmail chat message. If it came from a Google Talk application it will be shown as "Talk". But when I used pidgin to test this, the name pidgin was not shown on the chat window. I think pidgin changes the xmpp protocol. Normally in an xmpp protocol stack there is an xml tag "from: user@gmail.com/Talk.........". Here Talk means the message came from a Google Talk application. But in pidgin this xml tag is user configurable. I talked to a pidgin developer in their IRC and he said that they have made it user configurable to enable the user to log in to two different sessions using the same email address. So i think we cant identify the user agent if we get the message from a pidgin application.

This is one of the best prjects in sip-communicator ideas list