Fwd: Re: Automatically Generated Keyboard Accelerators (replacing kaccelgen.h)

[Ingo Klöcker]

On Tuesday 10 June 2008, Riccardo Iaconelli wrote:
> On Tuesday 10 June 2008 17:00:02 Mark Summerfield wrote:
> > I certainly know that my algorithm outperforms the existing one in
> > all the tests I've done (and uses an algorithm that is
> > intrinsically better), so I'm inclined to hope you'll use the one
> > I've done, at least for now?
>
> Apart for math, which I'm not going to debate (26 seems a non-so-high
> number given the current amount of things we can shortcut), I've just
> contacted the guy with the implementation linked above in the thread,
> and he says he'd be extremely happy to relicense it to fit our needs,
> and that he's also happy to answer questions about the integration of
> the code (or the code itself).
>
> So, let me know what to do next. =)

Let's start with using the algorithm without using different weights (or 
cost in the language of the Assignment Problem [AP]) depending on the 
position of the accelerators in the menu entries.

We have 26 accelerators (the agents) and we want to assign them to n 
menu entries (the tasks). In the worst case (if all menu entries are 
entirely non-ASCII) we do not want any of the accelerators to be 
assigned to any of the menu entries. Therefore we have to add 26 dummy 
menu entries (matching all accelerators) as fallback.

So now we have 26 agents and n+26 tasks. Next we define the cost matrix
  Matrix<int> C(n+26, 26);
as follows (for 0 <= i < n+26 and 0 <= j < 26). [Note that we have 
swapped agents and tasks because for the algorithm we must have at 
least as many rows as columns.]:
C(i,j) = 0 if i < n and the i-th menu entry contains the j-th 
accelerator
C(i,j) = 2 if i < n and the i-th menu entry does not contain the j-th 
accelerator
C(i,j) = 1 if i >= n (i.e. for the dummy tasks)


Simplified example:
- We have three accelerators: A, B, C
- We have two menu entries: "Alpha", "Beta"
Then the cost matrix looks as follows:

        A  B  C
Alpha   0  2  2
Beta    0  0  2
dummy1  1  1  1
dummy2  1  1  1
dummy3  1  1  1

After constructing the cost matrix we apply the algorithm to the matrix.

  // Apply Munkres algorithm to matrix.
  Munkres m;
  m.solve( C );

Finally we look for zeros in the first n rows to find out which 
accelerator to use for which menu entry.


Once the above works we can start playing with different costs depending 
on the position of the letter in the menu entry. Note that the cost for 
assigning an accelerator to a dummy menu entry (above this cost was 1) 
must be higher than the cost for assigning a valid accelerator to a 
normal menu entry (above this cost was always 0). Moreover, the cost 
for an invalid assignment (above this cost was 2) must be even higher.


I hope the above was more or less understandable.


Regards,
Ingo
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 194 bytes
Desc: This is a digitally signed message part.
URL: <http://mail.kde.org/pipermail/kde-core-devel/attachments/20080611/c375d3a0/attachment.sig>