<commit_before>/**
 * @fileoverview Copyright (c) 2019-2022, <NAME>,
 *               via Ferrata, 1, I-27100, Pavia, Italy
 *
 * @author <EMAIL> (<NAME>)
 *
 */

// ORIGINAL SOURCE CODE FOR THE NETWORK SIMPLEX BASIS DATA STRUCTURE TAKE FROM:
// WEBSITE: https://lemon.cs.elte.hu

/* ORIGINAL LICENSE FILE:
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2013
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#pragma once

#include "DOT_Commons.h"

namespace DOT {

// Main network simplex implementation with double for cost, capacity, and
// supplies
class NetSimplexCapacity {
 public:
  /// The type of the flow amounts, capacity bounds and supply values
  typedef double Value;
  /// The type of the arc costs
  typedef double Cost;

 private:
  typedef std::vector<int> IntVector;
  typedef std::vector<Value> ValueVector;
  typedef std::vector<Cost> CostVector;
  typedef std::vector<signed char> CharVector;

  // State constants for arcs
  const int STATE_UPPER = -1;
  const int STATE_TREE = 0;
  const int STATE_LOWER = 1;

  // Direction constants for tree arcs
  const int DIR_DOWN = -1;
  const int DIR_UP = 1;

  // Data related to the underlying digraph
  int _node_num;
  int _arc_num;

  int _fixed_arc;
  int _dummy_arc;  // Arc id where begin the basic arcs
  int _next_arc;

  int _all_arc_num;
  int _search_arc_num;

  // Parameters of the problem
  Value _sum_supply;

  // Data structures for storing the digraph
  IntVector _source;
  IntVector _target;

  // Node and arc data
  ValueVector _upper;
  ValueVector _cap;

  ValueVector _supply;
  ValueVector _flow;
  CostVector _cost;
  CostVector _pi;

  // Data for storing the spanning tree structure
  IntVector _parent;
  IntVector _pred;
  IntVector _thread;
  IntVector _rev_thread;
  IntVector _succ_num;
  IntVector _last_succ;
  CharVector _pred_dir;
  CharVector _state;
  IntVector _dirty_revs;

  int _root;

  // Temporary data used in the current pivot iteration
  int in_arc, join, u_in, v_in, u_out, v_out;
  Value delta;

  const Value MAX;
  const Value INF;

  double _runtime;

  double _timelimit;
  double _opt_tolerance;

  size_t _iterations;

 public:
  // Implementation of the Block Search pivot rule
  class BlockSearchPivotRule {
   private:
    // References to the NetworkSimplex class
    const IntVector& _source;
    const IntVector& _target;
    const CostVector& _cost;
    const CharVector& _state;
    const CostVector& _pi;
    int& _in_arc;
    int _arc_num;
    int _dummy_arc;

    // Pivot rule data
    int _block_size;
    int _next_arc;

    // Negative eps
    const double negeps;

   public:
    // Constructor
    BlockSearchPivotRule(NetSimplexCapacity& ns)
        : _source(ns._source),
          _target(ns._target),
          _cost(ns._cost),
          _state(ns._state),
          _pi(ns._pi),
          _in_arc(ns.in_arc),
          _arc_num(ns._arc_num),
          _dummy_arc(ns._dummy_arc),
          _next_arc(ns._next_arc),
          negeps(std::nextafter(-ns._opt_tolerance, -0.0)) {
      // The main parameters of the pivot rule
      const double BLOCK_SIZE_FACTOR = 1.0;
      const int MIN_BLOCK_SIZE =
          10;  // THIS VALUE IS IMPORTANT AND IT SHOULD BE A PARAMETER (!)

      _block_size =
          std::max(int(BLOCK_SIZE_FACTOR * std::sqrt(double(_dummy_arc))),
                   MIN_BLOCK_SIZE);
    }

    // Find next entering arc
    bool findEnteringArc() {
      Cost c, min = negeps;
      int cnt = _block_size;
      int e;
      _in_arc = -1;
      for (e = _next_arc; e != _arc_num; ++e) {
        c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
        if (c < min) {
          min = c;
          _in_arc = e;
        }
        if (--cnt == 0) {
          if (min < negeps) goto search_end;
          cnt = _block_size;
        }
      }
      for (e = _dummy_arc; e != _next_arc; ++e) {
        c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
        if (c < min) {
          min = c;
          _in_arc = e;
        }
        if (--cnt == 0) {
          if (min < negeps) goto search_end;
          cnt = _block_size;
        }
      }
      if (min >= negeps) return false;

    search_end:
      _next_arc = _in_arc;
      return true;
    }

  };  // class BlockSearchPivotRule

 public:
  NetSimplexCapacity(const char INIT, int node_num, int arc_num)
      : _node_num(node_num),
        _arc_num(0),<commit_msg>Change block size<commit_after>/**
 * @fileoverview Copyright (c) 2019-2022, <NAME>,
 *               via Ferrata, 1, I-27100, Pavia, Italy
 *
 * @author <EMAIL> (<NAME>)
 *
 */

// ORIGINAL SOURCE CODE FOR THE NETWORK SIMPLEX BASIS DATA STRUCTURE TAKE FROM:
// WEBSITE: https://lemon.cs.elte.hu

/* ORIGINAL LICENSE FILE:
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2013
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#pragma once

#include "DOT_Commons.h"

namespace DOT {

// Main network simplex implementation with double for cost, capacity, and
// supplies
class NetSimplexCapacity {
 public:
  /// The type of the flow amounts, capacity bounds and supply values
  typedef double Value;
  /// The type of the arc costs
  typedef double Cost;

 private:
  typedef std::vector<int> IntVector;
  typedef std::vector<Value> ValueVector;
  typedef std::vector<Cost> CostVector;
  typedef std::vector<signed char> CharVector;

  // State constants for arcs
  const int STATE_UPPER = -1;
  const int STATE_TREE = 0;
  const int STATE_LOWER = 1;

  // Direction constants for tree arcs
  const int DIR_DOWN = -1;
  const int DIR_UP = 1;

  // Data related to the underlying digraph
  int _node_num;
  int _arc_num;

  int _fixed_arc;
  int _dummy_arc;  // Arc id where begin the basic arcs
  int _next_arc;

  int _all_arc_num;
  int _search_arc_num;

  // Parameters of the problem
  Value _sum_supply;

  // Data structures for storing the digraph
  IntVector _source;
  IntVector _target;

  // Node and arc data
  ValueVector _upper;
  ValueVector _cap;

  ValueVector _supply;
  ValueVector _flow;
  CostVector _cost;
  CostVector _pi;

  // Data for storing the spanning tree structure
  IntVector _parent;
  IntVector _pred;
  IntVector _thread;
  IntVector _rev_thread;
  IntVector _succ_num;
  IntVector _last_succ;
  CharVector _pred_dir;
  CharVector _state;
  IntVector _dirty_revs;

  int _root;

  // Temporary data used in the current pivot iteration
  int in_arc, join, u_in, v_in, u_out, v_out;
  Value delta;

  const Value MAX;
  const Value INF;

  double _runtime;

  double _timelimit;
  double _opt_tolerance;

  size_t _iterations;

 public:
  // Implementation of the Block Search pivot rule
  class BlockSearchPivotRule {
   private:
    // References to the NetworkSimplex class
    const IntVector& _source;
    const IntVector& _target;
    const CostVector& _cost;
    const CharVector& _state;
    const CostVector& _pi;
    int& _in_arc;
    int _arc_num;
    int _dummy_arc;

    // Pivot rule data
    int _block_size;
    int _next_arc;

    // Negative eps
    const double negeps;

   public:
    // Constructor
    BlockSearchPivotRule(NetSimplexCapacity& ns)
        : _source(ns._source),
          _target(ns._target),
          _cost(ns._cost),
          _state(ns._state),
          _pi(ns._pi),
          _in_arc(ns.in_arc),
          _arc_num(ns._arc_num),
          _dummy_arc(ns._dummy_arc),
          _next_arc(ns._next_arc),
          negeps(std::nextafter(-ns._opt_tolerance, -0.0)) {
      // The main parameters of the pivot rule
      const double BLOCK_SIZE_FACTOR = 1.0;
      const int MIN_BLOCK_SIZE =
          20;  // THIS VALUE IS IMPORTANT AND IT SHOULD BE A PARAMETER (!)

      _block_size =
          std::max(int(BLOCK_SIZE_FACTOR * std::sqrt(double(_dummy_arc))),
                   MIN_BLOCK_SIZE);
    }

    // Find next entering arc
    bool findEnteringArc() {
      Cost c, min = negeps;
      int cnt = _block_size;
      int e;
      _in_arc = -1;
      for (e = _next_arc; e != _arc_num; ++e) {
        c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
        if (c < min) {
          min = c;
          _in_arc = e;
        }
        if (--cnt == 0) {
          if (min < negeps) goto search_end;
          cnt = _block_size;
        }
      }
      for (e = _dummy_arc; e != _next_arc; ++e) {
        c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
        if (c < min) {
          min = c;
          _in_arc = e;
        }
        if (--cnt == 0) {
          if (min < negeps) goto search_end;
          cnt = _block_size;
        }
      }
      if (min >= negeps) return false;

    search_end:
      _next_arc = e;
      return true;
    }

  };  // class BlockSearchPivotRule

 public:
  NetSimplexCapacity(const char INIT, int node_num, int arc_num)
      : _node_num(node_num),
        _arc_num(0),
{'fraction_non_alphanumeric': 0.09276665304454434, 'fraction_numerical': 0.0075602778912954634, 'mean_word_length': 2.535211267605634, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 19, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '82238', 'n_tokens_mistral': 3372, 'n_tokens_neox': 3223, 'n_words': 1007}