-2

S-expressions are a well-known way of describing trees in high-level code.

Is there something similar for describing graphs?

The two closest things I've found are DOT and Ko. Both aren't quite what I'm looking for because:

  1. 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")
  2. 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).

closed as off-topic by gnat, Jörg W Mittag, amon, BobDalgleish, TZHX Feb 26 at 10:29

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions asking us to find or recommend tools, libraries, programming languages, resources (including books, blogs, tutorials, and examples), or projects to undertake are off-topic here as they attract opinionated answers that won't have lasting value to others. You may be able to get help in The Whiteboard, our chat room." – gnat, Jörg W Mittag, amon, BobDalgleish, TZHX
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
  • 1
    Is use an adjacency matrix the kind of answer you are looking for ? Or use an adjacency list ? Both are widely used ways of representing graphs in programs, and both matrices and lists are widely implemented in programming languages. It's not clear from your very brief statement of requirements what more you are looking for. – High Performance Mark Feb 21 at 14:51
  • @HighPerformanceMark, not really (unless I'm missing something). I'm looking for a syntactic representation, not a data-structure. – blz Feb 21 at 15:28
  • @ErikEidt This seems quite promising. If I'm splitting hairs, DOT is a full-fledged language, whereas I'm looking for a general syntactic construct. Lisp is to DOT as S-expressions are to X. Find X. (But thanks for this suggestion -- I'm digging into it) – blz Feb 21 at 15:30
  • My mind addled by too-long exposure to S-expressions and the like, I'm not sure I clearly see the difference between a syntactic representation and a data structure any more ... – High Performance Mark Feb 21 at 15:49
1

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.

References

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.

Broadly speaking:

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 B and G refer to A.
  • C is a Cyclic Graph that refers to itself.

Obviously the shape of the graph is no-longer self-evident. But it is expressed.

Alternatives

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(
    1: +-+--
    2: --+-+
    3: ++---
    4: --++-
    5: -----
    );

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.

  • This is an absolutely fantastic answer -- thank you very much. You indeed do have my measure, and I appreciate your clearing up my (multiple!) confusions. Thanks for teaching instead of downvoting; it's deeply appreciated. – blz Feb 22 at 12:02

Not the answer you're looking for? Browse other questions tagged or ask your own question.