I wrote a tool for work that would order VHDL files for compilation. VHDL is one of those languages in which, (annoyingly), everything that file a.vhd depends on must be compiled before a.vhd. After scanning all the source files I extract a dependency list which I stored as a dictionary mapping source file names to the source files they depended on.
I then needed to sort the files so that no file was compiled before any file it depended on.
Now I did google for such a pre-written routine using phrases that included dependency, dependancy :-), depends etc; sort and maybe Python. I got nothing! Eventually I wrote my own which worked very well and I was proud of it.
A couple of months later, whilst reading a newsgroup reply on something or other, someone mentioned a topological sort and so I went and looked that up. If only I knew the term 'topological' I could have found a ready-made solution such as this (which has a good explanation too).
So, "What's in a name"?
Quite a lot actually.
:-) Paddy.
P.S. There is also the tsort Unix utility.
Mainly Tech projects on Python and Electronic Design Automation.
Saturday, October 13, 2007
Subscribe to:
Post Comments (Atom)
About Me
Followers
Subscribe Now: google
You are actually not the first to come up with this problem (specifically with topological sort).
ReplyDeleteA friend I know was writing a build program, and he reinvented the concept, because he was not aware of it.
I think many names in computer science are not 'the right names'. Take memoization for example.
If you just came out of a university lesson about lisp(for me it was scheme), you'd call the appropriate decorator "memoize".
If however you were just a regular self-educated programmer, you'd probably use the much more clearer "cache".