Jannis Pohlmann Personal website

Jannis

I am an open source enthusiast, student and musician from Lübeck, Germany. In my free time I enjoy hacking on Xfce and Lunar Linux. I've been a member of both teams since about 2005. Besides developing software, I love to listen to and play music (Guitar, Bass and Drums) and hang out with friends.

Contact me via jannis@xfce.org. My public PGP key is 0x354AFBA6. You can download it from here.

My CV is also available for download.

Tag - university

Entries feed - Comments feed

Monday, October 17 2011

An introduction to drawing graphs with TikZ/PGF, Part 3

This post is the last in a series of articles about PGF/TikZ and its new graph drawing features on which I am working as part of my graduate thesis.

In the previous two posts I gave an introduction to graph drawing, the graph syntax of TikZ and its Lua-based graph drawing engine that can be used to implement automatic graph drawing algorithms and use them to compute layouts for graphs that are to be rendered with TikZ.

For this post, my intention was to demonstrate the algorithms that I implemented as part of my thesis. These algorithms work well with many graphs, including grids, symmetric graphs, flow charts, flow networks and state machines or automata.

However, I decided to just point to the final version of my thesis here. It documents the algorithms extensively and gives many examples of how to use and tweak them. I think the thesis holds information much more useful to users and graph drawing researchers than what I’d be able to put in a regular blog post.

So, here is the official link: 

http://www.tcs.uni-luebeck.de/downloads/papers/2011/2011-configurable-graph-drawing-algorithms-jannis-pohlmann.pdf

If you find mistakes, please keep them to yourself. It still has to be marked by the two reviewers, so I don’t want to know what I did wrong yet. ;)

Monday, August 29 2011

Looking for a full time job in Open Source

Two years ago I was really close to canceling my studies and looking for a job instead. In the end I continued studying, passed the final exams of my Diplom (the German old-school equivalent to a Master’s degree) with excellent results and started working on my graduate thesis. Today, I am 1 1/2 months away from the submission deadline and it is clear that I will make it.

So, this time I’m serious: I’m looking for a full time employment in Open Source software development, engineering or management starting November this year. Hiring me will get you an experienced and talented hacker with a natural intuition for software architecture and aesthetics as well as a scientific and painstaking approach to software planning and implementation.

Through my work at the university and within the Xfce and Lunar Linux projects, I have gained experience in/with

  • many programming languages (including C, C++, Ruby, Python, Vala, Lua, XSLT, TeX, Java, Bash and a couple of others),
  • many frameworks (the whole GTK+/GLib stack including D-Bus, a bit of Clutter, XLib and Qt/QML, SWT/JFace, the FOX toolkit as well as web frameworks like Sinatra and Rails; some knowledge about the Linux kernel, its facilities and kernel-userspace communication mechanisms included),
  • many developer tools (GNU compilers, Autotools, VIM, NetBeans, Eclipse and others),
  • many software versioning systems (Git, Subversion, CVS and Mercurial), and
  • various areas of computer science and software engineering (complexity theory, signal processing, graph drawing, micro-controller programming and sensor-based networking, software planning, testing etc.).

I feel equally at home developing for the desktop or for the web. Granted, my main area of expertise is user interface and middleware development on Linux, which my fellow Xfce hackers and I have successfully participated in, but I’ve always found web development with Ruby to be a refreshing change.

There are many other things related to open source that I love doing. Over the past years I’ve enjoyed being able to improve the transparency of the development and release management of Xfce. Streamlining the release process and providing tools for making release management fun was an initiative I am particularly proud of. The same goes for community efforts like the Xfce Foundation, which we’ve launched in early 2011 and which I am currently heading as president.

This post is not just about the past though, it’s also about what lies ahead. Things I am particularly interested in with regards to the future include

  • mobile platforms and applications (iOS and Android are not good enough, I think we need open alternatives),
  • multi-touch interfaces on Linux (yep, this is on the way, but there still is a lot of potential work to be done, I guess),
  • cloud-based applications (I know I can store files and data on the web, but where are the mind-blowing features that go beyond availability of personal data everywhere?), and
  • environmental and power saving applications (living responsibly will become important soon enough; how can we generate awareness and support environmental causes with the help of software?).

I am excited and curious what my role will be in all this. Anway, I guess this is enough information about me for now. After all, this is no biography but a job-search post. ;)

If you read this and you happen to be Microsoft or Apple, do not even bother to send a headhunter. I prefer to work in the open and I believe in Open Source for many reasons. This ecosystem that we’ve created over the past two decades provides a great way for people from all around the world to collaborate on projects they care about, in an honest and tolerant way. I think that’s an inspirational model from which our entire society can and hopefully will benefit. Why would we want to have it any other way?

If you are a member or leader of a company dedicated to Open Source software and are interested in hiring me, please let me know. Linked below are my resumé, software projects and email address. I’m looking forward to talking to you!

Download my resumé/CV — A list of references is included. Feel free to contact them; they are aware of being listed and I’m sure they will be happy to answer any of your questions.

My software projects — A list of open source software projects I am or have been working on.

Email address: jannis@xfce.org

Thursday, July 21 2011

An introduction to drawing graphs with TikZ/PGF, Part 2

This post is part of a series of articles about PGF/TikZ and its new graph drawing features on which I am working as part of my graduate thesis.

In the previous post I wrote about motivations for using computer tools to draw graphs. I described the problems with older and current versions of PGF/TikZ. The essence of that post was to show that the current PGF/TikZ syntax for graphs is too verbose and that manual node positioning is impractical. I concluded by explaining that a solution for this is in development. 

In this post I will present some of the graph-related features of the upcoming version of PGF/TikZ. As mentioned in part 1, these are:

  • A new, drastically simplified graph syntax that is as powerful as the verbose old syntax.
  • A couple of basic node positioning (or: placement) strategies such as circular placement or grid placement.
  • The new graph drawing subsystem for automatic graph drawing algorithms based on the Lua scripting language.

As part of my graduate thesis I implemented a set of algorithms for force-directed and layered drawings of graphs. These work remarkably well with a lot of graphs that I collected from lecture notes, books and research papers. I will present these algorithms in a separate post, the third and last of this series.

The new, simplified graph syntax supported by TikZ

TikZ is the graphics language that comes bundled with PGF. In the upcoming version it includes a new syntax for specifying and drawing graphs. First, let us remember the old syntax though (copied from the previous post):

\usemodule[tikz]
\starttext
\starttikzpicture[every path/.style={>=latex},every node/.style={draw,circle}]
  \node            (a) at (0,0)  { A };
  \node            (b) at (2,0)  { B };
  \node            (c) at (2,-2) { C };
  \node[rectangle] (d) at (0,-2) { D };
  \draw[->] (a) edge (b);
  \draw[->] (a) edge (c);
  \draw[->] (b) edge (c);
  \draw[<-] (c) edge (d);
\stoptikzpicture
\stoptext

Remember the problems: manual node positioning, verbose declaration of nodes and edges. Here’s the result once again:

Now, let’s take a look at the new syntax using the same example:

\usemodule[tikz]
\usetikzlibrary[graphs]
\starttext
\startTEXpage
\starttikzpicture
  \graph [no placement,nodes={draw,circle},edges={>=latex}] {
    A [at={(0,0)}] -> {
      B [at={(2,0)}] -> C [at={(2,-2)}],
      C -> D [at={(0,-2)},rectangle]
    }
  };
\stoptikzpicture
\stopTEXpage
\stoptext

The main differences compared to the old notation are:

  • The graph is declared with the \graph macro which executes all TikZ options in the /graphs scope, making the definition of options possible that are not visible to other elements in the TikZ environment (such as nodes={} instead of every node/.style={}).
  • Nodes no longer need to be declared with the \node macro. Instead, simply typing their value is often sufficient. Name names may contain spaces as well as special characters, so things like x_i -> x_j are possible too (in combination with the math nodes graph option these nodes would be typeset just like in a math environment). A third notation is name_text, where name is the internal name to be used when defining edges and text is a string that is displayd inside the node. Again, this text may include special characters and spaces e.g. for formulas.
  • The manual positioning with the at option is a bit more verbose but there are ways around this as you will learn soon.
  • Note that TikZ options can be passed to nodes as well as edges by using the [] syntax.
  • Nodes can be combined in chains (e.g. A -> B -> C) and groups (e.g. { A, B }). Groups are particularly interesting as edges entering or leaving a group are (often, not always) duplicated and re-routed to/from the individual nodes in the group. Also, groups can be assigned TikZ options as well, allowing all nodes or edges in the group to be altered at once (e.g. by changing the color of the nodes A and B to red with { [red] A, B }).

This new syntax has plenty of other features, some of which are still in development (e.g. yesterday we discussed a new syntax for edge labels). All of these features are explained along with helpful examples in about 50 extra pages in the updated manual that we will ship with the next release.

Basic node positioning strategies

In the above example, I chose to set no placement to avoid automatic node positioning. In the upcoming version, TikZ supports various placement strategies including:

  • Cartesian placement (from left to right, with nodes in the same group being placed at the same level),
  • circular placement (nodes are placed on a circle),
  • grid placement (nodes are placed in a N * M grid where the number of columns or rows can be configured by the user), and
  • no placement (for manual positioning)

Here is an example using circular placement and grid placement:

\usemodule[tikz]
\usetikzlibrary[graphs]
\starttext
\startTEXpage
\starttikzpicture
  \startscope
    \graph [circular placement,nodes={draw,circle}] {
      a, b, c, d, e, f,
    };
  \stopscope
  \startscope[xshift=2cm,yshift=1cm]
    \graph [grid placement,n=6,nodes={draw}] {
      a, b, c, d, e, f,
    };
  \stopscope
\stoptikzpicture
\stopTEXpage
\stoptext

There are various options for these placement strategies. Together with a set of standard graphs (complete graphs, complete bipartite graphs, circles, grids etc.) that can be created using keywords such as subgraph K_n or subgraph Grid_n, these already cover a number of use cases.

The original problem, however, remains: how to find a good layout for arbitrary trees, state machines, automata, flow charts and graphs compiled from large sets of data? This is where the new graph drawing subsystem of PGF/TikZ comes into play.

The Lua-based graph drawing subsystem of PGF

Lua is a powerful, light-weight scripting language often used to extend complex software systems such as computer games. It combines elements of procedural, functional and object-oriented programming and is similar to other modern languages like Ruby or Python in that regard. The major differences are that it ships a rudimentary standard library only and that only a few basic data types are provided by default. All other complex data types need to be built on top of the table data type which is a mixture of an array and a hash table.

LuaTeX is an enhanced distribution of the TeX typesetting system that embeds Lua as a scripting and extension language. One of its features is that there is a TeX macro to execute Lua code directly from TeX: \directlua. This can be used to process TeX data with Lua scripts and pass data between these two layers (TeX and Lua). 

Combining the power of LuaTeX with algorithms available for automatic graph positioning (or: graph drawing) might be a good idea. At least that’s what Till —- author/maintainer of PGF/TikZ and supervisor of my undergraduate and graduate theses —- and a group of students thought before they went on to implement a graph drawing interface between TikZ, PGF and Lua. Later when I started my graduate thesis I picked this up and continued to improve and complete it.

Today, this graph drawing subsystem is closed to being stable. It offers TikZ options to select and configure the graph drawing algorithms available in the PGF repository as well as data structures and algorithms to help with implementing new drawing algorithms.

Implementing a new algorithm is as simple as creating a .lua file in the PGF tree and implementing a single function (although I am about to change this so that a class needs to be implemented rather than a function). After that, users can select your algorithm and if you create another file in the PGF tree, you can even specify graph, node and edge parameters for them to configure.

Creating a new algorithm

Again, in order to create a new graph drawing algorithm, all you need to do is create a .lua file in the PGF tree. The graph drawing subsystem resides in the generic/pgf/graphdrawing directory which is divided into two subdirectories called algorithms and core. The core directory contains all the internals and data structures while the algorithms directory holds all the graph drawing algorithms. The algorithms tree is further subdivided into directories for the different classes of algorithms, namely force (for force-based algorithms), layered (for layered drawing algorithms), trees (for graph drawing algorithms related to trees) and misc (for stuff we didn’t know how to classify it).

To demonstrate the procedure of creating a new algorithm, we are going to create a new misc algorithm by creating a file

generic/pgf/graphdrawing/algorithms/misc/pgfgd-algorithm-simple-demo.lua

with the following content:

pgf.module("pgf.graphdrawing")
 
--- A trivial node placing algorithm for demonstration purposes.
--
-- All nodes are positioned on a circle with a user-defined radius.
--
function drawGraphAlgorithm_simple_demo(graph)
  local radius = tonumber(graph:getOption("/graph drawing/simple demo/radius"))
  local nodeCount = table.count_pairs(graph.nodes)
  local alpha = (2 * math.pi) / nodeCount
  local i = 0
  for node in table.value_iter(graph.nodes) do
    -- the interesting part...
    local node_radius = tonumber(node:getOption('/graph drawing/simple demo/node radius') or radius)
    node.pos:set{x = node_radius * math.cos(i * alpha)}
    node.pos:set{y = node_radius * math.sin(i * alpha)}
    i = i + 1
  end
end

Let us quickly walk through the code to get an understanding of the concepts involved:

  • The first line tells PGF to import the graph drawing Lua module. This makes all data structures and functions of the graph drawing available in the script.
  • The function drawGraphAlgorithm_simple_demo() is the entry point to our algorithm. In PGF/TikZ the algorithm will be known by a more readable name: simple demo. The Lua file and the function have to be named consistently to make this work.
  • The function takes a single argument called graph. This is an instance of the Graph class shipped with PGF/TikZ. It holds nodes and edges and provides a number of useful methods to manipulate them, iterate over them etc.
  • Our algorithm places nodes in a circle with a user-defined radius. Thus, in the first line of the algorithm, the /graph drawing/simple demo/radius option is retrieved from the graph object. This option is defined in a different file but we’ll get to that later.
  • Once we have the radius, we can count the nodes, iterate over all of them and place them on the circle where they belong. Note that all values are assumed to be in points, so if the desired radius is 1cm, the value of radius would be something like 28.35.

Basically, everything a graph drawing algorithm is supposed to do is take a graph and set the positions of all nodes to something that makes sense. (This is not entirely correct. Some algorithms may also want to bend edges so that they don’t cross nodes etc. but this is not covered here.)

Defining algorithm parameters for graphs, nodes and edges

I promised to talk about how to define and pass parameters which will lead us to the final syntax for using the algorithm in TikZ. Each class of algorithms (force, layered, misc etc.) forms a so-called TikZ library (graphdrawing.force, graphdrawing.layered, graphdrawing.misc etc.). This way people are not forced to load everything. Instead, they can choose what to include and what not to include in their TeX document. For misc algorithms, this library is defined in the following file:

generic/pgf/graphdrawing/algorithms/misc/pgflibrarygraphdrawing.misc.code.tex

This is where graph, node and edge parameters are defined. For our simple algorithm this would look as follows:

\pgfgddeclarealgorithmkey{simple demo}{simple demo}{algorithm=simple demo}
 
\pgfgdset{
  simple demo/.cd,
  radius/.graph parameter=evaluate math expression,
  radius/.parameter initial=4cm,
  node radius/.node parameter=evaluate math expression
}

The above lines define:

  • A graph drawing algorithm called simple demo. The first argument for \pgfgddeclarealgorithmkey is the name of the algorithm in PGF/TikZ. The second argument is the algorithm family. Sometimes different algorithms take the same parameters and this way the parameters can be defined once and be re-used in all of these algorithms. We do not need this in our simple case and so the family key is set to the algorithm name. The third and last parameter can be used to execute any kind of code allowed in PGF keys. We want to set the graph drawing algorithm to simple demo, which will make PGF/TikZ load our Lua file. We could also set default values for parameters here.
  • Inside the \pgfgdset call we first switch into the algorithm family. Then, we define two parameters: one to be passed to the \graph macro and the other to be passed to nodes using the [] option syntax. Both parameters may be complex mathematical expressions (with optional units). By using evaluate math expression, we leave it to PGF/TikZ to resolve the expression and convert it into points. The general rule to follow here is to leave all parsing to PGF/TikZ and pass values down to the algorithm that are ready to be used in Lua. The radius parameter has a default value set to 4cm which is automatically passed to the algorithm unless the user defines a custom value in the description of the graph.

This is it. There are other ways to define algorithms, families of algorithms and algorithm parameters and those will be covered in detail in the updated PGF manual. In order to understand the basic idea of the graph drawing subsystem, the above information should be sufficient.

Using the new algorithm

Having written a simple graph drawing algorithm the next, obvious question is: how to use it? An brief explanation follows, again using a basic example:

\usemodule[tikz]
\usetikzlibrary[graphs,graphdrawing,graphdrawing.misc]
\starttext
\startTEXpage
\starttikzpicture
  \graph [simple demo={radius=1cm},nodes={draw,circle}] {
    a -> b -> c -> d [simple demo={node radius=2cm}] -> e -> a
  };
\stoptikzpicture
\stopTEXpage
\stoptext

Again, we have to load the graphs library for the graph syntax. We also need to load the graphdrawing library which will pull in graph drawing subsystem. Finally, we need to load graphdrawing.misc to have access to the simple demo algorithm and its parameters.

We select the algorithm by typing \graphs [simple demo]. The part where the radius is set to 1cm can be omitted if the default value proves to be fine. The node d is altered to have a different radius by setting the corresponding node parameter to 2cm. Here is the result:

And that’s it.

Conclusion

With this graph drawing framwork in place we have plenty of opportunities to implement various kinds of graph drawing algorithms and experiment with new ideas. Creating an algorithm and making it available in TikZ is easy once you get used to it, making PGF/TikZ one of the most flexible and developer-friendly graph drawing systems out there.

In the next post

In my next article I will demonstrate the algorithms that were implemented as part of my graduate thesis. These algorithms are comparable with those shipped with Graphviz and Mathematica and are useful for many graphs and work well with grids, symmetric graphs, flow charts, flow networks and state machines/automata. Stay tuned!

Wednesday, July 20 2011

An introduction to drawing graphs with TikZ/PGF, Part 1

This post is part of a series of articles about PGF/TikZ and its new graph drawing features on which I am working as part of my graduate thesis.

In this post you will learn about the motivation for using computer-aided tools to draw graphs as well as the graph drawing features and problems of PGF/TikZ in the version currently available. At the very bottom of the article I will introduce to you the graph drawing features that we have worked on over the past months. They will be covered in more detail in my next post.

Motivation based on my life as a student

When I started as a computer science student, I first had to learn about all the tools that exist out there in order to help with writing down one’s homework. In particular, everyone was looking for an easy way to combine text, math formulas and code for our programming assignments. The answer to all this will be obvious for most of you: LaTeX. Or, as I found out later, its main alternative ConTeXt which I prefer to use nowadays.

LaTeX and ConTeXt make embedding math formulas and code into text documents a bliss, at least compared to other solutions on the market such as the math editor of LibreOffice. The output format is PDF (although other formats are possible) and the resulting documents are rendered and typeset in exceptionally high quality. Sure, you can write homework down on paper yourself. Not everyone fancies professionally-looking, printed documents as they often take more time to create if you are not familiar with the tools. But in our case, having invested a lot of time into preparing our homework was followed by the desire to produce visually appealing documents.

A special problem my fellow students and I were often confronted with was drawing graphs. Typically, we were dealing with binary or arbitrary trees, directed or undirected graphs, flow networks, state machines or automata in general. There are many image editors and vector graphic applications out there, but which one to pick for these kinds of tasks? In the beginning, I remember, we simply left empty spots in the PDFs and filled them with hand-drawn graphs later. This was ok for small graphs but manually arranging the various elements (nodes, edges, labels attached to them etc.) soon became tiring and painful, in particular with larger graphs. Just think about drawing a Huffman code tree for a small alphabet, which was one of our earlier assignments. (Although trees are harmless as it’s relatively easy to predict how they grow.)

Graphviz and the problem with specialized graphics tools

Anyway, you can imagine how happy we were when, finally, we found out about Graphviz. It provides two things mainly: a relatively simple and succinct syntax for specifying the structure of graphs (again: nodes, edges, labels and other information) as well as a set of command line tools to convert this syntax into image files (I mostly used PNG). Graphviz supports directed graphs as well as undirected graphs and provides a handful of different tools/algorithms for drawing them. Here is an example of a simple directed graph drawing with the dot command:

Now, this is quite cool. Even better, the code needed to achieve this layout is just a few lines:

digraph mygraph {
  1 -> 2;  2 -> 3;  3 -> 4;  4 -> 2;
  5 -> 6;  6 -> 3;  6 -> 7;  6 -> 8;
  1 -> 8;  1 -> 5;
}

The major disadvantages of Graphviz (at least from my perspective) are:

  • Rather than being a general purpose graphics toolkit, Graphviz only supports drawing graphs. There are many kinds of graphics people need to create while working on homework, theses, research papers or books. As you can imagine it’s hardly desirable to learn a different syntax or tool for each of these types of graphics.
  • Graphviz only ships external tools and is not integrated into the typesetting systems many people are used to (like TeX). Thus, whenever you change your document’s font, you also need to update and regenerate all the graph drawings created by Graphviz. This might be solvable by generating PostScript files to be included in TeX documents though, I am not sure.

Which leads us back to the topic.

PGF/TikZ — A graphics package integrated into the TeX typesetting system

For TeX-based typesetting systems like LaTeX or ConTeXt there are a number of full-fledged graphics packages that come bundled with their own syntax for creating complex graphics of every kind. Their main advantage is the tight integration with the typesetting system, allowing graphics to be embedded in TeX documents in order to adopt the font and metric properties of the document itself. 

One of the most versatile of these graphics packages is PGF (for the lack of a proper official website I am linking to texample.net here) which comes bundled with the TikZ graphics description language. With a bit of exercise and patience, PGF and TikZ can be used for almost anything. PGF has a manual comprising 800 pages of dense information about all its features and options as well as the internals (the latter being useful for developers mostly). In PGF/TikZ, there is a solution to (almost) everything.

Graph drawing in PGF/TikZ and the problems with the current features

Many graphic objects in PGF/TikZ are represented as nodes and the visual connections between them are remarkably similar to edges as we know them from graphs. It thus comes as no surprise that TikZ can be used to describe and draw graphs. Here is a simple example:

The ConTeXt code (based on the syntax available in the current PGF stable release) for this is more verbose:

\usemodule[tikz]
\starttext
\starttikzpicture[every path/.style={>=latex},every node/.style={draw,circle}]
  \node            (a) at (0,0)  { A };
  \node            (b) at (2,0)  { B };
  \node            (c) at (2,-2) { C };
  \node[rectangle] (d) at (0,-2) { D };
  \draw[->] (a) edge (b);
  \draw[->] (a) edge (c);
  \draw[->] (b) edge (c);
  \draw[<-] (c) edge (d);
\stoptikzpicture
\stoptext

The syntax presented here is a lot more verbose than the compact syntax offered by Graphviz. In particular, nodes have to be defined with the \node macro and edges are defined using the \draw instruction. Obviously, with a syntax like this graph drawings are harder to create and understand at the same time. Again, for small graphs the syntactic overhead might be acceptable. On the other hand creating drawings of large graphs this way becomes a tiring process.

More important and critical than the syntax issues, however, is the fact that, in version available publically, PGF/TikZ does not arrange nodes automatically. As you can see in the above example, all nodes are positioned manually (e.g. node (b) at coordinate (2,0)). People are unlikely to have the perfect layout in mind before seeing a visual representation of the graph the first time, so typically, manual positioning requires step by step improvements or paper sketches to find a visually appealing graph layout. This clearly defeats the purpose of using computer tools.

Note that for trees there is a different syntax. The following example shows a tree drawn with TikZ:

One way to write this down would be with the verbose syntax and manual positioning as described above. A more comfortable notation supported by the current stable version of PGF/TikZ is this:

\usemodule[tikz]
\starttext
\startTEXpage
\starttikzpicture[every node/.style={draw,circle}]
  \node { a }
   child {
     node [fill=black!20] { b }
     child [->,>=latex] { node [red]  { c } }
     child [<-,label=x] { node [blue] { d } }
   } child {
     node[rectangle] { e }
   };
\stoptikzpicture
\stopTEXpage
\stoptext

There is quite a lot you can do with this syntax without blowing the code up too much. The main problem of this node/child approach though is that the built-in tree growth function is somewhat inflexible. And of course it does not solve the problems with general graphs. 

Luckily, there is a solution coming up.

Major graph drawing improvements in the upcoming release of PGF/TikZ

Over the past twelve months, there has been a lot of activity around graph drawing in the PGF repository. Let me briefly list some of the major new features available in the development tree, all of which will be part of the next release of PGF/TikZ:

  • TikZ now supports a new and drastically simplified syntax for defining graphs. This syntax is inspired by the Graphviz format but is more flexible as it allows nodes and edges of a graph to be combined with elements of other features of the graphics system.
  • A couple of simple node placement strategies have been added such as circular placement (placing all nodes of a graph in a circle) or grid placement (placing nodes in a N*M grid).
  • As part of a student project and my graduate thesis, PGF has been extended by a graph drawing subsystem that allows automatic graph layout algorithms to be implemented in the Lua programming language. This is as simple as dropping a Lua script in the PGF tree that implements a single function. PGF provides a number of very useful object-oriented data structures for working with graphs.
  • A number of standard algorithms have been implemented (some are work in progress) to cover the most common scenarios. This was the main subject of my graduate thesis. After initial research I decided to implement three force-based algorithms (for distributing nodes evenly on the plane and highlighting graph features such as symmetry) as well as a modular algorithm for layered drawings of directed graphs. These algorithms are very similar to those available in Graphviz and Mathematica. The results so far look great!
These awesome new features will be covered in detail in the next post. They greatly improve the usefulness of PGF/TikZ for drawing all kinds of graphs and hopefully will make many people’s life easier. Also, the Lua-based graph drawing subsystem provides a great framework for graph drawing researchers to experiment with new ideas. So keep your eyes open for the next post!

Monday, January 10 2011

Attending FOSDEM 2011

I'm going to FOSDEM, the Free and Open
Source Software Developers' European Meeting

Today Nick and I booked hotel rooms for FOSDEM so now it’s official that the two of us will be there. I’m very much looking forward to it and I’m hoping to meet some of you at the FOSDEM Beer Event on Friday! Still need to think about a way to make ourselves recognizable as Xfce folks though.

If you are planning to attend and would like to meet any of the Xfce folks, please add your name in the wiki:

  http://wiki.xfce.org/events/2011/fosdem

We haven’t decided where and when to meet on Saturday and Sunday but I’m sure we will find something. Stay tuned for additional announcements on this weblog.

In addition to celebrating the 4.8 release of Xfce which is scheduled for next weekend, one of our goals for FOSDEM 2011 will be to sign the papers for registering the Xfce Foundation e.V. in Germany. The details of this still need to be worked out, however. I’ll keep you posted about this as well.

If you would like to talk to me about things other than Xfce, please drop me a mail and I’m sure we can arrange something.

- page 1 of 3