Richard Suchenwirth - Continuing Graph theory in Tcl, here comes a different application for graphs, that can be turned into a game (stimulated by a remark on Donal Fellows) and thus have a little practical application.
Let a word chain be a list of e.g. English words of equal length, where each two neighboring words differ in only one letter. Examples:
son - sun - gun cat - hat - hot - hog - dog
These word chains are simple graphs, even trees as they contain no cycle. Some may be completed to a cycle, but that indicates it was not the shortest path:
hat - hit - hot #could have been shortened to: hat - hot
In the proposed game, the player has to find a (or a shortest) word-chain for two random words over a given vocabulary. This amounts to finding a path in a graph whose edges need not be literally enumerated, but can be retrieved with a function (as Donal mentioned) like this:}
proc neighbors {word wordlist} {
set res {}
foreach w $wordlist {
if {[wordDistance $w $word]==1} {lappend res $w}
}
set res
}
proc wordDistance {word1 word2} {
set distance 0
foreach c1 [split $word1 ""] c2 [split $word2 ""] {
if {$c1!=$c2} {incr distance}
}
set distance
}
% neighbors cat {car cat man cot con hat fat fan}
car cot hat fatMore to come...