4 ms·

> Every graph can be represented by a 2-dimensional tree. do you have a good reference for this encoding? i vaguely recall seeing something like this in a pape

by uryga 6y ago

> Every graph can be represented by a 2-dimensional tree. do you have a good reference for this encoding? i vaguely recall seeing something like this in a paper, but can't remember any specifics

breck 6y ago
Here is the paper: https://github.com/treenotation/research/blob/master/papers/paper/treenotation.pdf https://github.com/treenotation/research/blob/master/papers/... It's not that traditional a style as I had no experience in academia until after I published it on arxiv, but I still stand by basically all of it. For the encoding all you need is 3 things: a node delimiter (generally newlines), a cell delimiter (generally tab or space), and an edge delimiter for parent/child relationships (generally reuse the tab or space from above). Think of a spreadsheet as a program, and that's the base encoding. From there you just need to define Grammars to get higher level constructs. This page (https://jtree.treenotation.org/designer/ https://jtree.treenotation.org/designer/) contains ~15 example grammars, including a grammar for grammars (similar to YACC or ANTLR). This is just the tip of the iceberg though, you can do really novel things with these languages that you don't see with all our traditional languages (like having N parse heads that start all over the place and move in all sorts of directions). So if you take these ideas and combine them with this "Statecharts" paper of 1987, what you would do is create a "Statecharts" Tree Language defining all the elements they have in that paper, and then people could write "programs" in this Tree Language, and then you could use the Compiler Compiler I linked to above to generate a compiler that reads those programs and either 1) compiles them to SVGs like they have in their paper or 2) generates 3-D visualizations where the program shape in the focus is unchanged.
- uryga 6y ago
  sorry, can't really find anything about graphs in there. how would use TN to represent a graph like this? A --> B --> C ^ | | | +-----------+
  - breck 6y ago
    A few options, depends on design of Tree Language. Here are a few programs using grammars following traditional top to bottom, left to right flows. A B C A A B C A A B C. A B C AB BC AB Verbose ones: ANode BNode CNode Edge ANode CAEdge ANode ABEdge BNode BCEdge CNode
    - uryga 6y ago
      ah sorry, i thought your OP was talking about a more graph-theory-ish thing, some fun bijection between trees and graphs or something, serialization isn't really what i had in mind re: TN stuff. don't take this the wrong way, but being able to serialize a graph into bunch of IDs+edges isn't very... remarkable. as in, you could also use JSON/YAML/XML/s-exprs or whatever format, they'd be kind of equivalent here (modulo punctuation). i mean, lightweight DSLs and homoiconicity are cool, but not really groundbreaking stuff --- PS (additional bit of unsolicited advice). afaik you're still looking for TN's "killer app"; i'd consider making something geared towards the org-mode/markdown/plain-text-everything crowd, because TN's advantage is conciseness + ease of input/editing + aesthetics. maybe it could find its niche as a markdown++/org-mode-ish thing where you can freely mix text with structured bits (DSL stuff would be handy here)
      - breck 6y ago
        I hear what you are saying, but there is a big leap between TN and "JSON/YAML/XML/s-exprs". One is isomorphic to 2 and 3 dimensional structures, and the rest are not, connecting the software world to the physical world. This will turn out to be very important and groundbreaking.
        nsajko 6y ago
        > One is isomorphic to 2 and 3 dimensional structures, and the rest are not So you're saying your notation can encode graphs that can't be represented as, e.g., JSON? The existence of such a graph would be the real (math-breaking) discovery here, no? I.e., you really should be able to give an example before offering such statements... > connecting the software world to the physical world I'm really not following you here.

by uryga 6y ago

> Every graph can be represented by a 2-dimensional tree. do you have a good reference for this encoding? i vaguely recall seeing something like this in a paper, but can't remember any specifics

breck 6y ago

Here is the paper: https://github.com/treenotation/research/blob/master/papers/paper/treenotation.pdf https://github.com/treenotation/research/blob/master/papers/... It's not that traditional a style as I had no experience in academia until after I published it on arxiv, but I still stand by basically all of it. For the encoding all you need is 3 things: a node delimiter (generally newlines), a cell delimiter (generally tab or space), and an edge delimiter for parent/child relationships (generally reuse the tab or space from above). Think of a spreadsheet as a program, and that's the base encoding. From there you just need to define Grammars to get higher level constructs. This page (https://jtree.treenotation.org/designer/ https://jtree.treenotation.org/designer/) contains ~15 example grammars, including a grammar for grammars (similar to YACC or ANTLR). This is just the tip of the iceberg though, you can do really novel things with these languages that you don't see with all our traditional languages (like having N parse heads that start all over the place and move in all sorts of directions). So if you take these ideas and combine them with this "Statecharts" paper of 1987, what you would do is create a "Statecharts" Tree Language defining all the elements they have in that paper, and then people could write "programs" in this Tree Language, and then you could use the Compiler Compiler I linked to above to generate a compiler that reads those programs and either 1) compiles them to SVGs like they have in their paper or 2) generates 3-D visualizations where the program shape in the focus is unchanged.

uryga 6y ago
sorry, can't really find anything about graphs in there. how would use TN to represent a graph like this? A --> B --> C ^ | | | +-----------+
- breck 6y ago
  A few options, depends on design of Tree Language. Here are a few programs using grammars following traditional top to bottom, left to right flows. A B C A A B C A A B C. A B C AB BC AB Verbose ones: ANode BNode CNode Edge ANode CAEdge ANode ABEdge BNode BCEdge CNode
  - uryga 6y ago
    ah sorry, i thought your OP was talking about a more graph-theory-ish thing, some fun bijection between trees and graphs or something, serialization isn't really what i had in mind re: TN stuff. don't take this the wrong way, but being able to serialize a graph into bunch of IDs+edges isn't very... remarkable. as in, you could also use JSON/YAML/XML/s-exprs or whatever format, they'd be kind of equivalent here (modulo punctuation). i mean, lightweight DSLs and homoiconicity are cool, but not really groundbreaking stuff --- PS (additional bit of unsolicited advice). afaik you're still looking for TN's "killer app"; i'd consider making something geared towards the org-mode/markdown/plain-text-everything crowd, because TN's advantage is conciseness + ease of input/editing + aesthetics. maybe it could find its niche as a markdown++/org-mode-ish thing where you can freely mix text with structured bits (DSL stuff would be handy here)
    - breck 6y ago
      I hear what you are saying, but there is a big leap between TN and "JSON/YAML/XML/s-exprs". One is isomorphic to 2 and 3 dimensional structures, and the rest are not, connecting the software world to the physical world. This will turn out to be very important and groundbreaking.
      - nsajko 6y ago
        > One is isomorphic to 2 and 3 dimensional structures, and the rest are not So you're saying your notation can encode graphs that can't be represented as, e.g., JSON? The existence of such a graph would be the real (math-breaking) discovery here, no? I.e., you really should be able to give an example before offering such statements... > connecting the software world to the physical world I'm really not following you here.