Reimplemented MinMeanCycle to be much more efficient.
The new version implements Howard's algorithm instead of Karp's algorithm and
it is at least 10-20 times faster on all the 40-50 random graphs we have tested.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
21 ///\brief An introduction to LEMON maps
23 /// \include maps_summary.cc
26 #include <lemon/list_graph.h>
28 using namespace lemon;
31 template < typename GRAPH, typename MAP >
32 typename MAP::Value summary( GRAPH& gr, MAP& m )
34 typename MAP::Value summ = typename MAP::Value();
36 for( typename GRAPH::NodeIt n(gr); n != lemon::INVALID; ++n )
46 ListGraph::NodeMap<double> value(gr, 0.0);
50 std::cout << "The summary of assigned values is " << summary(gr,value) << std::endl;