6 * $Date: 2012-07-05 16:45:20 +0200 (Do, 05. Jul 2012) $
7 ***************************************************************/
10 * \brief front-end for min-most flow algorithm (Reinelt)
12 * \author Carsten Gutwenger
15 * This file is part of the Open Graph Drawing Framework (OGDF).
19 * See README.txt in the root directory of the OGDF installation for details.
22 * This program is free software; you can redistribute it and/or
23 * modify it under the terms of the GNU General Public License
24 * Version 2 or 3 as published by the Free Software Foundation;
25 * see the file LICENSE.txt included in the packaging of this file
29 * This program is distributed in the hope that it will be useful,
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32 * GNU General Public License for more details.
35 * You should have received a copy of the GNU General Public
36 * License along with this program; if not, write to the Free
37 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
38 * Boston, MA 02110-1301, USA.
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
44 #include <ogdf/graphalg/MinCostFlowReinelt.h>
45 #include <ogdf/basic/NodeArray.h>
46 #include <ogdf/basic/EdgeArray.h>
53 bool MinCostFlowReinelt::call(
55 const EdgeArray
<int> &lowerBound
,
56 const EdgeArray
<int> &upperBound
,
57 const EdgeArray
<int> &cost
,
58 const NodeArray
<int> &supply
,
61 NodeArray
<int> dual(G
);
62 return call(G
, lowerBound
, upperBound
, cost
, supply
, flow
, dual
);
66 // computes min-cost-flow
67 // returns true if a minimum cost flow could be found
68 bool MinCostFlowReinelt::call(
70 const EdgeArray
<int> &lowerBound
,
71 const EdgeArray
<int> &upperBound
,
72 const EdgeArray
<int> &cost
,
73 const NodeArray
<int> &supply
,
77 OGDF_ASSERT(checkProblem(G
,lowerBound
,upperBound
,supply
) == true);
79 const int n
= G
.numberOfNodes();
80 const int m
= G
.numberOfEdges();
82 // assign indices 0, ..., n-1 to nodes in G
83 // (this is not guaranteed for v->index() )
84 NodeArray
<int> vIndex(G
);
86 Array
<int> mcfSupply(n
);
91 mcfSupply
[i
] = supply
[v
];
96 // allocation of arrays for arcs
97 Array
<int> mcfTail(m
);
98 Array
<int> mcfHead(m
);
101 Array
<int> mcfCost(m
);
102 Array
<int> mcfFlow(m
);
103 Array
<int> mcfDual(n
+1); // dual[n] = dual variable of root struct
105 // set input data in edge arrays
111 // We handle self-loops in the network already in the front-end
112 // (they are just set to the lower bound below when copying result)
113 if(e
->isSelfLoop()) {
118 mcfTail
[i
] = vIndex
[e
->source()];
119 mcfHead
[i
] = vIndex
[e
->target()];
120 mcfLb
[i
] = lowerBound
[e
];
121 mcfUb
[i
] = upperBound
[e
];
122 mcfCost
[i
] = cost
[e
];
128 int retCode
; // return (error or success) code
129 int objVal
; // value of flow
131 // call actual min-cost-flow function
132 // mcf does not support single nodes
135 //mcf does not support single edges
141 flow
[e
] = lowerBound
[e
];
145 else retCode
= mcf(n
, m
-nSelfLoops
, mcfSupply
, mcfTail
, mcfHead
, mcfLb
, mcfUb
,
146 mcfCost
, mcfFlow
, mcfDual
, &objVal
);
151 // copy resulting flow for return
155 if(e
->isSelfLoop()) {
156 flow
[e
] = lowerBound
[e
];
160 flow
[e
] = mcfFlow
[i
];
162 OGDF_ASSERT( (flow
[e
]>=lowerBound
[e
]) && (flow
[e
]<= upperBound
[e
]) )
167 // copy resulting dual values for return
170 dual
[v
] = mcfDual
[i
];
174 // successful if retCode == 0
175 return (retCode
== 0);
179 } // end namespace ogdf