Graph drawing algorithms - I'm trying to render finite state automata

Question

I want to write something that will draw finite state automata. Does anyone know any algorithms that are related to this?

EDIT: I should mention that I know about graphviz. I want to build my own draw program/function, so what I'm looking for is some more theoretical stuff/pseudo-code for algorithms.

Answer 1

Check out Graphviz. It's an open source graph visualization software.

EDIT: Check out the documentation section which links to some of the layout algorithms used.

Answer 2

Graph drawing is a fairly complex subject due to the fact that different graphs need to be drawn in different ways - there is no one algorithm fits all approach.

May I suggest the following resource:

• http://www.cs.brown.edu/~rt/papers/gd-tutorial/gd-constraints.pdf

It should be a good starting point, page 14 provides a number of links and books to follow up.

Answer 3

To get started with graph drawing algorithms, see this famous paper:

• "A technique for drawing directed graphs" (1993), by Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, Kiem-phong Vo, IEEE Transactions on Software Engineering.

It describes the algorithm used by dot, a graphviz drawing program. On the linked page you will find many more references. You will also find some more papers when you google for "drawing directed graphs".

Also, you might find OpenFst convenient, a general toolkit for finite-state machines. It has a binary called fstdraw, which will output a finite-state machine in a format that can be read by dot.

Answer 4

Maybe, I'm a little late in answering this question. Anyway this is a very comprehensive reference to the different types of graphs and the algorithms to visualize them.

http://www.cs.brown.edu/~rt/gdhandbook/