COIN-OR::LEMON - Graph Library

Opened 13 years ago

Last modified 11 years ago

#415 new enhancement

Custom cost types in NetworkSimplex

Reported by: Peter Kovacs Owned by: Alpar Juttner
Priority: major Milestone:
Component: core Version: hg main
Keywords: Cc:
Revision id:


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
  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

Attachments (1)

network_simplex.patch (6.0 KB) - added by Peter Kovacs 13 years ago.

Download all attachments as: .zip

Change History (2)

Changed 13 years ago by Peter Kovacs

Attachment: network_simplex.patch added

comment:1 Changed 11 years ago by Peter Kovacs

Milestone: LEMON 1.3 release
Note: See TracTickets for help on using tickets.