Node graph layout library for incremental graphs

Question

I'm looking for a library to which nodes and edges can be supplied and which generates a coordinate list of all the nodes laid out nicely. However, it should be possible to supply fixed positions for some, but not all nodes which the layout algorithm should respect.

I have tried graphviz (fdp, neato) so far, which does not seem able to keep the position of certain nodes and built the layout around them.

The library has to be usable with python, so it should be either python or c/c++ so we could write our own binding.

The following pictures illustrates exactly what I'm looking for (this is the uDraw-project, which does not seem to exist as a library).

Answer 1

You can do this in graphviz in reverse, if that is useful to you. To do that, you would plot the right-hand graph first, and then plot the left-hand graph with nodes 15, 16 and 17 set to style=invis. That would give you much the same layout as is shown here.

A problem that I could perceive with plotting the left-hand graph first is that the software (dot or something else) would naturally try to plot a "nice-looking" graph without nodes 15, 16 and 17 and that might not leave enough space for nodes 15, 16 and 17 to be fitted in if they're needed later. For example, if we tried to insert a node 12a between nodes 11 and 12, there wouldn't be room for that node in the graphs shown above. On the other hand, if node 12a was initially plotted but invisible, then the software would allocate the space for it, where it could be included later.