MaxFlowDinic/Graph.h

#pragma once

#include <chrono>
#include <vector>
#include <set>
#include <stack>
#include <string>
#include <fstream>
#include <iostream>

#include "util/GraphParser.h"
#include "util/Arc.h"

#define NO_AUGMENTING_PATH_FOUND -1

#define INVALID_VERTEX -1
#define NOT_PROCESSED 0
#define ON_STACK 1
#define PROCESSED 2


typedef std::vector<std::vector<Capacity>> CapacityMatrix;

namespace data {
  class Graph {
    public:
      Graph(bool stdout_output, bool file_output, std::string output_filename, bool verbose_max_flow, bool min_cut, int verbosity);

      void parseFromString(const std::string &graph_string);
      void parseFromFile(const std::string &graph_file);

      int maxFlowDinic();
      void printMatrices() const;
      void hasUniqueMaxFlow();
      void hasUniqueMinCut();

    private:
      void initMatrices();
      void initOstream();

      void constructLevelGraph();
      int findAugmentingPaths();
      void buildPath(std::vector<Vertex> &current_path);
      void computeFlowForPath(const std::vector<Vertex> &current_path);

      void isResidualGraphCyclic(const CapacityMatrix &residual_graph, int *visited, const int previous, std::stack<int> *recursive_stack, bool &found_cycle);
      void printCycle(const CapacityMatrix residual_matrix, std::stack<int> *stack);

      void computeMinCut(std::vector<Vertex> *source_vertices = nullptr, std::vector<Vertex> *sink_vertices = nullptr, std::vector<Arc> *cut_edges = nullptr) const;
      void incrementArcCapacity(const int source, const int sink);

      void printInformation() const;
      void printMaxFlowInformation() const;
      void printMinCut() const;
      void printComputationStatistics(const std::chrono::steady_clock::time_point &start, const std::chrono::steady_clock::time_point &end) const;

      void disableOutput();
      void enableOutput();
      void resetNetwork();

      std::vector<Vertex> m_vertices;
      std::vector<Arc> m_arc_list;
      VertexID m_source_id;
      VertexID m_sink_id;
      std::vector<Vertex>::iterator m_source;
      std::vector<Vertex>::iterator m_sink;

      CapacityMatrix m_network;
      CapacityMatrix m_flow;
      CapacityMatrix m_capapcities;

      int m_num_vertices;
      int m_num_arcs;

      int m_max_flow = 0;

      bool m_stdout_output = true;
      bool m_file_output = false;
      std::string m_output_file_name;
      std::ostream *m_ofstream;
      bool m_verbose_max_flow = false;
      bool m_min_cut = false;
      int m_verbosity = 0;

      uint m_num_paths = 0;
      uint m_num_build_path_calls = 0;
      uint m_num_level_graphs_built = 0;
      std::vector<std::string> m_augmenting_paths;
  };
}