| 221 | /// by default. For more information, see \ref PivotRule. |
| 222 | template <typename GR, typename V = int, typename C = V, typename NodesType = unsigned short int, typename ArcsType = int64_t> |
| 223 | class NetworkSimplexSimple |
| 224 | { |
| 225 | public: |
| 226 | |
| 227 | /// \brief Constructor. |
| 228 | /// |
| 229 | /// The constructor of the class. |
| 230 | /// |
| 231 | /// \param graph The digraph the algorithm runs on. |
| 232 | /// \param arc_mixing Indicate if the arcs have to be stored in a |
| 233 | /// mixed order in the internal data structure. |
| 234 | /// In special cases, it could lead to better overall performance, |
| 235 | /// but it is usually slower. Therefore it is disabled by default. |
| 236 | NetworkSimplexSimple(const GR& graph, bool arc_mixing, int nbnodes, ArcsType nb_arcs, uint64_t maxiters) : |
| 237 | _graph(graph), //_arc_id(graph), |
| 238 | _arc_mixing(arc_mixing), _init_nb_nodes(nbnodes), _init_nb_arcs(nb_arcs), |
| 239 | MAX(std::numeric_limits<Value>::max()), |
| 240 | INF(std::numeric_limits<Value>::has_infinity ? |
| 241 | std::numeric_limits<Value>::infinity() : MAX) |
| 242 | { |
| 243 | // Reset data structures |
| 244 | reset(); |
| 245 | max_iter = maxiters; |
| 246 | } |
| 247 | |
| 248 | /// The type of the flow amounts, capacity bounds and supply values |
| 249 | typedef V Value; |
| 250 | /// The type of the arc costs |
| 251 | typedef C Cost; |
| 252 | |
| 253 | public: |
| 254 | |
| 255 | /// \brief Problem type constants for the \c run() function. |
| 256 | /// |
| 257 | /// Enum type containing the problem type constants that can be |
| 258 | /// returned by the \ref run() function of the algorithm. |
| 259 | enum ProblemType { |
| 260 | /// The problem has no feasible solution (flow). |
| 261 | INFEASIBLE, |
| 262 | /// The problem has optimal solution (i.e. it is feasible and |
| 263 | /// bounded), and the algorithm has found optimal flow and node |
| 264 | /// potentials (primal and dual solutions). |
| 265 | OPTIMAL, |
| 266 | /// The objective function of the problem is unbounded, i.e. |
| 267 | /// there is a directed cycle having negative total cost and |
| 268 | /// infinite upper bound. |
| 269 | UNBOUNDED, |
| 270 | /// The maximum number of iteration has been reached |
| 271 | MAX_ITER_REACHED |
| 272 | }; |
| 273 | |
| 274 | /// \brief Constants for selecting the type of the supply constraints. |
| 275 | /// |
| 276 | /// Enum type containing constants for selecting the supply type, |
| 277 | /// i.e. the direction of the inequalities in the supply/demand |
| 278 | /// constraints of the \ref min_cost_flow "minimum cost flow problem". |
| 279 | /// |
| 280 | /// The default supply type is \c GEQ, the \c LEQ type can be |