Content-Type: text/shitpost

Mark Dominus (陶敏修) [email protected]

RSS Atom

I have another blog that doesn't suck.

25 recent entries

Archive:

Comments disabled

Graphiviz is useful graph- and network-layout software. You give it a description of a graph, as on the left:

    graph "example" {
        A -- B -- C
        B -- D, F [style="dotted"]
        D -- F -- E -- C
    }

and it produces a drawing of a graph as on the right. The first line says that node A is connected to B, which is connected to C. The second line says that B is also connected to D and F, but the edges should be dotted. The third line says that D is also connected to F, which is connected to E, which is connected to C.

Graphviz has several layout engines, which try to optimize layouts for different kinds of properties. The example above uses the neato layout engine, which tries for a generally compact layout. The example below gives the same input to the dot engine, which is intended more for directed graphs and which tries to emphasize hierarchies or flows among the nodes.

I built a Graphiviz configuration file for the graph of U.S. state boundaries and put it in to see what would come out. The graph is naturally planar, and it will be interesting to see if the layout algorithms can detect that.

Here's what the U.S. actually looks like. (Source: Wikimedia Commons)

This is the output of Graphviz's default layout engine, neato, which has done a great job of inferring the actual shape of the United States!

(Nodes here are labeled with their standard postal abbreviations. When you hover your pointer over a state name or other gegraphical designations in this article, the corresponding abbreviation will pop up. For example, New York should pop up a box with “NY”.)

The Mid-Atlantic, South Atlantic and Pacific coasts are clearly visible, Florida is dangling off the bottom, as it does. It's pretty amazing. The fact that the map is oriented correctly is a bonus. There are a few oddities: New England is where it should be, but Vermont should be switched with Connecticut and Rhode Island. South Carolina is sticking out into the Atlantic Ocean.

There is only one planarity failure, resulting from the inadvertent flipping of New England. The apparent crossing edge between Minnesota and Michigan is illusory; the edge could have been curved around Wisconsin with no trouble. (The real border between Minnesota and Michigan is a bit of an oddity, occurring in Lake Superior, and it really does leap over the head of Wisconsin that way.)

Here's fdp, which uses a similar approach to neato: a “spring” model where it imagines the nodes are connected by springs and tries to minimize the energy. It produces a very similar result:

It has New England flipped over like neato does. I wonder why that happened? And Washington is embedded in Northern California for some reason.

The sfdp engine is a variation on fdp which “uses a multi-scale approach to produce layouts of large graphs in a reasonably short time”. The map it produces has south at the top and east on the left, but otherwise looks pretty much like the fdp one. I'm pretty sure that by graphviz standards this is not a “large” graph:

Now we move on to the odd ones. The dot engine I mentioned before tries to maintain the hierarchy, to the extent that there is one.

The geography is still correct here, more or less, with South at the top and East on the left. That puts Florida in the upper left and Washington in the lower right. But in between it's unexpectedly tangled. The central column states, ND-SD-NE-KS-OK-TX are all over the place.

So many questions here. What the heck is going on with Ohio and Michigan? And Illinois and