1 /* -*- C++ -*- |
1 /* -*- C++ -*- |
2 * src/hugo/min_cost_flow.h - Part of HUGOlib, a generic C++ optimization library |
2 * src/lemon/min_cost_flow.h - Part of LEMON, a generic C++ optimization library |
3 * |
3 * |
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
5 * (Egervary Combinatorial Optimization Research Group, EGRES). |
5 * (Egervary Combinatorial Optimization Research Group, EGRES). |
6 * |
6 * |
7 * Permission to use, modify and distribute this software is granted |
7 * Permission to use, modify and distribute this software is granted |
12 * express or implied, and with no claim as to its suitability for any |
12 * express or implied, and with no claim as to its suitability for any |
13 * purpose. |
13 * purpose. |
14 * |
14 * |
15 */ |
15 */ |
16 |
16 |
17 #ifndef HUGO_MIN_COST_FLOW_H |
17 #ifndef LEMON_MIN_COST_FLOW_H |
18 #define HUGO_MIN_COST_FLOW_H |
18 #define LEMON_MIN_COST_FLOW_H |
19 |
19 |
20 ///\ingroup flowalgs |
20 ///\ingroup flowalgs |
21 ///\file |
21 ///\file |
22 ///\brief An algorithm for finding a flow of value \c k (for small values of \c k) having minimal total cost |
22 ///\brief An algorithm for finding a flow of value \c k (for small values of \c k) having minimal total cost |
23 |
23 |
24 |
24 |
25 #include <hugo/dijkstra.h> |
25 #include <lemon/dijkstra.h> |
26 #include <hugo/graph_wrapper.h> |
26 #include <lemon/graph_wrapper.h> |
27 #include <hugo/maps.h> |
27 #include <lemon/maps.h> |
28 #include <vector> |
28 #include <vector> |
29 |
29 |
30 namespace hugo { |
30 namespace lemon { |
31 |
31 |
32 /// \addtogroup flowalgs |
32 /// \addtogroup flowalgs |
33 /// @{ |
33 /// @{ |
34 |
34 |
35 ///\brief Implementation of an algorithm for finding a flow of value \c k |
35 ///\brief Implementation of an algorithm for finding a flow of value \c k |
36 ///(for small values of \c k) having minimal total cost between 2 nodes |
36 ///(for small values of \c k) having minimal total cost between 2 nodes |
37 /// |
37 /// |
38 /// |
38 /// |
39 /// The class \ref hugo::MinCostFlow "MinCostFlow" implements |
39 /// The class \ref lemon::MinCostFlow "MinCostFlow" implements |
40 /// an algorithm for finding a flow of value \c k |
40 /// an algorithm for finding a flow of value \c k |
41 /// having minimal total cost |
41 /// having minimal total cost |
42 /// from a given source node to a given target node in an |
42 /// from a given source node to a given target node in an |
43 /// edge-weighted directed graph. To this end, |
43 /// edge-weighted directed graph. To this end, |
44 /// the edge-capacities and edge-weitghs have to be nonnegative. |
44 /// the edge-capacities and edge-weitghs have to be nonnegative. |