Projects About AlBasmala
build status

org-special-block-extras: Org lists, drawn as Graphviz graphs

Article image
  

Ξ  

⭐ The code lives at github.com/alhassy/org-special-block-extras —star it, or discuss it there!

1. An outline is already a graph

Say we are showing a friend how 1 * 2 + 3 - 4 parses. On paper, we would draw a tree. In Org, we would reach for Graphviz —and write that tree a second time, in a second language: 

digraph { "-" -> "+"; "-" -> 4; "+" -> "*"; "+" -> 3; "*" -> 1; "*" -> 2; }

Every arc there restates what an outline's indentation already says. So we write the outline, and let the outline be the graph. Each demo in this README shows what we write, then what we get:

﴾What You Write﴿ 
#+begin_graph
+ -
  + +
    + *
      + 1
      + 2
    + 3
  + 4
#+end_graph
﴾What You Get﴿
- + 4 * 3 1 2

That is the whole idea. A #+begin_graph block compiles the Org we already write —nested lists, two-column tables, links, tags, footnotes— into Graphviz dot. Nesting is an arc; the rest of this README refines that one sentence, one gap at a time, and every example stays with our running theme: parsing 1 * 2 + 3 - 4, from characters to tokens to trees.

A wide graph shrinks to fit the page; a click on it shows it full size, and another shrinks it back.

1.1. Setup

org-graph-block extends org-special-block-extras: 

(require 'org-special-block-extras)
(require 'org-graph-block)

Graphviz must be on our PATH: dot -V should work in a terminal.

1.2. A REPL for pictures

The fun part is how quickly a picture grows. Start with the seven tokens as a flat list, one item each, and press C-c C-c anywhere in the block: seven lonely nodes.

﴾What You Write﴿ 
#+begin_graph
+ 1
+ *
+ 2
+ +
+ 3
+ -
+ 4
#+end_graph
﴾What You Get﴿
1 * 2 + 3 - 4

Now M-S-<right> demotes an item, children and all —Org's own list editing— and another C-c C-c shows the new arc. A minute later, the flat list is the tree above. (Plain M-<right> demotes the item alone, leaving its children behind, as anywhere in Org.)

C-c C-c renders a PNG and links it beneath the block, under #+RESULTS:. The file's name is made up, unless :file picks one, as in #+begin_graph :file parse-tree.png. When the picture surprises us, C-u C-c C-c shows the generated dot instead; see Comforts while editing.

2. Arcs that speak: description lists

A bare arc says “related”, and little else. Explaining how our expression becomes a value, we want each arc to say how: the source text is lexed into tokens, which are parsed into a tree. Org's description list, - TERM :: DEFINITION, already attaches a word to an item; in a graph, that word sits on the arc into the item. Read left to right, the line is the arc —source, then lexed into, then tokens:

﴾What You Write﴿ 
#+begin_graph :rankdir LR
+ ="1 * 2 + 3 - 4"=
  + lexed into :: tokens
    + parsed into :: syntax tree
      + evaluated to :: -1
      + compiled to :: bytecode
#+end_graph
﴾What You Get﴿
"1 * 2 + 3 - 4" tokens lexed into syntax tree parsed into -1 evaluated to bytecode compiled to

Two arcs between the same nodes are just two items. A parser both consumes its tokens and peeks at the next one, unconsumed; two arcs, one stream:

﴾What You Write﴿ 
#+begin_graph :rankdir LR
+ parser
  + consumes :: token stream
  + /peeks at/ :: token stream
#+end_graph
﴾What You Get﴿
parser token stream consumes peeks at
  • The term may be marked up, as /peeks at/ is; it is then an HTML-like label.
  • It is the terse spelling of | :edge.label | consumes |, met below; an explicit :edge.label row wins.
  • A top-level item has no arc into it, so a term there is an error —except for a legend entry, met later.
  • As in Org, the :: needs whitespace on both sides: std::vector is a name, not a description, and so is BNF's expr ::= term, as ::= is not ::.

4. Ids and labels

Links make us name things, and a name wants to be short where a label wants to be clear. So every node has an id, which arcs and links name, and a label, which is drawn. By default both are the item's text, so these three items, spelling it out more and more, all declare one and the same node:

﴾What You Write﴿ 
#+begin_graph
+ expr

+ <<expr>> expr

+ expr
  | :id   | expr |
  | label | expr |
#+end_graph
﴾What You Get﴿
expr

When the two should differ, we set either one apart: a <<target>> or an | :id | row gives the id, and a | label | row gives the label:

﴾What You Write﴿ 
#+begin_graph
+ <<expr>> Expression
  + Term
    | :id | term |
    + factor
      | label | Factor: a number, or ( expr ) |
      + [[expr]]
+ Sum
  + [[term]]
#+end_graph
﴾What You Get﴿
Expression Term Factor: a number, or ( expr ) Sum
  • The id is the :id row, else the <<target>>, else the text —sans markup, links, footnotes, and tags.
  • The label is the label row, else the text; markup makes it an HTML-like one.
  • Two items with one id are one node, so an item may appear twice to gain more children.

5. Styling: one key-value syntax

Out of the box, Graphviz draws black ellipses; soon we want our tokens boxed and our rules round. Graphviz's attributes are key-value pairs, and Org's key-value syntax is the two-column table. So a table beneath an item styles that item: one syntax, from a single node up to the whole graph.

5.1. A node's table, and two kinds of keys

In a parse tree, the leaves are tokens, straight from the lexer; we box them, so they read apart from the grammar's rules:

﴾What You Write﴿ 
#+begin_graph
+ term
  + factor
    + NUMBER 1
      | shape | box   |
      | :id   | one   |
  + STAR
    | shape | box |
    | label | *   |
  + factor
    + NUMBER 2
      | shape | box |
#+end_graph
﴾What You Get﴿
term factor * NUMBER 1 NUMBER 2

A plain key, such as shape, is a Graphviz attribute of the node, passed straight through. We quote its value for you, so NUMBER 1, #00ff00, and x -> y all need no quotes; already-quoted values, and <…> HTML labels, are left alone.

A key starting with a colon is reserved: it means something to the graph block itself, never to Graphviz. A leading colon is never a Graphviz attribute, so the two kinds cannot clash. The reserved keys are listed in org-graph-reserved-keys; each is met in due time:

Key Meaning
:id the node's name for cross-references; else its <<target>>, else its text
:edge.KEY attribute KEY of the arc from the parent
:edge[T].KEY attribute KEY of this item's arc to T
:inherit inherit the rows of #+name: templates; also :NAME: tags
:children-rank { rank=… } over this item's immediate children

An unknown :key is an error, rather than a silently ignored attribute.

5.2. An arc's table: :edge.KEY

An arc is drawn from parent to child, so the child's table is where it is styled: an :edge.KEY row there is attribute KEY of the arc into the item. Every attribute is its own row, exactly like a node's. Peeking consumes nothing, so its arc should look tentative:

﴾What You Write﴿ 
#+begin_graph :rankdir LR
+ parser
  + consumes :: token stream
    | :edge.penwidth | 2 |
  + /peeks at/ :: token stream
    | :edge.style | dashed |
    | :edge.color | gray   |
#+end_graph
﴾What You Get﴿
parser token stream consumes peeks at

A reference is styled just the same; this is why an inline link graduates to one. The recursion back to expr is the arc that makes our grammar interesting, so we paint it:

﴾What You Write﴿ 
#+begin_graph
+ <<expr>> expression
  + term
    + factor
      + number
      + in parentheses :: [[expr]]
        | :edge.color     | red |
        | :edge.fontcolor | red |
#+end_graph
﴾What You Get﴿
expression term factor in parentheses number
  • A parallel arc is simply a second child, styled on its own; a KEY given twice is an error.
  • As in Org, an item's tables and directives may also follow its sub-items; they still belong to it.

5.3. The whole graph: the #+begingraph line

Small graphs deserve no preamble at all. So the header line takes the graph's title and any graph attribute; a parse tree laid out left to right, every node boxed, every arc grey:

﴾What You Write﴿ 
#+begin_graph How 1 * 2 + 3 - 4 parses :rankdir LR :node.shape box :edge.color grey
+ -
  + +
    + *
      + 1
      + 2
    + 3
  + 4
#+end_graph
﴾What You Get﴿
How 1 * 2 + 3 - 4 parses - + 4 * 3 1 2
  • The title, the words before the first :key, is the graph's label; :directed nil makes the graph undirected, with -- arcs.
  • :KEY V is a graph attribute; :node.KEY V and :edge.KEY V are node and edge defaults —the same KEY, node.KEY, edge.KEY spelling as table rows.
  • As on Org's own #+attr_html: lines, values need no quotes: :bgcolor #6c7086, :fontname Helvetica,Arial. A value with spaces does: :fontname "Helvetica Neue".
  • :file, :svg, :directed, :wrap, :notes, :unflatten, :unknown-tags, :smartdiagram, :dpi, and :C-c_C-c belong to the block itself, never to Graphviz; each is met below. So do the Babel habits :exports and :results, which the block ignores; and :demo, which every block of this package understands.

5.4. When the preamble outgrows the line

A real graph's settings outgrow one line. Then #+graph:, #+node:, and #+edge: name what the table below them styles —the graph, every node, every arc— and they override the header. A drawer of any name, :SETTINGS: or :PALETTE:, folds them away with TAB, along with #+rank: and #+name: lines:

﴾What You Write﴿ 
#+begin_graph A compiler's front end
:SETTINGS:
#+graph:
| rankdir  | LR        |
| fontname | Helvetica |
#+node:
| shape    | box       |
| style    | rounded   |
| fontname | Helvetica |
#+edge:
| fontsize | 10   |
| color    | gray |
:END:
+ characters
  + lexer :: tokens
    + parser :: syntax tree
#+end_graph
﴾What You Get﴿
A compiler's front end characters tokens lexer syntax tree parser

5.5. Subtrees inherit #+node:, #+edge:, and #+rank:

Sometimes a style belongs to one branch, not the whole graph. A compiler folds constants: 1 * 2 is known before the program runs, so its whole subtree collapses to 2. We want that subtree shaded. Org's properties are inherited: a :PROPERTIES: drawer on a heading reaches its subheadings. So it is with an item's #+node: and #+edge: tables: they style every node and arc beneath the item, while the item itself keeps its own | key | value | rows; its #+rank: lines apply there too:

﴾What You Write﴿ 
#+begin_graph Constant folding
+ -
  + +
    + *
      | xlabel | folds to 2 |
      #+node:
      | style     | filled    |
      | fillcolor | lightgrey |
      #+edge:
      | style | dotted |
      + 1
      + 2
    + 3
  + 4
#+end_graph
﴾What You Get﴿
Constant folding - + 4 * folds to 2 3 1 2

Above, * keeps its plain look —only what lies beneath it is shaded— just as a heading's own properties drawer is not one of its subheadings'. Graphviz scopes such defaults by an anonymous subgraph, which draws no box. A deeper item's tables override a shallower one's, as nested :PROPERTIES: do; a node first declared elsewhere keeps the defaults of where it was declared.

6. Saying it once: templates

A parse tree repeats itself: every token the same box, every rule the same ellipse. Restating those rows at each leaf is how styles drift apart. So we name them once: a #+name: table is a reusable bundle of rows, and a tag applies it. On a headline, :work:urgent: classifies the entry; on an item, tags classify the node:

﴾What You Write﴿ 
#+begin_graph
#+name: token
| shape     | box       |
| style     | filled    |
| fillcolor | lightblue |
#+name: rule
| style | bold |

+ expr :rule:
  + term :rule:
    + NUMBER 1 :token:
    + STAR :token:
      | label | * |
    + NUMBER 2 :token:
  + PLUS :token:
    | fillcolor | pink |
  + NUMBER 3 :token:
#+end_graph
﴾What You Get﴿
expr term PLUS NUMBER 3 NUMBER 1 * NUMBER 2

Explicit rows win over a template's, so PLUS above is pink. A line may carry several tags, :token:rule:, each a template, the earlier winning on a clash. The same rule reaches every other line a template could apply to; after a reference, or a description term, a tag styles the arc:

Line What its tags style
+ NUMBER 1 :token: the node
+ [[expr]] :recursion: the arc to the reference
+ reduces :rule-arc: :: expr :rule: the arc, by the description term's tags; the node, by its own
#+node: :token: every node; likewise #+edge: and #+graph:
#+name: keyword :token: the template keyword, which inherits token
﴾What You Write﴿ 
#+begin_graph
#+name: recursion
| color | red    |
| style | dashed |
#+name: keyword
| fontname | Courier |
#+node: :keyword:

+ <<expr>> expression
  + term
    + factor
      + in parentheses :recursion: :: [[expr]]
#+end_graph
﴾What You Get﴿
expression term factor in parentheses

6.1. Tags are sugar for :inherit

Each tag is terse sugar for an :inherit row, which names one or more templates and is often the clearer choice in a long-lived graph: | :inherit | token | in an item's table or under #+node:, | :edge.:inherit | recursion | for the arc into an item. Wherever it sits, the item's explicit rows still win:

﴾What You Write﴿ 
#+begin_graph
#+name: token
| shape | box |
#+name: recursion
| color | red |

+ <<expr>> expression
  + NUMBER
    | :inherit | token |
  + [[expr]]
    | :edge.:inherit | recursion |
    | :edge.label    | ( … )     |
#+end_graph
﴾What You Get﴿
expression ( … ) NUMBER
  • A template may inherit others; one that, directly or not, inherits itself contributes nothing the second time.
  • A name that no #+name: defines is an error, rather than a silent nothing.

As with Babel's named tables, a #+name: table anywhere in the buffer, outside any graph, is a template every graph in the buffer may use; so a house style is named once per file rather than once per graph. A graph's own template of the same name wins, and a template inside one graph stays that graph's own:

﴾What You Write﴿ 
#+name: token
| shape | box |

#+begin_graph Lexing
+ 1 * 2 :token:
  + NUMBER 1 :token:
  + STAR :token:
  + NUMBER 2 :token:
#+end_graph
﴾What You Get﴿
shape box
Lexing 1 * 2 NUMBER 1 STAR NUMBER 2

6.2. Which colons are tags

Tags are trailing :word: groups, exactly as on a headline; inside graph blocks, they wear Org's org-tag face, so they do not read as part of the label. Colons anywhere else are just text. A label that needs a trailing :word: of its own —Smalltalk's at:put: selector, say— puts it in =verbatim=, or in a | label | row:

﴾What You Write﴿ 
#+begin_graph Colons that are just text
#+name: faint
| style | dotted |

+ Python's xs[1:2]
+ C++'s std::vector
+ BNF's expr ::= term
+ Smalltalk's =at:put:=
+ a token, read at 12:30 :faint:
#+end_graph
﴾What You Get﴿
Colons that are just text Python's xs[1:2] C++'s std::vector BNF's expr ::= term Smalltalk's at:put: a token, read at 12:30

Unlike Org's, our tags may be kebab-case: :rule-arc:. A tag naming no template is an error, rather than a typo silently becoming part of the label.

6.3. Prototype first, name later

That strictness is right for a finished graph, and in the way of a sketch: while prototyping, we want shapes before names. #+begin_graph :unknown-tags random-templates makes up a template for each unknown tag —a colour, a shape, a font— the same at every use, so the tags read at a glance. A legend entry gives each its meaning; when the design settles, #+name: tables replace the made-up templates, one tag at a time:

﴾What You Write﴿ 
#+begin_graph Prototype first, name later :unknown-tags random-templates
#+begin_cluster Legend
- :rule: :: a grammar rule
- :token: :: a token
- :literal: :: a literal
#+end_cluster
+ expr :rule:
  + term :rule:
    + NUMBER :token:
      + 1 :literal:
    + STAR :token:
  + PLUS :token:
#+end_graph
﴾What You Get﴿
Prototype first, name later Legend a grammar rule a token a literal expr term PLUS NUMBER STAR 1

The Nth unknown tag takes the Nth of org-graph-random-template-colours, -shapes, and -fonts, so renders are stable, and the first eight tags differ in every way.

6.4. Legends are description lists

A reader meeting blue boxes and red dashes asks what they mean. A legend answers: a glossary of templates. Org's glossary is the description list, so a top-level - :T: :: MEANING —which has no parent to arc from— is a legend entry: a sample styled by template T, captioned MEANING. Wrap the entries in a #+begin_cluster to box them:

﴾What You Write﴿ 
#+begin_graph
#+name: token
| shape     | box       |
| style     | filled    |
| fillcolor | lightblue |
#+name: recursion
| color | red    |
| style | dashed |

+ <<expr>> expression
  + term
    + factor
      + NUMBER :token:
      + [[expr]] :recursion:
#+begin_cluster Legend
- :token: :: a token, from the lexer
- :recursion: :: /back/ to an enclosing rule
#+end_cluster
#+end_graph
﴾What You Get﴿
Legend expression term factor NUMBER a token, from the lexer back to an enclosing rule
  • The legend can never drift from the graph: change recursion, and its sample changes too.
  • A template that styles some arc in the graph —by a reference's or a term's tags, an :edge.:inherit row, or an #+edge: line— is sampled as an arc; any other, as a node.
  • …~, sample their templates together.
  • The sample drops constraint, which shapes the layout rather than the arc.

6.5. Checkboxes are templates

A checkbox says how far along a thing is; so a graph of tasks is just a checklist. Our calculator's compiler is half built. [X], [-], and [ ] apply the templates checked, partial, and unchecked, as a :checked: tag would; and C-c C-c on a checkbox toggles it, as Org's own does, then renders the graph:

﴾What You Write﴿ 
#+begin_graph Our calculator, so far
#+name: unchecked
| style | dashed |

+ [-] compiler
  + [X] lexer
  + [X] parser
  + [-] type checker
  + [ ] code generator
#+end_graph
﴾What You Get﴿
Our calculator, so far compiler lexer parser type checker code generator

checked and partial default to green and orange, by org-graph-checkbox-templates; a graph's own #+name: template wins. A checkbox whose template exists nowhere, such as unchecked by default, styles nothing.

6.6. Macros name single values

Templates name whole bundles of rows; sometimes we want to name one value. A palette repeats itself, and Org's #+macro: names a value once, so {{{name}}} uses it —in a table, an item, a cluster's header, anywhere in the block:

﴾What You Write﴿ 
#+macro: token-colour #a6e3a1

#+begin_graph Tokens, in one colour
+ 1 * 2
  + NUMBER
    | color | #a6e3a1 |
  + STAR
    | :edge.color | #a6e3a1 |
    | color       | #a6e3a1 |
#+end_graph
﴾What You Get﴿
Tokens, in one colour 1 * 2 NUMBER STAR

An undefined macro is an error. In similar spirit, inline src_LANG{…} blocks and call_NAME() calls run at export, as anywhere in Org, their results landing in the label; C-c C-c shows them as written.

7. Richer labels

A label is more than a name: we want a rule in bold, a token in monospace, a formula, a second line. Again, Org already has the syntax.

7.1. Markup makes rich labels

*bold*, /italic/, _underline_, +strike+, =code=, and ~pre~ in an item's text make its label an HTML-like one, while its id stays the plain text:

﴾What You Write﴿ 
#+begin_graph :rankdir LR
+ *expr* is =term= /op/ =term=
  + _left_ operand :: =term=
  + +ambiguous+ :: /fixed by precedence/
#+end_graph
﴾What You Get﴿
expr is term op term term left operand fixed by precedence ambiguous

We escape &, <, >, and " for you. Graphviz has no way to tell =code= from ~pre~, so both are monospace. A #+record: table's cells keep their markup too. Names such as a_b, C++, and org-graph.el are not mistaken for markup.

7.2. Entities, scripts, and snippets

Org's entities are their characters, and braced sub- and superscripts are Graphviz's own; as under Org's #+options: ^:{}, an unbraced a_b stays text, so snake_case ids are safe. For whatever Org has no markup for, a @@dot:…@@ export snippet is raw label HTML; a snippet for any other backend vanishes:

﴾What You Write﴿ 
#+begin_graph :rankdir LR
+ x^{2} \to pow(x, 2)
+ parse : String \to Tree \times String
+ token_stream
+ @@dot:<FONT COLOR="red">@@syntax error@@dot:</FONT>@@ at line 3
#+end_graph
﴾What You Get﴿
x 2 → pow(x, 2) parse : String → Tree × String token_stream syntax error at line 3
  • Timestamps, statistics cookies, and citations show as written; LaTeX fragments too, since Graphviz has no math.
  • Syntax that means nothing in a graph —a headline, a #+begin_quote, an unknown #+key:— is an error, rather than silently dropped. Comments, and footnote definitions, are fine.

7.3. \\ breaks a line, :wrap fills

A long label makes a wide node, and a wide node a sprawling graph. In Org, a \\ ending a line is a hard line break; in a graph, it breaks the node's label. Since a label seldom wants a literal \\, it may sit mid-line too, so a two-line node stays one terse line:

﴾What You Write﴿ 
#+begin_graph
+ parser
  + reports :: <<err>> Unexpected token =)= \\ at line 3, column 7
  + *Recursive descent* \\
    one function per rule
  + every grammar \\ needs a lexer :: lexer
#+end_graph
﴾What You Get﴿
parser Unexpected token ) at line 3, column 7 reports Recursive descent one function per rule lexer every grammar needs a lexer

The label becomes an HTML-like one, as with markup; the id joins the lines with a space, so a node reached by a link usually wants a <<target>>, as err above. It is the one line break wherever a label is written: a description term, as above; a table value, | :edge.label | consumes \\ tokens |; a #+record: cell.

Breaking every long label by hand is tedious, though. #+begin_graph :wrap N fills node and arc labels to lines of N characters, so long item text needs no \\ at all; a label already broken by \\ stays as written:

﴾What You Write﴿ 
#+begin_graph :wrap 20 :rankdir LR
+ A parser turns a flat stream of tokens into a tree
  + by repeatedly asking which grammar rule the next token can begin :: recursive descent
#+end_graph
﴾What You Get﴿
A parser turns a flat stream of tokens into a tree recursive descent by repeatedly asking which grammar rule the next token can begin

9. Layout: ranks, boxes, and records

Graphviz lays out the graph for us, and mostly well; but sometimes the layout says something the graph does not mean. Here is how we take the wheel back.

9.1. Ordered lists keep their order

Look again at our parse tree: 1 * 2 + 3 - 4 subtracts 4 from the rest, never the other way around, yet nothing in an unordered list promises Graphviz will draw 4 on the right. Org's + - * bullets say “these things”; 1. 2. 3. say “first, second, third”. So ordered children sit side by side, on one rank, in the order written —Graphviz no longer reshuffles them to save a crossing:

﴾What You Write﴿ 
#+begin_graph
+ -
  1. +
     1. *
        1. 1
        2. 2
     2. 3
  2. 4
#+end_graph
﴾What You Get﴿
- + 4 * 3 1 2
  • An ordered top-level list, or one inside a cluster, shares a rank too.
  • An explicit | :children-rank | min | wins over the rank=same; a lone ordered child gets no rank at all.
  • For one rank without the fixed order, use | :children-rank | same | with + bullets.

Nodes with no common parent share a rank by #+rank:, which takes bare ids or links; a link spares a multi-word id its quotes. Every token is a leaf, so we line them all up, as the lexer emitted them:

﴾What You Write﴿ 
#+begin_graph
+ -
  + +
    + *
      + 1
      + 2
    + 3
  + 4
#+rank: 1 2 3 4
#+end_graph
﴾What You Get﴿
1 2 3 4 - + *

Under splines=curved, Graphviz drops the label of an arc between two nodes on one rank; so there, such an arc's label becomes an xlabel, which it still draws.

9.2. Clusters draw boxes

Some nodes belong together —a compiler's front end, say— and a box around them says so. A cluster is a subgraph, so it gets the graph's own spelling: a #+begin_cluster block takes a title and :KEY V attributes, :node.KEY and :edge.KEY defaults included, exactly as the #+begin_graph line does; and, being a block, it folds with TAB:

﴾What You Write﴿ 
#+begin_graph :rankdir LR
+ compiler
  #+begin_cluster Front end :bgcolor lightgrey :node.shape box
  + lexer
    + parser
      #+begin_cluster
      + syntax tree
      + symbol table
      #+end_cluster
  #+end_cluster
  #+begin_cluster Back end :style dashed
  + code generator
  #+end_cluster
#+end_graph
﴾What You Get﴿
Front end Back end compiler lexer code generator parser syntax tree symbol table
  • A cluster block inside an item is that item's child: above, compiler has an arc to Front end. An arc to or from a cluster lands on the cluster's first node, clipped at its border.
  • An untitled cluster is an anonymous box, with no label and no name to draw arcs to.
  • The title runs up to the first :KEY; #+begin_cluster Time 12:30 is titled Time 12:30.
  • When the attributes outgrow the line, a table opening the block styles the box, as an item's table styles its node; #+node: and #+edge: tables set defaults inside it, as usual:
﴾What You Write﴿ 
#+begin_graph :rankdir LR
#+begin_cluster Tokens
| style     | filled  |
| fillcolor | #ddeeff |
#+node:
| shape | box |
+ NUMBER
+ PLUS
+ STAR
#+end_cluster
#+end_graph
﴾What You Get﴿
Tokens NUMBER PLUS STAR
  • C-c C-c, C-M-i, and eldoc work inside a cluster block just as anywhere else in the graph.

9.3. Records: a #+record: table

Some nodes have insides: an AST node has a left operand, an operator, and a right operand, and each arc should leave from its own field. A record is a node drawn as a table, and Org already has tables: under #+record:, an item's table is its label, laid out exactly as written —just as #+graph:, #+node:, and #+edge: name what the table below them is. A cell's <<target>> is its port, a cell's [[link]] is an arc from that port, and an arc reaches a port by record::port —just as Org's [[file:notes.org::target]] reaches into a file:

﴾What You Write﴿ 
#+begin_graph Our expression, as an AST
+ minus
  #+record:
  | <<l>> left [[plus]] | - | <<r>> right [[four]] |
+ plus
  #+record:
  | <<l>> left [[times]] | + | <<r>> right [[three]] |
+ times
  #+record:
  | <<l>> left [[one]] | * | <<r>> right [[two]] |
+ <<one>> 1
+ <<two>> 2
+ <<three>> 3
+ <<four>> 4
+ evaluator
  + starts at :: [[minus::l]]
#+end_graph
﴾What You Get﴿
Our expression, as an AST left - right left + right 4 left * right 3 1 2 evaluator starts at

Org tables have no merged cells, so two markers stand in for them: ^ continues the cell above, and an empty cell continues the cell to its left —or, in the first column, the one above. Together they draw any layout that Graphviz's old { } nesting could. A grammar rule with three alternatives spans its name over three rows; a token's heading spans its two fields:

﴾What You Write﴿ 
#+begin_graph
+ expr
  #+record:
  | expr \\ ::= | term =+= expr |
  | ^           | term =-= expr |
  | ^           | term          |
+ token
  #+record:
  | Token  |        |
  | <<kind>> kind | lexeme |
  | NUMBER | ="42"= |
#+end_graph
﴾What You Get﴿
expr ::= term + expr term - expr term Token kind lexeme NUMBER "42"

Hlines and column cookies mean what they mean to Org. An hline draws a rule between rows, and a table with any hline draws one outer border rather than a box around every cell —so a UML class is just the table we would write anyway. A row of <l>, <c>, and <r> cookies aligns its columns, and cells keep their markup:

﴾What You Write﴿ 
#+begin_graph
+ Parser
  #+record:
  | <l>                  |
  | *Parser*             |
  |----------------------|
  | tokens: =List Token= |
  | position: =Int=      |
  |----------------------|
  | parse(): =Tree=      |
  | peek(): =Token=      |
#+end_graph
﴾What You Get﴿
Parser tokens: List Token position: Int parse(): Tree peek(): Token
  • A record is otherwise an ordinary node: its children are nodes of their own, and its attributes, tags, and templates apply as usual; color, fillcolor, and fontcolor colour the table. Its attribute table goes above #+record:, since rows right below the record table are part of it.
  • A record is shape=plain, the table being its whole outline; an explicit shape row wins.
  • A cell with a link but no target is ported by its text, spaces as underscores; <<left operand>> is likewise reached as [[minus::left operand]].
  • Ports belong to their record, so all three records above have an l port: minus::l, plus::l.
  • A cell's trailing tags style its arcs, as a reference's style its arc: | <<l>> left [[plus]] :dashed: | draws a dashed arc. A cell with tags but no link is an error; write =:x:= for literal text.
  • a::b names a port only when a names a record; otherwise it is an ordinary node, such as std::vector. Record and port names may contain dots: [[org.el::v1.2]].
  • Graphviz spells ports record:port; that is the spelling in the generated dot.

9.4. Mind maps: :layout twopi

Every graph so far flows top to bottom; a mind map grows outward from its centre. Graphviz's layout attribute picks its engine, so the header line turns a tree into a mind map: twopi places root in the middle and each generation on a ring around it. With :wrap, long labels stay compact:

﴾What You Write﴿ 
#+begin_graph Parsing, radially :layout twopi :root Parsing :wrap 12 :directed nil :node.shape box :node.style rounded
+ Parsing
  + Top-down
    + Recursive descent
    + LL(k)
    + Packrat
  + Bottom-up
    + LR(0)
    + LALR(1)
    + Shift-reduce
  + Chart
    + Earley
    + CYK
#+end_graph
﴾What You Get﴿
Parsing, radially Parsing Top-down Bottom-up Chart Recursive descent LL(k) Packrat LR(0) LALR(1) Shift-reduce Earley CYK

Sans :root, twopi picks a centre itself. neato, fdp, and circo suit graphs that are not trees.

9.5. Wide trees: :unflatten N

A node with many children lays them out in one wide row: a ribbon, too wide for the page. Our lexer knows nine kinds of token:

﴾What You Write﴿ 
#+begin_graph Token kinds
+ token
  + NUMBER
  + IDENT
  + PLUS
  + MINUS
  + STAR
  + SLASH
  + LPAREN
  + RPAREN
  + EOF
#+end_graph
﴾What You Get﴿
Token kinds token NUMBER IDENT PLUS MINUS STAR SLASH LPAREN RPAREN EOF

:unflatten N passes the dot through Graphviz's own unflatten -l N, which staggers those leaves over N ranks, so the graph is a block rather than a ribbon:

﴾What You Write﴿ 
#+begin_graph Token kinds :unflatten 3
+ token
  + NUMBER
  + IDENT
  + PLUS
  + MINUS
  + STAR
  + SLASH
  + LPAREN
  + RPAREN
  + EOF
#+end_graph
﴾What You Get﴿
Token kinds token NUMBER IDENT PLUS MINUS STAR SLASH LPAREN RPAREN EOF

10. Graphs in their document

A graph rarely stands alone: prose refers to it, and an outline may already be one. Org's own document machinery reaches graphs too.

10.1. #+name: and #+caption: make a figure

We want to write “as Figure 1 shows”, and have the number stay right. In Org, #+name: is what [[links]] reach, and #+caption: captions a table or an image. A graph is an image, so both mean what they always do. Its point is an image file beside our document, so we show it as source alone: 

As parse-tree shows, =*= binds tighter than =+=.

#+name: parse-tree
#+caption: How 1 * 2 + 3 parses
#+begin_graph
+ +
  + *
    + 1
    + 2
  + 3
#+end_graph
  • The graph renders to parse-tree.png —both on C-c C-c and on export— and exports as that image, numbered and captioned: [[parse-tree]] reads “Figure 1” in HTML, and \ref in LaTeX.
  • An explicit :file still wins: #+begin_graph :file elsewhere.png renders there, and the #+name: still labels it. With :svg t, the figure is parse-tree.svg.
  • An unnamed graph exports as before: inlined into HTML, or as dot source elsewhere.

10.2. Sections are graphs: the :graph: tag

Sometimes a whole section is nothing but the outline we want drawn; wrapping it in a block is ceremony. A #+begin_graph block is a function on a region; a :graph: tag is the same function on a section. The section's text is the graph, and its :PROPERTIES: drawer —Org's own home for key-value settings— is the #+begin_graph line: :RANKDIR: LR is :rankdir LR, :NODE.SHAPE: box is :node.shape box, and :FILE: is :file:

﴾What You Write﴿ 
* Our grammar :graph_The_Grammar:
:PROPERTIES:
:RANKDIR: LR
:NODE.SHAPE: box
:END:
+ <<expr>> expr
  + term
    + factor
      + NUMBER
      + ( … ) :: [[expr]]
﴾What You Get﴿

Our grammar

The Grammar expr term factor ( … ) NUMBER
  • The heading stays a heading; only its text becomes the graph, on export.
  • :graph_The_Grammar: titles the graph The Grammar, as the words before the first :key would; plain :graph: leaves it untitled.
  • Org's own properties, such as :CUSTOM_ID: and :CATEGORY:, stay Org's; they never reach Graphviz.

11. Beyond Graphviz: smartdiagram

Graphviz lays out a graph; but a slide or a README's opening often wants something more posed than a layout. LaTeX's smartdiagram package typesets a handful of fixed pictures —a planet amid its satellites, a flow of boxes, a column of terms and their descriptions— that suit it better than any graph. :smartdiagram TYPE hands the very same list to smartdiagram instead; C-c C-c renders it with pdflatex, and LaTeX export typesets it in place. Our compiler's pipeline is a flow:

﴾What You Write﴿ 
#+begin_graph From text to value :smartdiagram flow:horizontal
+ characters
+ tokens
+ syntax tree
+ value
#+end_graph
﴾What You Get﴿
graph
  • TYPE is one of constellation, connected-constellation, bubble, flow, flow:horizontal, circular, circular:clockwise, descriptive, priority-descriptive, or sequence.
  • A constellation or bubble has one top item, its centre; that item's children orbit it. A descriptive diagram's items are + TERM :: DESCRIPTION. Every other type reads the top items, in order.
  • The #+graph: rows are \smartdiagramset's, in smartdiagram's own words: | planet color | black!75 |.
  • An item's | color |, | fontcolor |, and | fontsize | rows —Graphviz's names for them— colour its shape and its text, and size its text; its :tags: splice #+name: templates of those rows, as in any graph. An item's later paragraphs sit beneath its text.
  • The title sits above the diagram; prose before the list, between the two; prose after it, beneath.
  • :dpi N sets the PNG's resolution, 300 by default. C-u C-c C-c shows the LaTeX.
  • C-M-i and eldoc know which kind of graph they are in: under :smartdiagram, they offer smartdiagram's keys, with their defaults, rather than Graphviz's.
  • Graphviz's own syntax ---#+node:, #+edge:, #+rank:, links between items, records— draws nothing here, so it is an error rather than silently dropped.

11.1. Org's markup in place of LaTeX's

Why bother, when LaTeX could draw it directly? Here is a richer diagram, one that began life as a #+begin_src latex-as-png block, via ob-latex-as-png: a constellation of how one syntax, (key map), replaces many. Its #+graph: rows, macro, and colour links are where the LaTeX went:

﴾What You Write﴿ 
#+macro: replaces \\ [[color:gray][replaces]] \\ [[color:gray][=$1=]]

#+begin_graph One syntax =(key map)= \\ where =key= is =number=, =:keyword=, ='symbol=, or ="string"=! :smartdiagram constellation
#+graph:
| planet color              | black!75        |
| planet size               | 3.5cm           |
| planet text width         | 3.3cm           |
| satellite size            | 3.6cm           |
| satellite text width      | 3.5cm           |
| distance planet-satellite | 5.7cm           |
| connection color          | gray!60         |
| font                      | \small\sffamily |

+ *easy-access.el* \\ one syntax
  | fontcolor | white |
  + =(:k plist)= \\ [[color:gray][replaces]] \\ [[color:gray][=(plist-get plist :k)=]]
  + =(:k alist)= \\ [[color:gray][replaces]] \\ [[color:gray][=(cdr (assoc :k alist))=]]
  + =(:k hash)= \\ [[color:gray][replaces]] \\ [[color:gray][=(gethash :k hash)=]]
  + =(:field instance)= \\ [[color:gray][replaces]] \\ [[color:gray][=(record-field instance)=]]
  + =(n sequence)= \\ [[color:gray][replaces]] \\ [[color:gray][=(seq-elt sequence n)=]]
  + =(setf (:k p) v)= \\ [[color:gray][replaces]] \\ [[color:gray][=(map-put p :k v)=]]

-----

=(:school 'math "jasim" :names 2 my-nested-life)=

[[color:gray][replaces]]

#+begin_src emacs-lisp
(seq-elt (-> my-nested-life
             (map-elt :school)
             (map-elt 'math)
             (map-elt "jasim")
             person-names)
         2)
#+end_src
#+end_graph
﴾What You Get﴿
graph

Every LaTeX incantation it needed has an Org counterpart that we already write daily:

LaTeX Org
\smartdiagram[constellation diagram]{…} :smartdiagram constellation, over a nested list
\smartdiagramset{planet color=black!75, …} a #+graph: table, one row a key
\newcommand{\old}[1]{\textcolor{black!70}{\texttt{#1}}} #+macro: old [[color:gray][=$1=]]
\texttt{(:k plist)}, \textbf{…} =(:k plist)=, *…*
\mbox{\texttt{…}}, lest code break mid-circle nothing: code never breaks
\textcolor{black!70}{replaces} [[color:gray][replaces]]
{\color{white}…} on the planet a fontcolor row of white
\centering{One syntax … \\ …} above the diagram the block's title
\vspace{1em}{\textcolor{black!44}\hrule}\vspace{1em} -----
\hspace{7em} (map-elt :school), line by line a #+begin_src block, indented as we read it
% \new{(N xs)} \replaces … # + =(N xs)= …
\resizebox, \vspace, {\color{white} Bye!} padding nothing: the image is cropped to a small border

The LaTeX column is a second language inside our Org file: its macros, its colour syntax, and hand-tuned \hspace's that drift the moment a line changes. The Org column is the language the rest of the file is already in; it folds, links, exports, and completes like everything around it. The only backslashes that survive the move are \\ —which Org itself reads as a line break— and the font names, such as \small, that smartdiagram's own settings take as values.

12. Comforts while editing

Graphviz has 177 attributes, and nobody remembers them. So the block helps as we type, wherever we type.

  1. C-M-i (completion-at-point) and eldoc know about graph keys —in any Org buffer's graph blocks, and in the org-graph-edit-mode buffer that C-c ' opens on one, as for a source block:
    • In a key cell, completion offers the attributes valid there, plus the reserved keys; after :edge. or :edge[T]., it offers only edge attributes, prefix and all. In a value cell, it offers the values of that row's attribute, such as vee for :edge.arrowhead. Each candidate is annotated with its description.
    • On the #+begin_graph line, :r C-M-i offers :rankdir and the other graph attributes, every :node.KEY and :edge.KEY, and the block's own :file, :svg, :directed, and :C-c_C-c; :rankdir L C-M-i then offers LR.
    • Eldoc shows the description of the key on the current row, or at point on the #+begin_graph line, ending with Graphviz's default; e.g., | :edge.arrowhead | vee | shows “Style of arrowhead on the head node of an edge. Default: normal.”

  2. When we would rather pick than type, C-u RET on any table row inside a graph inserts a new | key | value | row interactively: a completion menu for the key, then one for the value —or a free-text prompt, when the attribute accepts arbitrary strings. Plain RET is unaffected. The menu shows only the attributes valid where the table sits:

    • Table under #+graph: ⟶ graph-level attributes (rankdir, splines, bgcolor, …)
    • Table under #+node: ⟶ default node attributes (shape, style, color, …)
    • Table under #+edge: ⟶ default edge attributes (arrowhead, dir, penwidth, …)
    • Table on a list item ⟶ node attributes, as above

    For a colour ---bgcolor, fillcolor, fontcolor, or color— the value is picked from Helm's colour list, when Helm is installed; RET inserts the colour's hex code, and its name as a comment. (This replaces our old ritual of M-x helm-colors, then C-z, then C-c r.) C-u RET works in the C-c ' buffer too.

  3. Where do the descriptions come from? org-graph-attributes, which lives on its own in org-graph-attributes.el: every Graphviz attribute, scraped from Graphviz's attribute table. To add or adjust one, edit its entry there, or M-x customize-variable RET org-graph-attributes; each entry has the form: 

    (:name "shape" :valid-on (nodes) :default "ellipse"
 :values ("box" "polygon" "ellipse" …)  ;; nil → free-text prompt
 :description "Sets the shape of a node.")

    Reserved keys are described by org-graph--reserved-key-docs, and the header's own keys by org-graph--header-key-docs.

  4. When the picture is wrong, we want to see what we built. C-u C-c C-c shows the generated dot in a *org-graph dot* buffer instead of rendering a PNG, and inserts —or replaces— a #+RESULTS: holding it as a #+begin_src dot block, so the source is preserved. For a block where we always want dot, :C-c_C-c dot in its header makes plain C-c C-c show dot, and C-u C-c C-c toggles back to PNG: the prefix always flips whatever the block's default is.
  5. The image C-c C-c renders is clickable. Hovering over a node or cluster shows its tooltip —its footnotes and notes— and a click follows it: to its link's target, when its item has a web, file, or [[*Heading]] link; else to the item itself, in the #+begin_graph block. Graphviz writes an image map (-Tcmapx) beside the PNG, from the same layout, and its areas become the image's :map; it is scaled as the image is, say by org-image-actual-width. The map lives only as long as the image does: an image Org redisplays itself, say on reopening the file, is clickable again after another C-c C-c.
  6. Big graphs make big PNGs; (setq org-image-actual-width 700) keeps them on screen. In an HTML export, a graph shrinks to the page's width by itself, and a click toggles its full size.
  7. In a :demo live graph, as throughout this README, C-c C-c still renders the graph: a live demo keeps no snapshot to take.

13. Reference

Once the demo is over, this is the page we keep open.

13.1. Syntax at a glance

Construct Dot equivalent
#+begin_graph TITLE graph [ label=TITLE ]
#+begin_graph :KEY V graph [ KEY=V ]; also :node.KEY V and :edge.KEY V; V needs no quotes
#+begin_graph :directed nil graph { … }, with -- arcs
#+name: N above #+begin_graph renders to N.png: a figure that [[N]] reaches, and #+caption: captions
* HEADING :graph:, with :PROPERTIES: the section's text is a graph; :RANKDIR: LR is :rankdir LR, and so on
:NAME: … :END: drawer the directives inside, folded away
#+graph: table graph [ … ]
#+node: table node [ … ]
#+edge: table edge [ … ]
#+rank: n1 [[n 2]] { rank=same; n1; "n 2" }
#+name: T + table style template T, used via :T: tags or :inherit rows; in or out of graphs
top-level - :T: :: MEANING a legend entry: a sample of template T, captioned MEANING
#+begin_cluster TITLE :KEY V subgraph cluster_TITLE { label=TITLE KEY=V … }
+ NAME list item node NAME declaration
indent + CHILD under + PARENT edge PARENT → CHILD
+ L :: CHILD under + PARENT edge PARENT → CHILD, labelled L
1. A, 2. B under + PARENT edges PARENT → A, B; { rank=same; A; B }, in that order
+ <<ID>> NAME node ID, labelled NAME
+ <<<NAME>>> node NAME; every item mentioning NAME arcs to it
+ NAME [[T]], + NAME [[T][L]] edge NAME → T, labelled L
+ NAME :T₁:T₂: node NAME, with templates T₁ and T₂ spliced in
+ NAME [fn::NOTE] node NAME, with tooltip=NOTE
a later paragraph of + NAME a note: NAME's tooltip, or beneath its label under :notes inline
+ NAME \\ MORE node NAME MORE, its label broken over two lines; likewise in table cells
+ NAME [[https://…]], [[file:x.png]] node NAME, with URL="https://…", or image="x.png"
+ [X] NAME, [-], [ ] node NAME, with template checked, partial, or unchecked, if defined
{{{M}}}, after #+macro: M V V, anywhere in the block
*b* /i/ _u_ +s+ =c= ~p~ an HTML-like label: <B>, <I>, <U>, <S>, monospace
∣ key ∣ value ∣ node attribute; values are quoted for you
∣ :id ∣ alias ∣ cross-reference name for this node
∣ :edge.KEY ∣ value ∣ attribute of the arc from the parent; each KEY at most once
+ [[T]] under + PARENT edge PARENT → T, a node declared elsewhere; record::port targets a port
∣ :edge[T].KEY ∣ value ∣ attribute of this item's arc to T, from a [[T]] link; see Strictly tables
∣ :inherit ∣ T ∣, ∣ :edge.:inherit ∣ T ∣ inherit template T's rows; explicit rows win
∣ :children-rank ∣ same ∣ { rank=same; <immediate children> }
∣ shape ∣ cluster ∣ subgraph cluster_ID { … } around the children; see Strictly tables
#+record: table under + NAME node NAME, labelled by that table; <<P>> in a cell is port P

13.2. Strictly tables: :edge[T].KEY and | shape | cluster |

Some of us prefer every attribute in a key-value table, never in the list's shape. Two spellings serve that taste; the examples above avoid them, but they are fully supported.

An inline link's arc is styled by :edge[T].KEY, naming the arc by where it goes; :edge[T].:inherit applies a template to it. A row with no [[T]] link in the item's text is an error:

﴾What You Write﴿ 
#+begin_graph
+ <<expr>> expression
  + term
    + factor [[expr][( … )]]
      | :edge[expr].style | dotted |
      | :edge[expr].color | red    |
#+end_graph
﴾What You Get﴿
expression term factor ( … )

A | shape | cluster | row makes an item a cluster, as #+begin_cluster does. Its children are then its members rather than arc targets, so arcs out of them are inline links, styled as above:

﴾What You Write﴿ 
#+begin_graph :rankdir LR
+ compiler
  + Front end
    | shape | cluster |
    + lexer [[parser]]
    + <<parser>> parser
#+end_graph
﴾What You Get﴿
Front end compiler lexer parser
Generated by Emacs and Org-mode (•̀ᴗ•́)و
Creative Commons License
Life & Computing Science by Musa Al-hassy is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License