DOT is a full-fledged language. I'm instead looking for a syntactic construct that I could use to create a whole new language (i.e. "S-expressions for general graphs")
S-Expressions are a language. They are a form of Pure Functional language needing only an interpreter.
Similarly DOT is a language. It needs only an interpreter.
If I have your measure, you are looking for a means to express any graph in a way that is both easy for a machine to interpret, and easy for a human to read.
In addition to the the above issues, Ko focuses on data-flow whereas I'm more interested in describing a graph's structure (i.e.: which vertex is connected to which other vertex).
Which leads me to confusion over why DOT, or a subset of the language is insufficient for your needs. Given that DOT primarily addresses the issue of connectivity in its syntax.
Tree's and S-Expressions
Trees are special forms of graph:
- with two dimensions
- each node is the parent once and the child at most once along the parent to zero or more children dimension (this gives an overarching partial ordering)
- each node is one of a set of siblings, possibly arranged in sequence. (either any order is acceptable or a 1-dimensional ordering is enforced)
This allows trees to be described syntactically by two operations:
- nesting (models parent/children),
- adjacency (models siblings).
Using such a scheme permits the identity and meaning of the node to be collocated and focused into a specific unbroken region of the description.
Unfortunately this does not generalise to the broader class of graphs for several reasons:
- Higher dimensionality more diverse forms of relationship)
- Each Node can have zero relationships (it is disconnected)
- Each node can have many relationships
- which can form cliques
- which can form cycles
- which do not necessarily impose even a partial ordering
- Hyper-Edges (that are composed of more than two nodes)
This precludes even DAGs which are similar to trees in many respects, the difference is that it is possible for a child to be nested under two parents.
By permitting references into the language you sacrifice locality of both identity and structure, but allow a node to be listed under more than one relationship.
id A = ('a', ('b', 'c'), 'd', 'e');
id B = ('g', A, G);
id C = ('f', A, C);
id G = (A);
A is just a tree.
B is a DAG Both
G refer to
C is a Cyclic Graph that refers to itself.
Obviously the shape of the graph is no-longer self-evident. But it is expressed.
Use Adjacency Lists/Tables.
Yes these are data-structures precisely because computer algorithms have to be able to express graphs in an interpret-able form. What they really are are methods for co-locating the important aspects of graphs such as vertices, and edges.
You could encode these syntactically:
graph = Directed(
But it is still difficult to get the measure of the graph, particularly when N >> 1.
Trial and Error
Frankly we don't have a known better means of expressing graphs syntactically. If we did it would be common place, DOT and S-Expressions are by far the best we have.
I would adopt either DOT( or a subset of it), or S-Expressions+References as a basic syntax for your graph language. I would only extend this for special cases of Graph/SubGraph that you frequently contend with, and only if it is arguably superior in terms of expression over an equivalent direct description.
For example say cliques are common,
clique('a', 'b', 'c', ...) could be a worthwhile extension.