[Lemon-user] Fwd: patch to lemon::NetworkSimplex for custom cost types

[Kovács Péter]

Hi All,

I forward an email of Duraid Madina to the list, because you may also be 
interested in it.

A ticket was also created in our issue tracker about this proposal:
https://lemon.cs.elte.hu/trac/lemon/ticket/415

Regards,
Peter


-------- Original message --------
Subject: patche to lemon::NetworkSimplex for custom cost types
Date: Mon, 21 Feb 2011 09:15:24 +0900
From: Duraid Madina ( duraid at riken dot jp )
To: kpeter at inf.elte.hu

Dear Peter,

	I have been using Lemon's network-simplex code for some time.
Recently I wanted to use it with a custom Cost type and int Value type.

	In order to make this simpler, I have patched network_simplex.h
so that the Cost class/type does not need/use operator*.

	At the moment, my patch requires that a custom Cost class must
still implement operator* for (Cost, int) pairs. However, this is only
for the initialization of ART_COST, and for totalCost(). It is also
possible to eliminate these uses of operator*, but I have not needed
to make these changes.

	The patch consists of three things:

    1) the addition of a unitMul() function for multiplying Costs by
"unit values" -1, 0 and 1
    2) changing all occurences of Cost*unit value multipication to
calls to unitMul()
    3) a small change to totalCost() allowing exact total costs to
be computed (requires the custom Cost class to provide Cost*Value
multiplication, but not Cost*Cost multiplication.)

	There is one potential problem with the patch. On x86 machines
and "int" Cost type, there is a speed penalty of about 15%. This can be
eliminated through template specialization of the unitMul function for
"int" Costs, but I have not done this for two reasons:

    1) It would be great if you could do it in your preferred "LEMON
style"
    2) On some machines, such as ia64 (Itanium), the unitMul in the
attached patch actually leads to a speed _gain_ of about 10%. The
reason is that there does not seem to be any compiler which can
detect that the "*" can be replaced by predicated/conditional clears
and negations.

	So rather than constant tempate specialization, perhaps
the choice of unitMul() implementation could be left to the user,
with a simple "*"-based implementation as default?

	Anyway, I hope this patch makes sense and you consider it
for inclusion in your code. I would like to conclude by saying a
big "thank you!" for the excellent LEMON library!!

	Yours sincerely,

	Duraid MADINA
	RIKEN



-------------- next part --------------
A non-text attachment was scrubbed...
Name: network_simplex.patch
Type: text/x-diff
Size: 6004 bytes
Desc: network_simplex.patch
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20110302/d72819d5/attachment.bin>