The tradition, if there is such a thing for programs, is to
memoize the function you wish to improve. That is,
if you want
adjacency_matrix(G) to be fast, then you would remember
G in the hash table for adjacency_matrix.
The less traditional would be to put it in a slot in
the header of G. e.g. (($graph simp <adjacency matrix>) (($edge_list
simp) ....)(($node_list simp) ....))
However, that would probably not be worth a lot because you
want to memoize small things that are expensive to compute,
not large things that are easy to compute. Just checking
that G had not changed would cost as much as computing
the adjacency matrix, I think.
RJF
Martin RUBEY wrote:
> I think (I'm not sure) I was thinking about similar things while planning
> the graph package (well, it's not done yet, due to lack of time...)
>
> I wanted to keep as much useful information as possible, ie. when a
> single thing of the graph is changed, not everything has to be recomputed
> and the like. The difficulty I encountered was where to store this
> information:
> eg (simple) : given an edge and a vertex set, the adjacency matrix is
> computed.
> Now, we could throw away the original information -- ie edge and vertex
> set -- or we could keep it. But if we want to keep it, where?
>
> I postponed the question by having all functions return two values: all
> the information of the graph and the wanted specific property.
>
> If my approach is stupid (it possibly is), please tell me so (and say why)
>
> Martin
>