Dear Stavros,
Thanks for your post. If you got my package you already know what I've
decided to do. Anyway, here come some comments (and I'm very happy we have
nearly one opinion!)
On Mon, 24 Feb 2003, Stavros Macrakis wrote:
> You can hide all you want in the cdar. Most of Maxima doesn't touch
> cdar's: it neither examines nor modifies them. This means (among other
> things) that two things are considered (syntactically) equal iff their
> visible parts are equal. This has bad consequences. So it is better to
> have the visible part fully represent the value.
Yes, well, when the visible part changes, all the tags are deleted... So I
decided to keep all the information in the cdr, one part stored in the
property list of a gensym, the rest of the cdr will contain those parts
which I want to be substituteable or evalable, i.e. currently the edge
weights. MAYBE I could also store the labels in it, but this might become
complicated, because I assume on input that vertex names are different.
Rationale: Imagine
hypergraph([a,a,b],[[[a,a]],[[a,b]]])
would be the input. There is no way for me to know whether the graph has
one loop, one edge and an isolated vertex or
one isolated vertex with a loop and an edge or
two edges, ...
> 1 The caar represents the object constructor or type.
> 2 The cdr is a list of GRs, fully representing the object's semantics.
> 3 Expressions are simplified to a quasi-canonical form, such
> that syntactic equality (ALIKE1) always implies semantic equality,
> and semantic equality often implies syntactic equality.
> 4 The cdar contains additional information which does not change
> the meaning of the expression.
> 5 Objects are immutable: operations on objects create new objects,
> they
> don't modify existing ones.
My package does not violate any of those. Of course, graph isomorphism is
nearly impossible to handle...
> (displa-def $graph dimension-graph)
>
> (defun dimension-graph (form result)
> (let ((vertices (cadr (memq 'vertices (cdar form))))
> (edges (cadr (memq 'edges (cdar form)))))
> (dimension-function
> `(($graph simp)
> ((msetq simp) $vertices ,(length vertices))
> ((msetq simp) $edges ,(length edges)))
> result)))
Thanks, this is good to know
> But if we create two identical graphs independently, they will still
> compare as not equal:
>
> set(complete_graph(5),complete_graph(5))
> => { GRAPH(VERTICES : 5, EDGES : 10), GRAPH(VERTICES : 5, EDGES
> : 10) }
As I said before, graph isomorphism is difficult.
> Now this brings up a host of other issues. For example, do you have a
> canonical form for graphs such that you can use ALIKE1 (Maxima's
> standard syntactic comparison function) to compare them? Maxima is very
> fond of such canonical forms. Forgive the anthropomorphizing: what I
> mean is that Maxima works well with representations where syntactical
> equality (ALIKE1) is a good approximation to semantic equality. As a
> general rule, Maxima takes advantage of syntactic properties without
> asking the user (e.g. during general simplification), but the user must
> explicitly ask for semantic properties. (There are exceptions; compare
> <<< assume(equal(a,b))$ a-b => a-b >>> vs <<< assume(a<0)$ abs(a) => -a
> >>>.)
I haven't thought about assumptions yet. I don't think it would be easy to
find good semantics for assumptions, nor to do a good implementation. I
won't pursue this in near future...
> Another issue: what is the meaning of your vertex names? Are they part
> of the graph, or simply a convenient way to enter graphs. For example,
> do you consider the undirected graph a-b (two vertices, one edge) to be
> the "same graph" as b-c (same structure, different labels)? How about
> b-a? How do you label vertices in generated graphs (like
> complete_graph(5))?
Well, the are isomorphic, but not identical. The vertex names are used to
distinguish the vertices on input and output. There is one part of the
package where to different vertices with the same name may be generated,
(g-spanning-trees) but this is not visible to the user. Internally,
vertices are structures which are lisp::eq or not. This works very well.
I don't know if it makes sense to have
x identity (lisp::eq)
x equality1 (the vertices are permuted)
x equality2 (the vertices are in the same order, but have different names)
x isomorphic (the vertices are permuted and have different names)
(equality1 is impossible right now, I think.)
> If you use a GR-type structure, all these becomes trivial. They just
> work -- but they will only really be useful if vertex labels are part of
> the value.
This is the only point where I disagree: I'd say
... but they will only really be useful if edge weights are part of the
value.
^^^^^^^^^^^^
I cannot control what happens if a vertex name gets substituted and is
afterwards identical to another one. The story is different for the edges.
Here the semantics are clear. So I might include the edges... (still this
is not trivial)
>
> For example,
>
> g1: graph([a,b],[[a,b]]) => graph(vertices:2,edges:2)
you mean edges:1
> g2: subst('a,'a,g1) => graph(vertices:1,edges:0)
> (or edges:1 if you allow self-edges)
I allow even edges like (a,a,b,a,c,d) in hypergraphs!
Thanks for everything and I hope you like it! Did you try it out. Maybe
the student of Richard wants to have a look at it too?
All the best,
Martin