4 ms·
>> We need a solid, simple program that can simply edit trees. I might be misunderstanding this but a "tree" is a graph, so formally a tuple G = {V,E} where V
by YeGoblynQueenne 10y ago
>> We need a solid, simple program that can simply edit trees.
I might be misunderstanding this but a "tree" is a graph, so formally a tuple G = {V,E} where V a set of vertices {a,b,c,....} and E a set of tuples: {{a,b}, {b,c},...} so that each a,b,c,... are vertices in V.
So for instance, the graph:
a
|
/ \
b c
| |
d e
Would be written as {{V,E}: V = {a,b,c,d,e}, E = {{a,b},{a,c},{b,d},{c,e}}} possibly accompanied by a statement as to whether edges are directed or not.
That's a simple, intuitive, light-weight notation that is very easy to manipulate in a text editor, so that's probably why nobody has bothered to write a special-purpose program for it.
And if you want a graphical representation there's always tools like graphviz, so our graph can be written in dot-language as:
digraph{
a->b
a->c
b->d
c->e
}
Also, I don't understand why a tool to manipulate graphs, rather than just represent them, would be any different than a proof assistant or a theorem prover.
- vog 10y ago> {{V,E}: V = {a,b,c,d,e}, E = {{a,b},{a,c},{b,d},{c,e}}} possibly accompanied by a statement as to whether edges are directed or not. From a math notation point of view, this statement is not needed. If your edges are directed, denote your edges not as sets (which are always unordered in math), but as ordered pairs instead: {{V,E}: V = {a,b,c,d,e}, E = {(a,b),(a,c),(b,d),(c,e)}}
- YeGoblynQueenne 10y agoThanks. Or you can always use what I think is slightly informal notation, where a directed edge is notated as a -> b (I've seen that in textbooks, but I'm not sure where it's coming from).
- vog 10y agoHaven't seen this notation in text books so far, but I guess one of the following 3 things happened: (1) The notation a->b was defined as a simple shorthand, i.e. a->b := (a,b). (2) The notation a->b was defined to be the graph consisting of just a, b and the edge, i.e. a->b := ({a,b}, {(a,b)}) ... this may be followed by some algebraic rules about how to combine small graphs to build larger graphs. (3) The notation a->b may be a somewhat misused notation for functions, meaning the only possible function from set {a} to set {b}, i.e. the function that maps a to b. If you define a function to be a relation (i.e. a set of pairs) where the first elements are unique, then this is acually equal to {(a,b)}, i.e. the set containing exactly this one pair. Interpretation (3) might look somewhat contrieved, but it actually isn't that much of a stretch, given the connections between graph theory and function structures through category theory.
- YeGoblynQueenne 10y agoI believe it's (1) and I think it might originate in Judea Pearl's textbook on causality [1], particularly the section on the IC algorithm. I've also encountered it in a bunch of papers on graph reconstruction, by Wermuth, Lauritzen, Spirtes and Glymour (not all in one go, I don't think). For instance, see [2]. I guess it's convenient notation for a typical step in those algorithms, where two edges are oriented towards a common vertex- shown as A -> B <- C or similar. That's a little more concise than {(A,B),(C,B)} but also more intuitive when the intention is to show how to (re)construct a graph from dependence relations, as those algorithms usually do. ___________________ [1] Causality; models, reasoning and inference: http://bayes.cs.ucla.edu/BOOK-2K/ http://bayes.cs.ucla.edu/BOOK-2K/ [2] A Fast Algorithm for Discovering Sparse Causal Graphs; Peter Spirtes & Clark Glymour: http://repository.cmu.edu/cgi/viewcontent.cgi?article=1316&context=philosophy http://repository.cmu.edu/cgi/viewcontent.cgi?article=1316&c...
- tunesmith 10y agoWould that support an edge between b and e? That's what determines whether something like an outliner would be a good UI for it. If you need that support, then the UI becomes more difficult - you either have to "draw" the graph visually, or have a continually adapting approximation.
- YeGoblynQueenne 10y agoWhy wouldn't it? You just add an edge: {b, e}. A UI, now that's a different issue but I don't see why you need a special UI there. It just sounds like a bit of a gimmick to me, to be honest. Or probably it's just that the OP wants to use graphs (trees) for something that doesn't really need graphs? As in, yeah, you can represent computation using graphs -you can represent all sorts of formal stuff with graphs- but that's an implementation detail. Like, why have a GUI to an AST and not a GUI to your computer's 1s and 0s, in RAM? Or a GUI to your processor's registers? It's just a very unnatural way to program, really.
- chriswarbo 10y agoYour representation is certainly valid, but I think those properties (light-weight, intuitive, etc.) apply to your example rather than your representation. For example, imagine representing the HTML of this Hacker News page in your format; it would be completely unwieldy, and Hacker News is notoriously simple as far as HTML goes. It's clear that this representation is massively space inefficient, since it repeats the vertex labels over and over. It's also massively time inefficient for common operations, like finding the incoming/outgoing edges of a node; these can be seen "at a glance" in some representations, like boxes + arrows, whilst your representation requires traversing the entire set of edges looking for matches. In fact, I can't figure out a sensible way to even write down the vertices in such an example! Even if we invented some arbitrary labelling scheme, e.g. labelling nodes based on their path from the root, or based on their position in a post-order traversal, such labelling schemes would be enough to define the tree on their own! Unfortunately I think this is another case of trying to shoehorn sets into places where they don't belong for no particular reason, as if trees are somehow "less mathematical" than sets. It didn't work for Bertrand Russell, and it doesn't work here ;) > if you want a graphical representation there's always tools like graphviz Graphviz is notoriously messy when it comes to graphs of any nontrivial size, and the existing tooling makes interaction less than ideal (e.g. using home-grown scripts on top of image canvases and hotspots, rather than established interaction methods like a widget toolkit). > Also, I don't understand why a tool to manipulate graphs, rather than just represent them, would be any different than a proof assistant or a theorem prover. I don't see the connection myself. Proof assistants are incredibly picky about what they allow (that's kind of the point ;) ); on the other hand, a tree editor would be used for "fast and loose" cutting, pasting, duplicating, rotating, swapping, etc. of arbitrary sub-trees in arbitrary structures. How would tooling like, say, Coq, help with that?
- YeGoblynQueenne 10y ago>> For example, imagine representing the HTML of this Hacker News page in your format; it would be completely unwieldy, and Hacker News is notoriously simple as far as HTML goes. Well yes, but that's because HTML is a mess, not because graph notation is unwieldy. In any case I don't think it's a good idea to try to program in graph notation, or anything like it. Actually, I think it's a terrible idea. Unless you want to create some kind of help tool for graph theory, I guess. >> Proof assistants are incredibly picky about what they allow (that's kind of the point ;) As are all programming languages. Manipulating graphs, er, graphically, will not give you some sort of magical get-out-of-jail-free card against syntax errors or undefinable behaviour etc. Like, I'm not even sure what the point is here, with the OP. Is it along the lines of "hey, look at graphs, graphs are cool, let's make coding cool with cool graphs"? Or is there some sort of benefit, like expressive power or syntactic clarity, that you don't have with high-level languages already? Why do you need a GUI to an AST? To be honest, the OP looks like a bit of a muddle to me.