Inkscape+batch+convert+SVG+to+PDF

March 16th, 2013

I recently had the problem that i needed to convert a lot of .svg files to .pdf for use in a LATEX document.

Inspired by this ubuntuforums post here is a little piece of bash that allows you to do the conversion for all .svg files in the current directory:

for i in *.svg; do inkscape -C $i -A=`echo $i | sed -e 's/svg$/pdf/'`; done

The -C tells inkscape to use the page as defined in the svg as export region. Replacing it with -D will make sure that all drawn objects are included. Of course you can also use the same technique to do e.g. a png export:

for i in *.svg; do inkscape -C $i -e=`echo $i | sed -e 's/svg$/png/'`; done

For more useful options check the inkscape man page.

Bachelor%26%238217%3Bs+thesis+complete

June 16th, 2011

Yesterday I finally handed in my bachelor’s thesis at the Technische Universität München. Although the chosen subject “Interactive visualization of global routing dynamics” was quite interesting to work with it does feel good when everything is over. However, since my advisers seemed to be quite pleased with the results, it is very likely that I will continue my work on this project as at research assistant at the Chair for Network Architectures and Services.

Abstract

To manage the rapid growth of the Internet, numerous tools were designed that allow to visually interpret routing graphs from a specific vantage point or on a local scale, thus helping network administrators make decisions on routing policies. Many of the applied techniques however exhibit poor scaling when they are used to draw larger parts of the global routing graph. In this thesis, AS-Viewer is introduced as a new and flexible tool that allows the use of different graph drawing techniques to display a wide variety of annotations for the AS-Graph. To limit the complexity of the resulting images, clustering can be used alongside with hierarchy based graph layouts. In addition, the graph drawing is done in hardware accelerated 3D, allowing the user to interactively inspect the AS-Graph using perspective to highlight specific subregions of the Internet. Further interactivity is provided through an interpreter that allows close inspection and man­ipulation of the graph. It will be concluded that AS-Viewer can greatly help interpreting large and complex datasets on global routing by allowing to quickly identify peculiarities and potential errors, thus making it an ideal tool in further analysis of global Internet structure.

If the images or the abstract made you curious: here is the .pdf

En+route+to+CAIDA+topology+map

March 30th, 2011

In my current endeavor to make the BGP-Graph comprehensible a few huge leaps have been made. If you are familiar with other work in this field you may know the following image. (source)

Internet topology map from CAIDA.org

Internet topology map from CAIDA.org

Although this rendering does convey a few insights that are not plainly visible looking at the graph data, it still has some serious drawbacks. My main criticism is that it is  fixed image that does not allow easy reuse of the underlying data or any interactivity such as querying and highlighting certain parts of the graph. Also it is not possible to watch changes in this graph in relation to events like 2008′s severing of a FLAG submarine cable leaving much of the middle east with poor Internet speeds. (BBC article)

As you could see in previous articles, it is not trivial to turn such a huge graph into something meaningful. A main problem has been that the force-based graph layout that I employed takes very long to converge if I impose too many restrictions that limit the complexity of the resulting layout. My new approach is to help the force-based algorithm by providing it with a meaningful initialization of the graph layout. Using the CAIDA as-rank dataset I determined a circle radius on which each Autonomous System is placed. The initial angle at which the AS is placed was then calculated using the country code in the WHOIS information obtained from APNIC and the other RIRs.

After this initial placement the movement of the graph nodes was restricted to the angle. The force-based layout algorithm then spread the ASes and also moved a fair few of them away from the United States, where many of them are registered although their main business is done elsewhere. The resulting positions can then be rendered and update in realtime using any decent graphics card.

Longitude based layout of graph

Longitude based layout of graph

There is still a lot of work left but this seems to me like a rather significant breakthrough. Next I will try to integrate my clustering algorithms into the rendering, stay tuned for more…

progress%40thesis

February 16th, 2011

Due to some exams at uni my thesis has been on low priority recently. Since last Thursday however these exams belong to the past and my thesis is humming along once more.

Right now I’m focusing on several aspects such as the rendering (note how the lines between nodes have been replaced by textured quads), user interface (descriptions are displayed for selected AS). Once I have improved the still rudimentary 3D navigation I will try to get the whole graph to render at once using an improved layout and a clustering algorithm.

Other interesting sub-projects are accessing the UPDATE messages from bgp-mon in realtime and integrating further information such as the as_rel dataset from CAIDA.

Stay tuned for more screenshots soon!

Next+up%3A+Bachelor+Thesis

January 28th, 2011

It looks like I have finally gotten myself a subject for my bachelors thesis:

Interactive 3D routing graph visualization (working title)
My supervisors are Dirk Haage and Johann Schlamp from the chair for “Network Architectures and Services” at TU München

What I’m trying to accomplish is to build a tool to visualize the data collected in the routeviews project. This project hosts dumps of the routing tables from several locations around the world. This data contains information about paths that can be used if you want to contact a certain IP-address. Such a table tells an AS (Autonomous System) which remote AS brings it closer to a certain ip address. After several such hops you get a route to your target address.

The data contained in these tables is quite massive (full dump means ~1GB) and requires extensive caching and preparsing. But also if you go a step further and consider the graph that is defined through hops from AS to AS you are looking at ~30.000 nodes and ~70.000 individual links (each of which may be used in thousands of routes!) The main goal of my thesis is to render this graph in such a way that is not just visually pleasing but actually enables the user to explore and understand the complex structure of the graph. To avoid ending up with a hairball (which you can see below) I intend to try several graph clustering and layout algorithms (spring based layoutsLGL, …)

Another main aspect will be to integrate data from various sources, so a user is not forced to copy & paste data all the time when he just wants to look up some additional information.

In order to work with such complex information I will build an extensive GUI interface that enables panning, zooming and rotation and selection through mouse and keyboard controls. To complement this, another fundamental part will be an extensive console interface that allows for complex queries. If I find the time (thumbs pressed) I will post updates on my progress from time to time.

Early screenshot of my bachelor thesis

Early screenshot of my bachelor thesis

back+home

February 4th, 2010

My time in Finland has passed far too quickly, but it was a great experience that I wouldn’t want to miss.

Besides getting to know heaps of students from half the world I also managed to learn a little bit of Finnish. I’m not sure if I will ever need

again, but who knows, after all almost one in thousand people worldwide speaks finnsih. [stunning number yeah] I got to know the Finns as a very nice people that may seem a little reserved at first, but when you managed to get to know them a little they are much more welcoming than some of the mediterranean folks. But of course the Finns also had some irritating customs. These included not really putting spice in their food, lighting hundreds of kilometres of streets through Nowhere and heating the pedestrian precinct. Maybe Finland could use some inspiration from southern europe for their cuisine ;)

I also had a few interesting courses in Finland that ranged from data compression to machine learning, it’s not unlikely that I’ll do one of my theses in on of these fields. But I have yet to decide about those…

And now a few more pictures from Finland:

the+finnish+outback+%26%238211%3B+cottage+trip

November 8th, 2009

just pictures this time ;)

shannon+coding+experiments

October 2nd, 2009

I just came back from today’s exercise in information theoretic modelling (so far I would call it redundancy and data compression, but that doesn’t sound anywhere as cool) with a question that had formed itself during the exercise.

We had the task to implement a Shannon-Fano encoding (a very simple data compression that uses variable length prefix codes) as homework. Basically the algorithm creates a binary tree so that the more frequent characters are higher up than the less frequent ones. This tree is then used to create binary prefix codes. The tree is constructed from a sorted table with the frequencies by subdividing it into 2 halfs that are as equal as possible.

This is the part where I didn’t pay too much attention and thought the equality was the most important goal when dividing. In fact the dividing step is quite simple as it is supposed to be a simple split at the right point. Instead I tried a brute force approach to find the best 1:1 sized  division. Later I came up with an approximation that is quite close to the brute force results and is much faster for bigger frequency tables. O(2^n) -> O(n)

In the exercise i found out how it was supposed to work and I started comparing the two approaches (brute force/approximation vs real shannon)

My understanding of the problem was that a very equal division means that the length of the codewords will be close to the length that is most suitable for the entropy – and thus would minimize average code length.

After trying it out I was proved wrong. I used a few pieces from the English wikipedia to test. And all of them turned out to be slightly longer using my encoding (difference between brute force and the approximation was negligible). On average Shannon was 3% better than my approach.

After thinking about it for a while I think I found the problem. It seems that my approach favours equal code length a little too much.

The following dataset illustrates the difference

char: C B A D E F
freq: 25% 22% 20% 15% 13% 5%

The two algorithms then give the following output
Shannon tree vs equal-split tree
As you can see the tree is more balanced for the equal-split but if you compare the differences in code length it is obvious that the second is worse for encoding.

char shannon equal-split len*probability (shannon) len*probability (equal-split) contribution to entropy
a 10 011 0.4 0.6 0.4644
b 01 10 0.44 0.44 0.4806
c 00 00 0.5 0.5 0.5000
d 110 111 0.45 0.45 0.4105
e 1110 110 0.52 0.39 0.3826
f 1111 010 0.2 0.15 0.2161
2.51 2.53 2.4542

The leftmost column represents the ideal ratio of this letter for the total encoding and the 2 columns right of this one show, how well the two algorithms work for that specific char. Most interesting is the last line where you can see that both algorithms are still a bit away from the lower bound imposed by the entropy. So the actual difference between the two algorithms is very slim. The effect of course varies with the dataset but I didn’t find any instances where the equal-split was closer to the entropy than shannon.
So far I wasn’t able to come up with a mathematical proof if shannon is always better, but maybe I’ll have the right idea one of these days…

You can also download the source from my experiments, but don’t expect too much as I have only just started with python ;)
soucecode (.py, 7.5kb)

Mink%C3%A4+maalainen+sin%C3%A4+olet%3F

September 29th, 2009

*Which country are you from?

Wow time passes quick. It’s already one month since i arrived here in Helsinki. On the one hand it feels like yesterday as I get to see new stuff every day but on the other hand it’s like I’ve been around for ages ;)

Yesterday I went to Nuuksio Nat. park for a second time, but this time there was eight of us and one even had GPS on his mobile phone … Of course that doesnt mean that we were able to follow a straight path and once again, the last thing we found was the lake, but we found a lot of other interesting things on the way. Most notably we found a trampoline that led to a fair bit of fun in the forest (until we were chased away by the owner of the trampoline ;)

[paragraph only suitable for computer science students, others might wanna skip ;þ ] Although some of you might not believe that, I’m actually learning some things at uni here, too. On of them is Python. So far the language has impressed me with a few nice features such as self managing lists, operator overloading and polymorphy, but I think it also has some serious drawbacks. One of them is how iterators are done. Why cant python have something like hasNext() instead of that stupid exception that you have to catch if you do anything else than the standard for-each loop? Also i don’t like using “self.” at least once per line, feels like python had added object orientation by a little child that is determined to get the rectangle block through the triangle hole of his toy… And never try to collaborate with ppl  in python unless everyone uses the same kind of indentation. As of now I’d say python is nice for a quick tryout, but thats it!

Apart from computer science I’m still learning Finnish here. That language also has some curious features.

By omitting one little “a”, you can turn a meeting into a murder: tapaan means I meet, whereas tapan means I kill, dangerous language. Also we learned that one reason for Finns having a less favourable image abroad is that they don’t use Anteeksi, “excuse me/please” very much, however they use Kiitos, thank you a lot. If you know that, they appear quite a lot less rude :)

But this weekend we wont need Finnish so much. We found a quite cheap overnight cruise to Stockholm that we will be taking from sunantai (Sunday) evening to tiistai (Tuesday) morning. Quite cheap means that we will have 4m² for 3 ppl but I don’t think we will need our beds all that much. We’re not quite sure yet what we are going to do in Stockholm, but i don’t expect that to be a problem, when Erasmus students go somewhere, the plan is made when they get there!

That’s it for now, more will follow sometime after Stockholm

Tallinn%2C+Soumenlinna%2C+National+Parks+%26%23038%3B+Squirrels

September 23rd, 2009

Hi everyone!

I’ve been lazy with my posts once again but here it is, another piece of new from the “not-so-cold”-north.

My sister has been around for the last few days and together with other exchange students we took the ferry to Estonia’s capital, Tallinn. We get up so early that the Finns at the train station were still trying to wash away the remains of last nights partying round the train station. Once on the ferry (which is only 30€ incl. return!) we quickly went inside because of the strong wind on deck. Tallinn itself turned out to have a really stunning old town. A large portion of the city fortifications is still intact and well kept. Also the houses in the city are sometimes a few hundred years old and many of them are now embassies, restaurants, or souvenir shops (every 50 meters ;)  We were mostly lucky with the weather but it did rain in the afternoon and so we went into a nice café somewhere in the backstreets. After some more walking we went inside again, although it wasn’t raining. The reason this time was that the restaurant at market square had different prices for inside and outside. The price of a small coke actually doubles if you buy it outside! In the evening we made a short stop at a supermarket and a liqueur store to buy some beer, as the prices are a fair bit lower than in Helsinki (up to factor 2!)

Also we went to Suomenlinna Island and found a nice sunny spot protected from wind directly at the shore.Another day we went to Nuuksio National Park near Espoo. We had planned to maybe collect some mushrooms but it turned out that we didn’t know the right spots for edible ones (we saw many that screamed “eat at own risk” ). However we came across a few interesting and beautiful places as we didn’t exactly follow the marked paths around the park. We actually crossed some kind of swamp :D. Throughout the day we met exactly 1 (thats “one” spelled out) other visitor in the entire time we were there. Not very busy but thats probably a good thing ;) Another thing that we didn’t come across is animals. Most of the animals fled long before we could even see them, but that wasn’t such a big problem as there are hundreds of curious squirrels living right behind my student housing complex (Yeah I almost live in a forest)

In the evenings we tried out a few more party places around Helsinki including an Irish Pub (Molly Malones) that is rapidly becoming on of my regular destinations when we can’t decide where to go. Next week I’ll probably go see something at the Helsinki Film Festival and we are starting to plan a trip to Stockholm.

In case you are wondering If I’m actually studying anything here, well I am…. but it doesn’t take up too much time so far. The semester is divided in two sections here and in the first one I’m only doing an easy introduction to Python programming and a lecture about information theory (things like data compression). The only other uni appointment is my Finnish course, so yes I do have a lot of time to check out things from cities to Erasmus parties. That’s it for the moment, maybe I can find some time to write more soon (don’t place any bets…)

(somehow I forgot this post in the drafts section sorry for delay)