DFAs and NFAs may seem like academic novelties but they are amazingly powerful for certain problems.
For example, naively searching a string of length N for P different substrings will yield an algorithm that has roughly O(N * P) worst case time complexity.
But implementing that algorithm as a DFA yields an efficient construction that has O(N) worst case time complexity.
This results in considerable speedups for complex pattern recognition tasks on large inputs, and yields other useful properties.
As a real world example, a CSV file can be parsed in parallel on a GPU by using a DFA based algorithm [1].
One downside to DFA representations is that they can be difficult to work with as linear text in your editor. Tikz produces great visualizations but I feel the syntax is a bit cumbersome. I’m still searching for that perfect text based format for DFAs - ideally one that can be visualized but also executed.
But implementing that algorithm as a DFA yields an efficient construction that has O(N) worst case time complexity.
I think it is worth saying that this is possible because finite state automata have a set of useful, well-understood operations, like concatenation, union, intersection, negation, kleene closure, determinization, and minimization. This makes it possible to generate complex automata from basic building blocks and to make them deterministic and minimal.
If I understand correctly, their work makes diagrams and code isomorphic. Meaning roundtripping between diagrams and code can be done with no loss, no impedance mismatch.
Meaning my long-time dream of a two-way structure editor is now feasible. Edit the diagram, the code updates. Edit the code, the diagram updates. Back and forth.
As you know, the Achilles Heel of CASE tools (and visual programming) has been the inability to roundtrip.
Do I understand correctly?
My science-fu is weak. I've been struggling to wrap my head around grammars and whatnot my entire career. Please forgive.
One of the elephants in the room of laying out node-arc diagrams is just how bad Graphviz is at the task. This sort of thing should be a core use case for Graphviz and it just isn't a good tool.
If anyone writes a Graphviz tutorial, it would be doing the world a service to prefix it with "But seriously, note that Tikz exists".
Do you mean that the graphs don't look good? They layout seems good, to me.
I have a Theory of Computation text so I have many, many such diagrams. I don't rely on the graphviz output directly. If I have to make a graph where the layout isn't obvious then I write a .dot file and run it through graphviz, specifically, neato. I use that as a model for drawing it with a LaTeX tool (I don't use TikZ, I use Asymptote, but the point is the same). That way I get a pretty good layout, better then I personally could do without the guidance from graphviz, and a visual consistency to the diagrams.
I've never really liked the look of the Tikz-generated automata. Something about them always looks a little off to me. I also dislike the use of 0 and 1 as the canonical alphabet. a and b look nicer, they stand out better in written instructions and solutions (when typeset using math mode), and (this sounds silly) sound nicer when talking about them with the class. Using 0 and 1 seems to imply some connection to binary that is not really there and probably confuses or misleads some students.
Of course, everyone will have a different opinion on such aesthetic matters. I taught an undergrad comp theory course for a decade or so and I wrote my own similar package[1] for generating diagrams using Metapost that built on the standard boxes package. Students were able to learn the system pretty quickly and the results were usually good, though it was pretty easy to pick out which students did/did not care about how things look.
Nice overview. One small nitpick: `right of=<label>` is deprecated, instead you should use `right=0cm of <label>` (after loading the `positioning` library), which is more flexible. If you don't want to specify the distance, there is also `right=of <label>`. See 17.5.3 in the manual.
The TikZ style should really be the default standard or even the bottom line. Last time I check Google Slides still doesn't understand how to connect two blocks of texts. I have to manually choose among four points (north/south/west/east of a block) to start or end a line. Whereas in TikZ the optimal point (among infinitely many points that constituent the border) is chosen.
Also, has anybody tried using Inkscape [1,2] or another vector drawing tool for this? I imagine it would be faster and more intuitive than learning Tikz.
I briefly looked at their website recently, and it looked to me like Penrose just renders the diagram interactively as a webapp. I didn't see a "compiler" that would translate the diagram code into a standalone PDF/PNG file that would be easy to include in a LaTeX document.
I find manually laying out graphs and digraphs tedious.
It seems like a problem that should be amenable to machine learning approaches. Basically, training a machine as to what is an aesthetically pleasing layout and what is not.
Are there layout engines that use machine learning for layout, as against being implemented in terms of specific tree or graph layout algorithms?
It would be nice if there were a tool that would take the input to graphviz, run it to graphviz to get the layout and then use that to generate the tikz code using that layout.
TikZ claims some support for automated graph layout generation in
chapter 26 of the manual [1]. It also lets you specify your own graph
layout algorithms in Lua. Results in my experience aren't as aesthetic
or intuitive as a custom layout but are comparable to graphviz.
Arguably a graph layout is performed by a kind of "training" in the sense that it takes many iterations for the parameters (and possibly physical distancing forces) to be evaluated for every node against all of the others. This is a solver, and not entirely unlike something like gradient descent. This is painting a rather broad brush with these terms, however.
I don't think the difficulty in making diagrams has to do creating a layout that is aesthetically pleasing, but rather with expressing ideas visually in a way that others can understand them. I'm sceptical that AI can help with that.
So repulsed by this. Learning custom DSL with opaque semantics that will leave you scratching your head when something goes wrong and tool behaves not like you expect. Why people opt into such tools at all?
Because those tools are well-known and they allow people to get the result they want. They also can be used for other things and are not specific to a particular kind of drawing.
Tikz also allows a tight integration to LaTeX documents that no external tools achieve so easily. The drawing inherits colors and fonts, and bits can be reused across the document and can be shared with other documents too.
High learning curve but long term efficiency with quality results.
Tikz is not perfect but it has the great characteristic of existing.
TikZ & pgfplots are really nice if you get over the initial learning curve and prefer programmatically defining things rather than drawing by hand.
E.g. in my theses all figures (except one in my first thesis) were made with TiKZ with colors and definitions defined in a file that is "imported" during compilation.
This allowed me to fine tune various parts (colors, ...) without having to touch each figure again.
Also, all the data files are stored as CSV and read/processed by LaTeX.
Between handing in my thesis and publishing the short-paper version of it for a conference I could rerun my analysis (to include the most recent data) with a single command and then just recompile the document to have all figures updated.
And TikZ graphics play somewhat nice with the beamer package. I found it easier to define transitions in technical figures with TikZ/beamer than with PowerPoint or any other tool so far.
In a summer internship I worked on the documentation of a project that tried to optimize pillar-placement for skilifts.
This was very Math/Physics heavy.
With TikZ I could define various parts (e.g. pillar, rope, gondola) as "function" and then create figures that combined these parts.
I.e:
- place pillars at these locations
- connect them with ropes obeying some formula
- put gondolas along the rope with some defined distance
Important points where marked with coordinates automatically, allowing explanatory nodes (text box with arrow or paths with labels) to be added (with full LaTeX support).
I cannot disagree. I was a fan of pic in the past for its much superior (IMHO) syntax, but I also envied tikz beautiful results (for it's based on tex rather than troff).
I haven't looked at that field for a good while but I'm still genuinely interested. And so I'd like to better understand your comment. It is unclear to me whether you are arguing in favor of using another similar tool using a better syntax, or using an automatic graph layout engine, or a manual general purpose vector drawing tool. How would you recommend one to draw such diagrams?
[+] [-] criticaltinker|4 years ago|reply
For example, naively searching a string of length N for P different substrings will yield an algorithm that has roughly O(N * P) worst case time complexity.
But implementing that algorithm as a DFA yields an efficient construction that has O(N) worst case time complexity.
This results in considerable speedups for complex pattern recognition tasks on large inputs, and yields other useful properties.
As a real world example, a CSV file can be parsed in parallel on a GPU by using a DFA based algorithm [1].
One downside to DFA representations is that they can be difficult to work with as linear text in your editor. Tikz produces great visualizations but I feel the syntax is a bit cumbersome. I’m still searching for that perfect text based format for DFAs - ideally one that can be visualized but also executed.
[1] ParPaRaw: Massively Parallel Parsing of Delimiter-Separated Raw Data https://arxiv.org/abs/1905.13415
[+] [-] microtonal|4 years ago|reply
I think it is worth saying that this is possible because finite state automata have a set of useful, well-understood operations, like concatenation, union, intersection, negation, kleene closure, determinization, and minimization. This makes it possible to generate complex automata from basic building blocks and to make them deterministic and minimal.
[+] [-] thaumasiotes|4 years ago|reply
They are the same thing as regular expressions. It's safe to say they're not being dismissed as academic novelties.
[+] [-] tomjen3|4 years ago|reply
[+] [-] CorrectHorseBat|4 years ago|reply
[+] [-] zingplex|4 years ago|reply
[+] [-] _vr9d|4 years ago|reply
[+] [-] jkhdigital|4 years ago|reply
[+] [-] specialist|4 years ago|reply
If I understand correctly, their work makes diagrams and code isomorphic. Meaning roundtripping between diagrams and code can be done with no loss, no impedance mismatch.
Meaning my long-time dream of a two-way structure editor is now feasible. Edit the diagram, the code updates. Edit the code, the diagram updates. Back and forth.
As you know, the Achilles Heel of CASE tools (and visual programming) has been the inability to roundtrip.
Do I understand correctly?
My science-fu is weak. I've been struggling to wrap my head around grammars and whatnot my entire career. Please forgive.
[+] [-] roenxi|4 years ago|reply
If anyone writes a Graphviz tutorial, it would be doing the world a service to prefix it with "But seriously, note that Tikz exists".
[+] [-] jimhefferon|4 years ago|reply
I have a Theory of Computation text so I have many, many such diagrams. I don't rely on the graphviz output directly. If I have to make a graph where the layout isn't obvious then I write a .dot file and run it through graphviz, specifically, neato. I use that as a model for drawing it with a LaTeX tool (I don't use TikZ, I use Asymptote, but the point is the same). That way I get a pretty good layout, better then I personally could do without the guidance from graphviz, and a visual consistency to the diagrams.
[+] [-] _russross|4 years ago|reply
Of course, everyone will have a different opinion on such aesthetic matters. I taught an undergrad comp theory course for a decade or so and I wrote my own similar package[1] for generating diagrams using Metapost that built on the standard boxes package. Students were able to learn the system pretty quickly and the results were usually good, though it was pretty easy to pick out which students did/did not care about how things look.
[1] - https://github.com/russross/automata/
[+] [-] opieters|4 years ago|reply
[+] [-] HPMOR|4 years ago|reply
[+] [-] ThinBold|4 years ago|reply
[+] [-] ashton314|4 years ago|reply
[+] [-] ogogmad|4 years ago|reply
Also, has anybody tried using Inkscape [1,2] or another vector drawing tool for this? I imagine it would be faster and more intuitive than learning Tikz.
[1] - https://stackoverflow.com/questions/17610717/drawing-an-undi...
[2] - The following appears to be part of a presentation: https://gould.cx/ted/presentations/txlf16/Technical%20Drawin...
[+] [-] goerz|4 years ago|reply
[+] [-] jes|4 years ago|reply
It seems like a problem that should be amenable to machine learning approaches. Basically, training a machine as to what is an aesthetically pleasing layout and what is not.
Are there layout engines that use machine learning for layout, as against being implemented in terms of specific tree or graph layout algorithms?
[+] [-] spockz|4 years ago|reply
[+] [-] gradschool|4 years ago|reply
[1] https://tikz.dev/gd-overview
edit: chapter 27 in the online version
[+] [-] th0ma5|4 years ago|reply
[+] [-] lottin|4 years ago|reply
[+] [-] RGamma|4 years ago|reply
[+] [-] artemonster|4 years ago|reply
[+] [-] jraph|4 years ago|reply
Tikz also allows a tight integration to LaTeX documents that no external tools achieve so easily. The drawing inherits colors and fonts, and bits can be reused across the document and can be shared with other documents too.
High learning curve but long term efficiency with quality results.
Tikz is not perfect but it has the great characteristic of existing.
[+] [-] oerpli|4 years ago|reply
E.g. in my theses all figures (except one in my first thesis) were made with TiKZ with colors and definitions defined in a file that is "imported" during compilation.
This allowed me to fine tune various parts (colors, ...) without having to touch each figure again. Also, all the data files are stored as CSV and read/processed by LaTeX. Between handing in my thesis and publishing the short-paper version of it for a conference I could rerun my analysis (to include the most recent data) with a single command and then just recompile the document to have all figures updated.
The thesis: https://www.ac.tuwien.ac.at/files/pub/hinteregger_18.pdf
And TikZ graphics play somewhat nice with the beamer package. I found it easier to define transitions in technical figures with TikZ/beamer than with PowerPoint or any other tool so far.
In a summer internship I worked on the documentation of a project that tried to optimize pillar-placement for skilifts. This was very Math/Physics heavy.
With TikZ I could define various parts (e.g. pillar, rope, gondola) as "function" and then create figures that combined these parts.
I.e: - place pillars at these locations - connect them with ropes obeying some formula - put gondolas along the rope with some defined distance
Important points where marked with coordinates automatically, allowing explanatory nodes (text box with arrow or paths with labels) to be added (with full LaTeX support).
[+] [-] andrepd|4 years ago|reply
[+] [-] rixed|4 years ago|reply
I haven't looked at that field for a good while but I'm still genuinely interested. And so I'd like to better understand your comment. It is unclear to me whether you are arguing in favor of using another similar tool using a better syntax, or using an automatic graph layout engine, or a manual general purpose vector drawing tool. How would you recommend one to draw such diagrams?
[+] [-] lrem|4 years ago|reply