Special care should be taken when using the template 
functions with a number
type |NT| that can incur rounding error, e.g., the type |double|.
The section ``Algorithms on Weighted Graphs and Arithmetic Demand'' 
of the LEDA book contains
a general discussion of this issue.
The template functions
are only guaranteed to perform correctly if all arithmetic performed is 
without rounding error. This is the case if all numerical values in the input
are integers (albeit stored as a number of type |NT|) and 
if none of the intermediate
results exceeds the maximal integer representable by the 
number type ($2^{53} - 1$ in the case of |doubles|).
All intermediate results are sums and differences
of input values, in particular, the algorithms do not use divisions and
multiplications. 

The algorithms have the following arithmetic demands. Let
$C$ be the maximal absolute value of any edge cost. If all weights are integral
then all intermediate values are bounded by $3C$ in the case of 
maximum weight matchings and by $4 n C$ in the case of the 
other matching algorithms. Let $f = 3$ in the former case and let $f = 4n$
in the latter case. 

The pre-instantiations for number type |double|
compute the optimal matching for a modified weight function |c1|, where
for every edge $e$
\[ |c1|[e]= |sign|(c[e]) \lfloor \Labs{ |c[e]| } \cdot S \rfloor / S \]
and $S$ is the largest power of two such that $S < 2^{53}/(f\cdot C)$.

The weight of the optimal matching for the modified weight function and the 
weight of the optimal matching for the original weight function differ by at
most $n \cdot f \cdot C \cdot 2^{-52}$.


template <class NT>
list<edge> MWMCB_MATCHING_T(graph& G, 
                                         const list<node>& A, 
                                         const list<node>& B,  
                                  const edge_array<NT>& c, 
                                        node_array<NT>& pot);
/*{\Mfunc Returns a maximum weight matching among the matching of 
maximum cardinality. 
The potential function |pot| is tight with respect to a modified 
cost function which increases the cost of every edge by $L = 1 + 2kC$ 
where $C$ is the maximum absolute value of any weight and 
$k = \min(\Labs{A},\Labs{B})$. 
It is assumed that the partition |(A, B)| witnesses that |G| 
is bipartite and that all edges of $G$ are directed from $A$ to $B$. If $A$ and
$B$ have different sizes, it is advisable that $A$ is the smaller set; in
general, this leads to smaller running time. The argument |pot| is optional.
\bigskip
}*/

template <class NT>
list<edge> MWMCB_MATCHING_T(graph& G, 
                          const list<node>& A, 
                          const list<node>& B,
                          const edge_array<NT>& c);


bool MWBM_SCALE_WEIGHTS(const graph& G, 
                        edge_array<double>& c);
/*{\Mfunc replaces $c[e]$ by |c1[e]| for every edge $e$, where |c1[e]|
was defined above and $f = 3$. This scaling function is appropriate for the
maximum weight matching algorithm. The function returns |false| 
if the scaling changed some weight, and returns |true| otherwise.

bool MWA_SCALE_WEIGHTS(const graph& G, 
                       edge_array<double>& c);
/*{\Mfunc replaces $c[e]$ by |c1[e]| for every edge $e$, where |c1[e]|
was defined above and $f = 4n$. This scaling function should be used for the algorithm 
that compute minimum of maximum weight assignments or maximum weighted
matchings of maximum cardinality.
The function returns |false| if the scaling changed some weight, 
and returns |true| otherwise. 
}*/

*****************************************************************************************
MORE INFO ABOUT THIS

bool 	MWBM_SCALE_WEIGHTS(graph G, edge_array<double>& c)
  	  	replaces c[e] by c1[e] for every edge e, where c1[e] was defined above and f = 3. This scaling function is appropriate for the maximum weight matching algorithm. The function returns false if the scaling changed some weight, and returns true otherwise.

bool 	MWA_SCALE_WEIGHTS(graph G, edge_array<double>& c)
  	  	replaces c[e] by c1[e] for every edge e, where c1[e] was defined above and f = 4n. This scaling function should be used for the algorithm that compute minimum of maximum weight assignments or maximum weighted matchings of maximum cardinality. The function returns false if the scaling changed some weight, and returns true otherwise.
		
		
ie
maximum weight matching => MWBM_SCALE_WEIGHTS
maximum weighted matchings of maximum cardinality => MWA_SCALE_WEIGHTS
