Anybody know of any tree/graph drawing software that can link edges?

Factual Questions
1

In my artificial intelligence class, we draw a lot of trees and graphs to represent states and searches and the like. Some of them, such as graphs or trees* for games using the MINIMAX algorithm or alpha-beta pruning, have some subtrees where the branches need to be AND-ed together; the resulting subtrees are called AND-subtrees, and the entire data structure is then referred to, logically enough, as an AND/OR tree.

My professor draws the AND-subtrees with arcs linking all of the edges to the nodes that should be AND-ed together. See this screenshot for an example; this is for a hypothetical game, and the AND and ORs work in a straightforward manner: in order for node B to represent a win, nodes E, F, and G must all be wins (since they have to be ANDed together), but the root node A is a win if any of nodes B, C, or D are a winner (one or more, in other words – since they’re ORed together).

So far, I haven’t been able to find any kind of tree or graph drawing software that lets me link subtree edges with the arcs (or straight lines, or anything at all) that represent that this particular subtree is an AND-subtree. So far I’ve just been copying the trees over to Word and drawing the arcs in manually, but that’s very time consuming and annoying.

So … does anybody know of any tree/graph drawing software that will let me link edges together like that? I’ve tried a couple of freeware programs such as uDraw (formerly known as daVinci) and TreeForm, but I can’t find anything that will join edges.

Any help is greatly appreciated!

  • I’m going to just say “trees” from now on, but I need something that can draw graphs too … although I guess a tree is just a particular kind of graph, so maybe I should say graph instead. Hmmm … no, I’ll stick with saying trees.
2

GraphViz is the shiznit for drawing directed and undirected graphs. You just provide a list of nodes, edges and labels in the proper syntax, and GraphViz will spit out an image.

There are various front-end programs that provide a nicer interface to generate the GraphViz code, but I’ve never used them.

ETA: I’m unsure if GraphViz has a feature for linking edges like you describe, but there are a lot of options which I’ve never explored.

3

Oh yeah – I was going to mention that one too. I just downloaded it five minutes before I posted my question, but I quickly abandoned it when I realized it wasn’t a quick-and-easy GUI but a “supply the list of nodes and edges and labels in the proper syntax” thing. (Which is very handy, if I can just get a decent GUI frontend for it for long enough to learn the proper syntax, because then I wouldn’t have to go through all the trouble of drawing out the graph every time – eventually I’d be able to slam out a few lines and have it automatically generate the graph. But at the moment, I need something quick and easy.)

But anyway … do you know if it can link edges like I mentioned? I briefly looked through the documentation, but I can’t tell on the site at the moment – some of the links on the documentation pages are giving me errors instead of … you know … actual documentation, at the moment.

4

You want Dia. I just downloaded it and tested, and it has the functionality you want. You can also anchor lines to nodes so they stay connected when rearranging the graph.

5

There’s a gallery on the graphviz site that has a lot of examples of the different sorts of graphs it can draw. I usually just grab the one that looks the most like what I want and modify it for what I need.

One of the most annoying things about it is that it can’t apply any formatting to the labels–so no underlines for the primary keys in your database, no subscripts for the state labels in your DFA, and so on and so forth. I’ll check out dia and see if it’s any nicer in that respect.

6

Thanks Dominic. Okay, I tried Dia. It’s pretty cool, but it seems to be more of a general diagramming tool (like Microsoft Visio) than a graph/tree drawing tool.

With TreeForm or uDraw or the like, I can add new nodes and have it automatically link to an existing node, thus making the new node a child/successor/neighbor of that existing node automatically and automatically moving around all the other nodes on that level (if it’s a tree) to make room for the new one, while maintaining the existing edges.

Whereas, as far as I can tell, with Dia I have to draw the nodes and position them by hand, so if I add another node to a particular level I have to reposition everything by hand. Is there a better way to use it that I’ve missed?

7

I was going to suggest using either Dia or Dot (a subpackage of graphviz; perhaps there’s a utility listed on the Wikipedia page that would be useful?). The only thing I have to add, since both have already been suggested, is that Dia can export Dot files. So you might draw them by hand in Dia, export, and then manipulate the .dot file.

But I’m interested in taking a gander at any other suggestions also…

8

I didn’t notice that Dia could do that. Thanks for pointing it out, that might be helpful. But ideally I’d like something that can automatically add nodes as children of other nodes, and the like …

TreeForm, for instance, lets you draw trees very quickly and does all the formatting as soon as you add the node. All you have to do is drag an up- or down-node from the menu onto an existing node, and then move the mouse left or right of any existing nodes to tell it where to put the new node.

So I guess my ideal package would be something that would let me draw trees/graphs quite simply like that, but would also have the flexibility of Dia to let me customize the tree/graph after the basic structure is done. It doesn’t sound like there’s anything quite right for me out there, though… although I still need to investigate GraphViz in detail.

Thanks for your help, everybody. And, of course, if anybody has any further suggestions, please share!