Improving graphviz layout

问题:

I have perfection paralysis when it comes to producing something graphic. If symmetries of the visual have not been fully explored, I have a harder time comprehending what is going on. I am a very visual learner as well, and I LOVE to simplify things that I just learned and draw them on paper.

Graphviz is a nice tool to draw thing automatically, but it could be better. Let's start with an example of a good graph )a state machine rather). Never mind the quality (it can be redrawn with a better tool) this one is almost perfect, except that I would turn it counter-clockwise 45 degrees to make the symmetry apparent. It should then take the reader less time to figure out how the states q1 and q2 are similar and how where they differ. I argue that there is a single best way to represent that diagram, given that there are no other pieces of graphic next to it.

http://gallery.hd.org/_exhibits/maths/math-finite-state-machine-DHD.gif http://gallery.hd.org/_exhibits/maths/math-finite-state-machine-DHD.gif

Now let's look at a less than perfect depiction:

http://linux.softpedia.com/screenshots/Graphviz_1.png http://linux.softpedia.com/screenshots/Graphviz_1.png

This looks like something a graphviz would generate. Yes, the edges are smooth but GAAAAWWWD this is unnecessary confusing! It looks like a mind map, not a finished diagram ready for consumption. I believe that human eyes CRAVE (no less) symmetry. Yes, hierarchy, etc. are also important factors.

I am surprised that there aren't better algorithms available. Some people are not visual learners at all; they can grasp abstract concepts by reading symbols. Not me!

So, what is my question? Well, is there better free software available for drawing small-to-medium graphs? Perhaps

Thank you!

Let me know how I can improve this post.

P.S. I took 10 minutes to draw out a similar enough clone in dia. It is still not perfect, but it was convenient to make because everything snaps to grid (and I missed a few little details but do not feel like re-uploading). The LR_0 needs a "Start--->" coming from above to let the user grasp the starting state sooner.

Finate State Machine http://i47.tinypic.com/315e6w6.png

回答1:

After several attempts at drawing your graph and failing to get a layout that you deem "best", you posed the question here: is there "[b]etter free software [for] drawing small-to-medium graphs." The sole criterion you've given for evaluating layout algorithms is how closely they come to the "[s]ingle best way to represent that diagram." "Best" of course, left for you to decide.

This is more or less the same as attempting to solve a problem using a given programming language, failing, and then asking for a better programming language.

At the heart of graph drawing algorithms are optimization routines that generate then evaluation solutions ('solution' here refers to the coordinates for each node which together comprise a layout). Those solutions are evaluated according to minimization of a single criterion or a series of ranked criteria--i.e., the minimization of one or more attributes of the graph--for instance, the total number of edges that cross, or the sum of the distances between nodes (or the combination of both, or some weighted combination of those two), or the closeness to a symmetrical configuration. Graphviz is comprised of six different layout algorithms (dot neato, fdp, sfdp, twopi, and circo). Of these, it appears you only used dot; however, twopi and circo might have been better options given their strict symmetry constraints which appear to match your own idea of a correctly drawn graph.

Second, the text of your question is directed to "graphs" and graph-drawing, After reading your full description, i don't think your question has anything to do with either concept.

Beyond the general graph drawing algorithms (like graphviz), there are a number of domain-specific layout algorithms, for instance, Hasse diagrams (to represent partially ordered sets in order theory), Barabasi-Albert graphs (scale-free networks), and Erdos-Renyi (random graphs). Each of those algorithms produces a graph layout based on criteria and constraints supplied by the domain--this ought to indicate to you that there is not a single "best" layout across all domains. Although you used the term "graph" in your question, your description indicates that your problem relates to drawing state machines--a highly idiosyncratic type of graph. General graph drawing algorithms are often poor at drawing specialized graphs of this sort because the algorithm knows nothing about domain. In fact, I'm not aware of any layout algorithm for state diagrams--just like there isn't one for flow diagrams (not the same, but similar). Workflow-wise, you might draw the graph in graphviz then import it to Omnigraffle for fine tuning--in Omnigraffle, you'll have fine-grained control over the node and edge placements.

回答2:

There are a number of options i know of:

• Prefuse - They have an older Java version. The newest version is in Flash and has some nice layouts. Its called Prefuse Flare. The demo page illustrates some of its layout capabilities.
• JUNG includes a number of layout options, as well as its powerful graph analysis functions. There are some examples here.
• Networkx also includes numerous layout capabilities. Some of them are listed here.

回答3:

Some softwares let users tweaking layout algorithms in real-time, as long as moving nodes with the mouse. This approach may greatly help you for larger graphs.

I mostly know Gephi (disclamer: I'm a dev).

回答4:

TikZ generates beautiful graph layouts. You can use a manual layout that lets you specify the minimum of hints, or you can ask for automatic layout. Defaults are good, and hooks exist to tweak to perfection.

With the semi-manual layout you don't have to declare every detail, because you can

• declare nodes as being 'above of', 'below right of', etc. relative to other nodes.
• place your nodes on a raster by entering them as a matrix: very convenient if you want to leave some positions empty.
• easily specify in what direction edges should enter, leave, bend, or take corners

For automatic layout, TikZ's graphdrawing library has some pretty slick algorithms.

Here is an example of manual layout and the TeX code used to obtain it:

\usepackage{pgf}
\usepackage{tikz}
\usetikzlibrary{arrows,automata}
\usepackage[latin1]{inputenc}
\begin{document}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,
                    semithick]
  \tikzstyle{every state}=[fill=red,draw=none,text=white]

  \node[initial,state] (A)                    {$q_a$};
  \node[state]         (B) [above right of=A] {$q_b$};
  \node[state]         (D) [below right of=A] {$q_d$};
  \node[state]         (C) [below right of=B] {$q_c$};
  \node[state]         (E) [below of=D]       {$q_e$};

  \path (A) edge              node {0,1,L} (B)
            edge              node {1,1,R} (C)
        (B) edge [loop above] node {1,1,L} (B)
            edge              node {0,1,L} (C)
        (C) edge              node {0,1,L} (D)
            edge [bend left]  node {1,0,R} (E)
        (D) edge [loop below] node {1,1,R} (D)
            edge              node {0,1,R} (A)
        (E) edge [bend left]  node {1,0,R} (A);
\end{tikzpicture}
\end{document}