Looking to my today’s e-mails as every morning I found one I waited for weeks. It was an e-mail of the official dungeon….no, I mean desk keeper at the institut of informatics. He wrote some desk in the Diplomandenroom (i.e., private room for students working on their master thesis) have been freed up.
3 Weeks ago I asked him for a desk but all were occupied by students. I was added to the waiting list. I was the second on the list. Well, today’s waitinglist consists of over 30 students waiting.
Am I so fast or too slow to find the right day putting me on the waiting list? Well, we’ll never know

But a lot of students are finishing their work and are going to leave the room. Students haven’t to wait for long time, at least the top listed students

I’m glad to be their. It will normalize my daily agenda and change them to human time. And some discussions and knowledge transfer will give more quality to my work.

Based on the graph-browser JSaurus, I implemented Wikigraph, a simple graph-based visualization of the content of Wikipedia.org. Every node in the graph represents a topic. Topics are connected to each other if and only if one topic refers to the other one. The references are take from the meta tag keywords of the topic’s website.

But what is the advantage of the graph-browser Wikigraph? Well, first of all, it is possible to create a knowledge map of wikipedia’s content. The knowledge map shows which topics are related to other topics. You have a breath overview about related topics. In other words you see the context of a selected topic.
As an example you can search for Informatics. As result you get Informatics and some linked topics (i.e., Mathematics, Information, Information System). You get the related topics to the related topics to. With all the relations you the context of the informatics.
The context can support you understanding a specific topic rather to read its content twice.

The main advantage is that you don’t have to find the right keyword to find the specific topic anymore. You search by context and not by keyword. You only have to search for a topic of the same context. You get a map of topics of the same context and you can selected the right one or browse further. So, Wikigraph provides not only searching by keyword, it provides searching by browsing too.

A readable graph respects aesthetic criteria of syntatic validity, perceptual organization and aesthetic optimality as proposed by Kosak et al. in 1994. Some algorithms focus on minimizing edge crossing whilst other focus on other aesthetic criteria.
Spring-embedder models and its variants fits aesthetic criteria. But which of them is the best?
First of all you have to define what best means. It dependes on the scenario where the graph is used. Do you need a symmetric graph with lots of edge crossing, or to you need a graph to simulate molecular interactions? You have to give the answer! In this evaluation here best fits the following criteria:

1. Performance: Short calculation time of node placement
2. Scalability
3. Aesthetic critera: Small number of edge crossing, optimal organization of vertices.

I’m evaluating the upper criterias for an implementation in Javascript. Javascript is highly sensible on calculation complexitiy. Lots of calculations and look-ups break down the speed very fast. Short calculation time is very important.

As already mentioned spring-embeded models fits aesthetic criteria very well. Using spring embeded models fits the 3. criteria of aesthetics. Let’s evaluate the algorithms in respect criteria 1 and 2.

The Spring Model

The spring model was originally proposed by Eades (1984). The concept is easy. For all connected vertices a attractive force f_a(d) is calulated. A repulsive force f_r(d) is calculated among all nodes not connected.

• f_a(d) = k_a * log(d)
• f_r(d) = k_r / d²

d is the current distance between two nodes and k_a and k_r are constants.
Asuming n is the number of nodes and r is the number of relations.
According to the implementation with Javascript a division is as expensive as a multiplication. But the calulation of a logarithm is 4 times more expensive then a multiplication or a division. The calculation time is:

(n * (1+1))²+ r * (1 + 4) = 4*n² + 5*r

The complexity is O(n²) because the repulsive force is calculated among all nodes.

The spring model is symmetric. It doesn’t try to reduce edge crossing. Reading those graphs could be problematic.

Force-directed Placement

The force-directed placement has been proposed by Fruchterman and Reingold (1991). This algorithm fits the criteria of minimized edge crossing. The spring model does not. This algorithm is based constists of attractive repulsive forces among nods. As in the spring model, attractive forces f_a are calulated between two connected nodes and repulsive forces f_r among all nodes.

• f_a(d) = d² / k
• f_r(d) = -k² / d

d is the distance between two nodes and k is the optimal distance betweent two nodes. k is calculated fromt he number of nodes and the drawing area.

Asuming n is the number of nodes and r is the number of relations.
According to the implementation with Javascript a division is as expensive as a multiplication. But the calulation of a logarithm is 4 times more expensive then a multiplication or a division. The calculation time is:

(n * (1+1))² + r * (1 + 1) = 4*n² + 2*r

The complexity is O(n²) because the repulsive force is calculated among all nodes.
The force directed placement is better then the spring model because it fits better the critera 3 about minimizing edge crossing and has lower calculation complexitiy in calculating attractiv forces. Force-directed palcement strikes the spring model in performance issues too (criteria 1);

Local Minimum and Simulated Annealing

Both try to organize nodes and relations to minimize the energy of forces between nodes. The display results are the best, but is extremly expensive in the meaning of calculation complexity that is at least O(n²).
I implemented the algorithm of local minimum with minimizing the energy state. The energy was calculated by the functions of the force-directed-graph. My experience with the local minimum is, that the nodes need lot more time to organize them self.
Simulated annealing is a very intersting concept. The difference between the this and other sprin model based algorithm is, that you cool down the temperature (i.e., decrease ability of movement) on every step. You’ll get a stable system very fast depending on the amount of temperature decrease. The force-directed placement can be seen as a special version of simulated annealing, but without a temperature decrease. Depending on the implementation of simulated annealing, it is possible to get a runtime of O(n). Imagine a stable system with nodes. You add one with high kinetic enery. You only have to calculate the energies for the new nodes with all the other nodes. But doing this, you’ll get a bad organized system of nodes and relations.

Conclusion

I think the best graph drawing algorithm is a combination of the force-directed placement in combination with local minimum or simulated annealing. With the force-directed placement you get a good organized system in a short time. To reduce cpu time a change of algorithm is need, because it doesn’t make sense to move nodes only a little and calculate so much. I think local minimum or simulated annealing is a better choice for the calculation at the end because they are going to filter nodes from calculation. But all spring-embedded models aren’t scalable of cause the calculation time complexity of O(n²). We all have to live with it.

First of all: It’s not possible to get directly content from other servers outside the domain with XMLHttpRequest. But if there is no direct way, it must have an undirect way . Well the solution is simply but genius. You call a local proxy, telling it to load the content from the other server and pass the request results to the XMLHttpRequest. That works fine.

In my case I tried to load data from another server for analyzing its link sturcture. I wrote a proxylike script that takes an URL, creates a request to the destination server and sends back the servers response. I’ve written the proxylike script in PHP. Here it is:

You can download http.inc (Advanced HTTP Client) at PHP Classes for free.

Now, you only have to redirect the URL of the content to this proxylike script. Here’s an example how to use the upper proxylike script:

Today it happend again: I got victim by the BIOZ-Syndrom. But what happend? Here’s the hole story about it.
I catched the tram at the Universitätsspital station. It was the line 10. Over all I was sure catching line 10! Passing the Irchel station the driver told us to change the tram to go to… . I didn’t focus on the dirver’s spoken content because I was sure to be in the line 10 that brings me directly to the trainstation of Oerlikon. You have to know that some institutes of the University of Zurich are located there. So is mine. Well, after ignoring the driver’s information he drove somewhere else then I intended to. It was the wrong way. Entering a deep and dark tunnel I remarked that I catched line 9. It wasn’t my first time making this fault. But I wasn’t the only student in the subways making this fault

But what is the BIOZ-Syndrom all about? This syndrom is about students beeing lost between Binzmühlestrasse, Uni Irchel, Oerlikon and Uni Zentrum. So was I. The university management do some prevention already by providing a so called Shuttle-Bus to students. Students don’t have to find the right path using depth-first or breath-first algorithms anymore to overcome zurich’s jungle.
Well, only one problem remains:

• Where is the Shuttle-Bus?

I asked other students but I got always the same phantastic stories about a ghost like bus. The ghost like shuttle bus has never been seen. There were only people knowing people that know other people who have seen this bus once. I’m asking if it is real or just some rumor about something inexistent?

I’m looking for people who have seen the bus. Please make a photo of it and send it to me. We need some proofs of the Shuttle Bus existence.

A graph is nothing else then a thesaurus: Both contains nodes and connections or relations. Therefore I thought about visualizing the link relations between a homepages websites. I took my own homepage cPOEt.net as test data set to create a sitemap with JSaurus, a JavaScript software to visualize a graph or thesaurus.

The node sites have some antigravitation that lets them go as far as possible from other nodes. Only node sites are forced to stay together that are connected by link to each other. This force is calcualted with spring force. It is quite interesting how all the site nodes automatically reorganizes themselves looking for the most optimal distribution in respect to the forces working.

To create a graph or a thesaurus, JSaurus only needs some XML, where the nodes are defined with a set of meta informations. You have to define node tags with some attributes only. You have to add some nodes in the subsection for every link on the nodes site. Every node tag has at least 2 attributes (i.e., ID, title). The title attribute describes the title or the content of this site. The ID tag contains a unique ID to identify each node site. The links are predestined for the use as ID, because they identify a site best. The use of IDs is important to define relations to an already defined node site. I’ll explain that in a short instant. But before, I want to show you an example of a simple XML file for a sitemap. The sites doesn’t have any links backwards to sites comming from.

You were asking how it is possible to define graph circles with a tree structured XML file? Well, it’s easier then you imagine. As ment befor, every node has an unique ID. If a node is going to be inserted into the thesaurus of JSaurus, its ID of the XML is taken to check if it has been inserted already. If it’s the case, the already inserted node is taken to create a relation with the parent node of the XML that exists in the thesaurus already. That’s the whole magic. In the following example the paper site has a link back to the main site. The ID tag is taken to identify the nodes.

For the sitemap if written a XML loader to read data from a XML file and insert elements into the thesaurus of JSaurus. But it is conceivablly to write different loaders that handles the import of different formats.

Jsaurus is a visualization tool to display a thesaurus with its nodes and relations in between. Jsaurus is written in JavaScript and DHTML. The goal of Jsaurus is to provide a piece of softare that manages every type of thesaurus and manages the visualization and behavior of nodes and relations too.
Jsaurus is build with the MVC design pattern. This pattern separates the model (data), the visualization and the control of the model from each other and defines interfaces to communicate between each layer. The advantages is the creation of more transparency and each layer can easy replaced by a new version or a complitely other one. In the Jsaurus case, the model is the thesaurus, the controller and eventhandler build the control layer and the visualization layer consists of a particle system and a renderer.

Below you can see an example of a thesaurus with 5 nodes and wihthout any relations. The particle system calculates the behavior of the nodes in the viszalization. The current particle system gives a kind of gravitation to each node. It calculates the force of gravitation and infers the velocity and position of each node. The example below shows remembers to a 3D planet system.

I’m developing Jsaurus for my diploma thesis about a Graph Based Knowledge Browser for a CMS. I’m looking forward to visualize knowledge maps for enterprises using Microsoft Sharepoint Portal Server. But I’m still in the beginning of my diploma thesis. It will end in 6 months from now on.

Yesterday I started with my diploma thesis at the Institute of Informatics of the University of Zurich. The morning was quite chaotic. First my mentor told me to go to the secretary getting my official task. If one sends you to a secretary it will ever end up with beeing forwarded to other people beeing responsible for the specific task. Well, it took only 1 hours of bureaux hopping . Currently my workplace is in the bureaux of my mentor. But I prefer one at the students room where everyone makes works on his diploma thesis. I already initiated the process of getting a workplace. I’ll see very soon where I’m going to work.

I prepared a detailed plan of what I’ll do the next 6 months. Well, like with every plan, it is deprecated before it is started. After 3 hours I destroyed my plans and adopted a prototyping development process with iterative cicles. Having users at a swiss financel institute I can let them review my prototype and develop in a user oriented way. my diploma thesis is about Implementation of a graphbased knowledge-browser for a CMS. The implementation ends up in a hypberbolic graph browser integrated in a Microsoft Sharepoint System by Ajax and Web 2.0. For the moment I’m checking some existing frameworks to create force directed graphs. There are funny stuff arround

In the afternoon I got invited to the so called Diplomanden-Apéro. I think I could have started better then with some Vodka-Apple-Juice-Drink at the end of the day.

2 weeks ago, I bought a MacMini. The reason was I wanted to use the MacMini in combination with my new NAS as a Home-Entertainment-Server. The MacMini should stream music and videos from the NAS and display it with the cool feature of Mac OS X Front Row. You have to know that an infrared remote controller comes with the MacMini. My plans were 1 computer for my work and one computer for the personal entertainment.
Well, plans tend to be deprecated. My plans changed the first second I started my MacMini. Well, not the first second because to start the MacMini you have to connect a USB keyboard. I had only one with PS2-keyboard. I ran out of the door, forgetting everything around, going to the next keyboard selling store. But thats another story . I’m not realy able to describe how cooool Mac OS X is, you have to experience. Since 1999 I’m working only under Linux and I’m realy happy with Linux. But Mac OS X brings much fun. MacMini is a good combination of a MiniPC and Home-Entertainment-System with FrontRow and the remote controller. Now, I use MacMini for everything expect development. I can’t imagine a better development computer as a Linux machine.
To use the MacMini and my computer at the same time, I added a KVM switch. With a KVM switch I only need 1 keyboard, 1 mouse, 1 monitor and 1 speaker. I have to connect them directly to the KVM switch. I only have to press a button on the switch and the devices changes the owner from my MacMini to my computer and vice versa. That quite handy. The KVM switch I’m using was designed for the use with a MacMini and has the same dimensions.

The most surprising thing is the similarity of the NAS Cube Station CS-406 from Synology and the combination of the KVM-Switch and the MacMini. Both use the same white, the same metallic and the same curves. It’s fantastic. I’m on the way to put an Apple sticker on the Cube Station I got for buying the MacMini. They look harmonic together. This fact brings me to the following idea:

• Imagine an MacMini with a NAS extension. The MacMini and the NAS extension have the same design and don’t make a lot of noise. Wouldn’t it be beautiful to have such a combination in the living room?

I think a combination of an NAS and a MacMini as a combination would be a realy hot Home-Entertainment-System. It would be the perfect product bundle with high synergy effects.

A manager asked me last week if I implement the possibility of putting the playernumber on the shorts and let users decide where the logo and the teamlogo will take place on the shirts. This manager doesn’t use SimCheeese to create teamphotos. He uses it to create pictures of each players only for his team-homepage. Well, that was the right moment to implement all the other features for SimCheeese stored in my head and meet his desire. The following features have been added now:

• Setting the amount of rows of players on the teamphoto: 1 row (players are standing only), 2 rows (players are seating and standing), 3 rows (players are seating, standing and standing on seats)
• Showing list of playernames on the bottom of the teamphoto
• Ahora tambien en ESPANOL!
• Putting playernumber on shorts
• Setting the location of the teamlogo and playernumber: right, center or left
• Scale the teamphoto’s size to the width of 400px, 200px or 100px or original size

Comparing the current state of SimCheeese with the ones of the past, SimCheeese increased not only by new features and possibilities. I invested lots of work into the usability too. I remarked very fast, that a user friendly webtool is used more. The website statistics shows this fact too. The first version of SimCheeese needed an upload of an face image for every player. User had to take a screenshot of the Hattrick’s website showing the players. Only a few were able to create a teamphoto without any erros. At the moment, users only have to copy the HTML source code of the players page of Hattrick and paste it into a textfield. In the this source code are written the images for the players faces. SimCheeese extracts the image pathes and loads them into the teamphoto. It’s more easy but a lot of people don’t know what HTML is and howto get it from their browser.
The problem could be solved easy. Hattrick provides for CHPP like me the possibility to get XML and HTML files. Unfortunately, Hattrick doesn’t allow to include the accessible HTML files into CHPP tools. The only way is to ask the users to extract manually the HTML source code from the page and paste it into a textfield.

Here are some examples of the past versions of SimCheeese:

• Hattrick-Spieler setzen rote Nasen für RED NOSE DAY™ auf.
• SimCheeese 2.0 - ein Tool für Mannschaftsfoto
• SimCheeese erstellt Mannschaftsfoto für Hattrick.org