graphviz

The market rewards features and integration, not performance, as long as an app is usable. Developers devel... I mean features features features.

This may be a fallacy. It is all connected. Some of the connections are not obvious at first. It's very tempting to create interesting features for your own edification or satisfaction, and leave them nearly undocumented. Years later, kind-hearted strangers discover these in the code and wonder why no one knows about them. Sometimes, it's like code that you just wrote for yourself might as well not even exist for the rest of the world. That's just one facet of this situation.

If the software endures long enough, there is no 100%. The Just Works stage is not stable. The ground keeps shifting beneath your feet.

We wonder if the swig APIs are worth it. Comments?

The recent unfixed breakage of gvedit (the cross-platform Qt GUI) and deletion from the Windows build seems semi-tragic. Could use help there.

The difficulty of implementing parsers (for the majority of programmers or engineers) is one of the tragedies of computer science. It is a very well developed theory and apparently it is too hard to deliver in a usable form without becoming one of those "to bake an apple pie you need to invent the universe" experiences. I just wanted a pie! Like the html-ish parser in Graphviz:

  bison -y -Wno-yacc -dv ../../lib/common/htmlparse.y -o htmlparse.c
  ../../lib/common/htmlparse.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
  ../../lib/common/htmlparse.y: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples

Noted.

This partially explains the success of languages like XML, JSON and YAML as alternatives to writing your own parser.

Whether or not AT&T was far-seeing, they had a mandate to design and deliver universal telephone service, and cost-plus deal to pay for it, so it made sense to buy nice expensive things. Even when the mission was fulfilled and the economy started to restructure the company, it ran along for at least another 10 or 15 years before the real disruption started (the 1996 breakup that turned Bell Labs into Lucent). And even then, the labs contributed fundamental research in machine learning, quantum computing and databases, to name a few areas. As you say, that model of large-scale corporate R&D doesn't exist any more - there's no funding model to support it.

Nice work.

Hi, Alejo Hausner!

We worked on this problem, too, and Gordon Woodhull created a working system for dynamic hierarchical layout. I think he also incorporated an improved node positioning and edge routing algorithm of Ulrik Brandes. The code is still available here, I think: https://www.dynagraph.org

It was great work. We meant well, but were overextended for the resources we had. Gordon is a brilliant programmer.

In hindsight it seems so ridiculous that we appropriated the .dot suffix, but no one made us - we did that intentionally. Later we tried switching to .gv but everyone forgets sometimes.

Yesteryear?

Nice writeup, easy to follow.

Regarding improvements to crossing minimization, we're fans of Brandes and Köpf, "Fast and Simple Horizontal Coordinate Assignment" GD2001 that guarantees linear time and at most two bends per edge. (If anyone would like to implement this in Graphviz let us know!)

Regarding introducing additional constraints to address the problem that the algorithm "doesn't understand the sensible or hierarchical relationship between the blocks in my diagram" we're fans of Yoghourdjian, Dwyer et al, "High-quality ultra-compact grid layout of grouped networks" from IEEEVIS 2015. It looks quite difficult to implement. The figures in the paper took several minutes to generate and probably involved cutting and pasting between several tools.

A different approach was taken by Dwyer, Koren and Marriott, in "IPSep-CoLa: An Incremental Procedure for Separation Constraint Layout of Graphs" IEEEVIS 2006 where they introduce a kind of layering or asymmetry into force-directed energy models. This is implemented in Graphviz neato -Gmode=hier

Yes. Is there a specification for what we need to implement? The native SVG generator is easily modified.

Do you mean anchors as in clickable objects, or do you mean attachments points on nodes for incident edges that stay attached if the node is dragged?

In 30 years this is truly the first time anyone said "well-documented". "Very well documented." Yes. Actually a lot of credit goes to the inheritors of this project (Magnus Jacobsson, Matthew Fernandez, Mark Hansen, and a boost from Steve Roush and Costa Shulyupin) for bringing some sense of order and self-respect.

It's thrilling someone else noticed the Nocaj et al. Simmelian backbone paper. There is a directory somewhere on this computer of an implementation in graphviz that Emden Gansner wrote a couple of years ago. (It should at least be uploaded to graphviz gitlab so we don't ever lose it.) All we need now is a summer intern to finish the job. Sometimes it's natural to miss Bell Labs and even AT&T Labs a whole lot.

Thank you for mentioning the aesthetics in graphviz. It's not in any sense optimal; we chose a collection of heuristics meant to get somewhere close to diagrams made by hand (with tools). Some areas can clearly be improved. Even the initial ranking and cycle breaking is not always quite right. Possibly some of the middle stages need to be more aware of groups of nodes. How to draw sets of natural looking curves around obstacles in diagrams still seems to be an open problem, do we even know what to optimize? It's natural to ask if machine learning algorithms will get there first.

The graph drawing community extensively studied algorithms that update and "preserve the user's mental map" of various types of layouts. It's all heuristics anyway; sometimes they produce locally optimal layouts, but it's not as if extant layout systems are producing mathematically optimal layouts in general.

If you're not too fussy about results it might not be "that hard" to load a previous layout into dot, and optionally mark the nodes and edges that are allowed to be moved (or preferred not to be moved), and run the algorithms on that. It "just" needs someone to work on it, or pay for developers to do it. We wrote a paper about this in the mid 90s and Gordon Woodhull even got a successor of that to work, see dynagaph.org

Taking a broad view of the area, it's interesting that tables and networks are both fundamental ways of representing data in many situation, and often complementary, but the technology for working with tables is far more mature. This spans the low end of representation (CSV files, data frames in pandas) to database systems that provide essential capabilities like query languages and consistency checking, to entire application platforms like Oracle. The equivalent systems for networks aren't as mature. There's still a big opportunity to meet this need, and you can see a lot of progress in technology like NetworkX and Neo4J.

A great service that network programming systems provide, as highlighted in some of the comments here, is simply to provide a framework for integrating useful functions for operating or computing on networks so they can be delivered to a broad audience. To illustrate, in the land of tables, if I need to join two tables, and count rows or sort and show the top-N, I know what software on my computer does that. If I have a network and want to find a shortest path or do some other simple pattern matching on paths, and maybe show the result graphically, what am I supposed to use? It's really not clear.

And, in 2023, why not both? Applications need both tabular and network views of data, and in some ways they are not that different. That the popular relational data platforms have not already rushed in to fill this need give some reason to pause and consider the situation further or maybe is an argument that tables and networks should have similar importance.

From real life, maybe one issue is that the technology for computing on tables is pretty well understood and manageable, but there are a lot of sharp edges around combinatorial structures like networks. From a recent real-life example, say I just want to make an attributed network representing employees in a company, and match them for an internal project. Is this as easy as sorting rows in a table? Hardly. Can you even find a textbook pseudocode algorithm and code it in a graph query language that is recognizable as that algorithm? These look like tough problems. At least NetworkX and systems like it provide a framework to integrate those implementation for a developer audience.

This is such an excellent observation (about Graphviz); you can see some of the rough outlines of the primitives that might get the job done, and how they might be composed. This area is so ready for new work. There are also some problems that maybe don't arise the same way in stat graphics and charts for data journalism, like coping with nested layouts, stable dynamic layout, optimizing topological properties, and intricate combinatorial optimization problems, to name a few things.

Does anyone want to look at porting the mermaid layout method back to Graphviz? It might be useful to people. I guess some friction would be around the kind of awkward way that Graphviz has to deal with objects that aren't strictly nodes, edges, or subgraphs.

You can ask us anything here.

The community should applaud the efforts of Magnus Jacobsson, Mark Hansen, Matthew Fernandez, Steve Roush, and recently Costa Shulyupin to support graphviz in a more disciplined and professional way. In hindsight, we got a lot of play by treating Graphviz as a research vehicle, but we weren't able to (or didn't choose to) direct a lot of effort into documentation, rewriting existing code, sorting out feature interaction, developing very polished front ends, or broadening the scope of the effort. Or finding a new home after AT&T Labs lost its enthusiasm.

Good discussion. It may help to separate the different threads.

Business models that support network visualization: mostly, not such a great story. Customers want to solve problems, not just look at pictures of networks. Inevitably this drives the work toward domain-specific capabilities in areas like computer security, fraud detection or bioinformatics. It's a slippery slope. If you stay focused on core algorithms, your audience is other tool builders i.e. cost centers.

Scaling up network visualization: fascinating technical problem, but a human can't actually see a million objects at once or form a mental map of their locations. So it's more like a clustering problem. Not a big surprise that Graphistry adopted uMAP. It's treating nodes more like points in big plot. We're not concerned with the same problems as illustration quality rendering of small readable graphs.

Building your own: an appeal of network visualization is that you can get going by just writing some kind of physical simulation, assign reasonable coordinates to nodes, drawing edges as lines, and poof you're done. If your goal is consistently making concrete diagrams that look like a human drew them (with nodes that have shapes and ports, various kinds of labels, constraints on edge routing, nesting, aspect ratio control, etc.) there are so many intricate subproblems that you could spend years on any of them. But what's the financial incentive?

The research frontier: no doubt machine learning will eventually transform this domain the way it has many others. The combinatorial objectives of network diagramming make it challenging for now. (Can an algorithm learn orthogonal planar layouts with port constraints? Maybe. Would like to see that.) Another frontier is to extend general methods for declarative 2D layouts. People don't want just pictures of networks, they want more elaborate diagrams: computer networks, metabolic pathways, business processes, cryptocurrency transactions. Network visualization is only a subproblem in information visualization. This ties in to the first point, people need to solve problems in a specific domain.

I can't even expand half the acronyms in this article. When do people have time to work on anything besides keeping their "system" up to date. python-is-python2? Maybe use sed to write all your code, too.

Excellent question.

Hoping the community will work more on declarative 2D diagramming methods and tools.

Is this project basically the New Mermaid? Why not go in a new direction. People want diagrams, not just networks, not just series-parallel graphs. Anyway, ML is changing everything. Can Stable Diffusion make crossings at right angles? Just wondering.

That's interesting. It's not hard to see the problem. HTML labels don't help, either. How do other languages solve this? Like, a shell HERE document that has one fixed string as a terminator? The graphviz lexer https://gitlab.com/graphviz/graphviz/-/blob/main/lib/cgraph/... seems hackable but disabling downstream processing of escapes elsewhere would be necessary too. Possibly this would mean bypassing some of the processing in the function make_label in https://gitlab.com/graphviz/graphviz/-/blob/main/lib/common/...

It's a disappointment or even failure of our current language scanning and parsing tools or, really, the way we used them, that this is not an easy exercise.

It is surprising though maybe they gave a good initial placement?

That's right. The initial layout in neato (which is really statistical multidimensional scaling) treats nodes as points, then draws shapes on top of the points without considering overlap. overlap=false or overlap=prism invokes a second layout phase as described in this report: https://link.springer.com/content/pdf/10.1007/978-3-642-0021...

There may be better methods by now - it would be a good intern project to look at that.

It would be a good idea to simply take the state centroids as an initial placement and onyl run the overlap removal phase.

In edge routing, we were really impressed with the "repulsive curve" work by Keenan Crane at CMU, https://www.cs.cmu.edu/~kmcrane/Projects/RepulsiveCurves/ind... - scroll halfway down for the graph layout examples.

Where is the funding for this work? Customers want to solve end-to-end problems, now, so it's difficult to get support for deep work on a particular part of the visualization and analysis stack (for almost anything, not just code).

We think maybe we should add a layout alg. based on the input being relative or absolute grid position (plus maybe unconstrained nodes). Someone should create a summer intern project to get this started.

How do you measure "an order of magnitude better"?

What algorithmic or programming breakthroughs made that possible?

Where are your most impressive examples?