Automatically Generated Keyboard Accelerators (replacing kaccelgen.h)

[Mark Summerfield]

On 2008-06-09, Ingo Klöcker wrote:
> On Monday 09 June 2008, Mark Summerfield wrote:
[snip]
> I don't want to spoil the fun, but this problem is usually known as
> assignment problem [1] and it is solvable in O(n^3) by the Hungarian
> algorithm (aka Munkres assignment algorithm aka Kuhn-Munkres algorithm)
> [2]. Moreover, there exists a C++ implementation of this algorithm [3]
> (which I didn't even have a quick look at). The only "problem" is that
> this implementation is GPLv2+ so it cannot be used in kdelibs.
>
> This is JFYI. Until there is a better implementation than the one
> proposed by Mark we should probably use Mark's implementation.
>
> Last but not least, an advise to all (KDE) developers (Please don't get
> this wrong, Mark!):
> Before you try to invent an algorithm to solve some problem please
> invest some time to check whether there is already an algorithm solving
> this exact problem. More often than not this will save you a lot of
> time.

I had a look at the wikipedia articles and I can (kind of) see how they
might be used to solve the problem. There is no way I would have
realised that it was a way of solving this problem (and nor did two
friends both of whom are much more mathematically sophisticated than I
am).

I'll stick to my plan and submit my updated kaccelgen.h today (with the
new quality() function) and I'll then look into the Hungarian algorithm. 

PS I've now found and copied kaccelgentest.cpp (which actually only has
two simple tests), so I'll try to produce a new version of that too.

-- 
Mark Summerfield, Qtrac Ltd., www.qtrac.eu