Project aim and design discussions

[mewmew]

This is a meta issue to discuss various design decisions related to the DOT package.

NOTE: This section is under construction, and will be revised based on continuous discussions, so feel free to join.

Aim and Objectives

The aim of this project is to create a general purpose package for accessing Graphviz DOT files, including both read and write support. To achieve this aim, a set of objectives have been identified.

• 1. Write a BNF grammar for the DOT file format and use Gocc to generate lexers and parsers.
• 2. Read support. Implement a translation from DOT AST to generic graph data structures.
• 3. Write support. Provide a means of translating generic graph data structures into DOT files (potentially using DOT ASTs which knows how to pretty-print themselves).
• 4. Read support. Support translating into gonum graphs
• 5. Write support. Support translating out of gonum graphs

Non-goals

An explicit non-goal of this project is to implement a specific graph data structure. Rather, it is intended to allow support for translating into and out of various graph data structures. We should make sure to investigate the feasibility of utilizing the gonum/graph package as the generic graph data structure. Where ever the graph data structure is defined, it should be as part of another repository, not the DOT repository. It is possible that a graphism/graph repo will be created for this purpose.

Public domain

The source code and any original content of this repository is intended to be released into the public domain. Anyone wishing to join the project are kindly asked to consider releasing their contributions into the public domain.

[suntong]

My #1 concern is the Licensing. Can we change it to Apache License Version 2.0 instead?

The reason is closely related to my second consideration, i.e., my assumption that this package is base on @awalterschulze's gographviz. So let's make that clear first, will this package be build from ground up, or it will fork @awalterschulze's gographviz first, and then enhance on it?

Either way, I think it'd be blessed to have @awalterschulze's endorsement. Otherwise, it might not go far. My opinion is fork first. Thus it comes to my #1 concern, because @awalterschulze released his gographviz in Apache License, thus the fork has to be in Apache License as well.

Thirdly, continue on the option of fork first, I had been thinking whether to patch upstream (to gographviz) or change it here. I admit that I had some strggle there. I first thought better patch upstream, so that we can get @awalterschulze involved in the enhancements.

However, now I'm thinking that forking into a different package is a better idea, because I think @Kargakis's Expose DOT-specific keywords makes perfect sense to me. However, the patch wasn't adopted because of the backward compatibly concerns -- "basically we have to return a runtime error, which breaks the API or we have to make it type safe and get a compile error, which also breaks the API". So we can keep gographviz as-is for old applications, and use this one for new feature enhancements. Thoughts, @awalterschulze @Kargakis?

[0xmichalis]

Why not extend the dot package in gonum/graph?

[suntong]

Actually I agree, at least on the principle that collaboration is much much more important than forking into separated islands.

However, somehow/somewhere I got the impression that

• first, gonum/graph is mainly for weighted graphs, and
• its dot package is solely for the purpose of outputing such graphs, not for analyzing Graphviz DOT files (both read and write support).

Not true?

[mewmew]

Why not extend the dot package in gonum/graph?

@Kargakis That's definitely a good option to investigate! I actually didn't know about the encoding/dot package of the gonum/graph repo until this evening. For what it's worth, this repository was intended as an experiment to get a fresh start, and see what the API may look like. It takes inspiration from @awalterschulze's gographviz, but also differs quite a bit. The lexer of gographviz is hand-written, while the dot lexer is generated by Gocc. The approach taken by gographviz to translate into the dot AST graph data structure, requires a large interface to be satisfied. The dot project takes a different approach, where a minimal dot AST graph is created from a gonum graph. The intention is to provide utility functions for annotating this minimal dot AST graph with attributes for nodes, edges and such. That way, the graph data structure may be kept clean, and does not need to know about the DOT format per se. Time will tell, if this is a good approach or not.

When the dot project matures a bit, and the API stabilizes, it would definitely be interesting looking into merging it with the gonum encoding/dot package.

its dot package is solely for the purpose of outputing such graphs, not for analyzing Graphviz DOT files (both read and write support).

As of commit 675a8f6 dot has preliminary read and write support, converting back and forth between gonum graphs. Support for undirected graphs and subgraphs have not yet been implemented. I'd be happy to see both read and write support for DOT graphs added to gonum, so merging this work into gonum, or taking ideas from it and contributing those back to gonum is definitely a direction I'd be happy with.

My #1 concern is the Licensing. Can we change it to Apache License Version 2.0 instead?

So let's make that clear first, will this package be build from ground up, or it will fork @awalterschulze's gographviz first, and then enhance on it?

@suntong Thanks for bringing this up! The project is indeed built from the ground up, obviously taking inspiration from @awalterschulze's gographviz library, as I've fallen quite attached to Gocc and enjoy writing grammars for languages in general. That being said, no code has been copied from the gographviz project, and the intention is to keep developing this project for the public domain. Obviously, if parts of the dot code are contributed to either gographviz or the gonum project, they are free to license it however they wish, as long as the original code of this repository remains in the public domain.

I need to go grab some lunch. Thanks for initiating the discussions @suntong and @Kargakis!

Cheers /u

[mewmew]

Side note, the API of the ast package is now considered stable (there may still be a few minor changes), while the API of the dot package is in a heavy flux and will definitely change within the days to come, while experimenting with different workflows.

[mewmew]

Also, the BNF grammar for DOT files is mostly complete (some minor cleanups remain), and the Gocc generated lexer and parser pass a rather extensive stress test using the official DOT test files of the graphviz project (see #2 for more details).

[suntong]

Thanks for the explanation.

The intention is to proved utility functions for annotating this minimal dot AST graph with attributes for nodes, edges and such. That way, the graph data structure may be kept clean.

Like that.

Support for undirected graphs and subgraphs have not yet been implemented.

Oh, I thought undirected graphs are simpler than directed graphs, :).

the Gocc generated lexer and parser pass a rather extensive stress test using the official DOT test files of the graphviz project.

Oh I like that very much.

cheers mate

[mewmew]

Oh, I thought undirected graphs are simpler than directed graphs, :).

Hehe, so did I. Most of my test cases are directed graphs however.

Just to be clear, undirected graphs are supported by the grammar (and thus by the lexer and parser). You can therefore read DOT files which contain undirected graphs, and they will be successfully parsed to an equivalent AST representation of the undirected graph, which knows how to pretty-print itself back to DOT format.

What still needs some love is the translation back and forth to the gonum graph representation. Translation of directed graphs is already support (with preliminary read and write support), but support for translation of undirected graphs is yet to be implemented.

[mewmew]

The intention is to proved utility functions for annotating this minimal dot AST graph with attributes for nodes, edges and such. That way, the graph data structure may be kept clean.

Like that.

I'm glad you like it. I also feel this is an approach which suits me well, as it creates a clear separation of concern.

[awalterschulze]

Sweet :)

[suntong]

Hi Robin,

What's the status of the dot project? stabled or stalled?

I remember that every official test case from Graphviz have been supported, is it so?

However, I do see from the thread that,

• "Support for undirected graphs and subgraphs have not yet been implemented."
• "The API of the dot package is in a heavy flux and will definitely change within the days to come."

Are these two statements still hold? Thx.

PS. Just want to know the current stage. No pressure actually.

[mewmew]

Hi @suntong,

Glad to hear from you.

What's the status of the dot project? stabled or stalled?

The dot project is still in an experimental stage. It should receive more love within the months to come.

I remember that every official test case from Graphviz have been supported, is it so?

This is true indeed. All official test cases of Graphviz are parsing and passing.

• "Support for undirected graphs and subgraphs have not yet been implemented."
• "The API of the dot package is in a heavy flux and will definitely change within the days to come."

Are these two statements still hold? Thx.

Yes, the dot package is still in an experimental stage. My friends and I have been playing around with an LLVM IR package for Go lately, and it has received most of our love and attention. The llir/llvm package is approaching feature completion however, and as such the dot package is next in line for receiving its well deserved love <3

This should happen in the next couple of months, at which point we will try to get up to speed with the gonum graph representation. Review if it has changed since last summer, and also look around in the Go ecosystem for other graph representations to learn from and look at other packages dealing with graphs.

The intention of the dot project is still, as previously indicated, to explore the feasibility of exposing a minimal API for parsing DOT files into ASTs of Graphviz dot files, and to implement utility packages for dealing with DOT attributes (e.g. adding background color to a set of nodes).

We still very much intend to implement support for undirected graphs, and will try to find a clean way of doing so. Our personal use cases still primarily involve directed graphs, which is why they have received most love so far.

Will provide an update/status report in a couple of months when we reinstantiate this work : )

Cheers /u

[suntong]

Wonderful! The only reason I asked is that I was afraid that the dot package might become an unfinished project. Now I'm quite at ease knowing that it will receive its love when the condition is ready.
That Go LLVM IR package looks really cool, BTW.
Keep up the good work, :) 👍

[mewmew]

As mentioned in #8, graphism/dot is now part of gonum/gonum :)