Article View: comp.lang.clos
Article #9Re: CLOS data structures shelf
From: Daniel LaLiberte
Date: Thu, 29 Oct 1992 19:41
Date: Thu, 29 Oct 1992 19:41
30 lines
2087 bytes
2087 bytes
Oh, what the heck, I'm not proud. Below is the header from my CLOS-based dag.lisp code. It is certainly not the ultimate in clean code, but I find it pretty useful and it is somewhere to start. Please include it in the archive. Dan LaLiberte liberte@cs.uiuc.edu (Join the League for Programming Freedom: lpf@uunet.uu.net) "If we don't succeed, we run the risk of failure. -- Vice President Dan Quayle." --------- DAG (directed acyclic graph) structures are made of dag-nodes and dag-groups. dag-group is a subclass of dag-node, and dag-group instances list all the sub-nodes of the group. dag-nodes list all parents, which strictly speaking is not part of a dag data structure, so this should probably be called something like a dag-with-backlinks structure. One can look at the parent references as forming an upside down dag structure, but CLOS doesnt deal well with unshared slots with the same name. Also, dag-group might be implemented as a subclass of a tree class. The difference, of course, is that dag-nodes may be shared by multiple parents. To support traversals, an external hash table is used (see tally class below). This permits multiple simultaneous traversals, and avoids an extra pass to unvisit. It is also safer. One problem is the wasted space of a hash table each time a traversal occurs. There is alot of redundancy in the traversal functions. How can I simplify them?
Technical Details
Message-ID:
<LIBERTE.92Oct29134136@birch.cs.uiuc.edu>Path:
arc1-ca.pugleaf.net!sparky!uunet!ukma!wupost!cs.uiuc.edu!m.cs.uiuc.edu!m.cs.uiuc.edu!liberteReferences:
<1992Oct29.114419@disuns2.epfl.ch> <WELCH.92Oct29095546@sacral.cis.ohio-state.edu>Show Full Headers
Complete Article Headers
Newsgroups: comp.lang.clos Path: arc1-ca.pugleaf.net!sparky!uunet!ukma!wupost!cs.uiuc.edu!m.cs.uiuc.edu!m.cs.uiuc.edu!liberte From: liberte@cs.uiuc.edu (Daniel LaLiberte) Subject: Re: CLOS data structures shelf In-Reply-To: welch@sacral.cis.ohio-state.edu's message of Thu, 29 Oct 1992 14:55:46 GMT Message-ID: <LIBERTE.92Oct29134136@birch.cs.uiuc.edu> Followup-To: comp.lang.clos Sender: news@m.cs.uiuc.edu (News Database (admin-Mike Schwager)) Organization: University of Illinois, Urbana-Champaign, Dept CS References: <1992Oct29.114419@disuns2.epfl.ch> <WELCH.92Oct29095546@sacral.cis.ohio-state.edu> Date: Thu, 29 Oct 1992 19:41:36 GMT Lines: 33