Custom cost types in NetworkSimplex

[Peter Kovacs]

Duraid Madina proposed an enhancement for NetworkSimplex:

	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