graph.cc

#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <climits>

class Graph
{
public:
  void addVertex(const std::string& str);
  void addEdge(const std::string& startVertex, const std::string& endVertex, int weight);
  std::vector<std::string> DFS() const;
  std::vector<std::string> topoSort() const;
  std::vector<std::string> BFS() const;
  bool pathExistsDFS(const std::string& startVertex,
                     const std::string& endVertex,
                     std::vector<std::string>& path) const;
  bool pathExistsBFS(const std::string& startVertex,
                     const std::string& endVertex,
                     std::vector<std::string>& path) const;
  bool isCyclic() const;
  bool isTree() const;
  Graph cloneGraph() const;

private:
  class Edge;

  struct Vertex
  {
    explicit Vertex(const std::string& name_) : name(name_) {}
    void addEdge(const Vertex* vertex, int weight);
    bool isCyclic(std::unordered_set<std::string>& visited,
                  std::unordered_set<std::string>& visited_rec) const;
    void DFS(std::unordered_set<std::string>& visited, std::vector<std::string>& vec) const;
    bool topoSort(std::unordered_set<std::string>& visited,
                  std::unordered_set<std::string>& visited_rec,
                  std::stack<std::string>& vertex_stack) const;
    void BFS(std::unordered_set<std::string>& visited, std::queue<const Vertex*>& q) const;
    bool pathExistsDFS(const Vertex& endVertex,
                       std::unordered_set<std::string>& visited,
                       std::vector<std::string>& path) const;
    void pathExistsBFS(std::unordered_set<std::string>& visited,
                       std::queue<const Vertex*>& q) const;
    void clone(std::unordered_set<std::string>& visited, std::queue<const Vertex*>& q) const;

    std::vector<Edge> edgeList;
    std::string name;
  };

  struct Edge
  {
    explicit Edge(const Vertex* vertex_, int weight_) : vertex(vertex_), weight(weight_) {}
    const Vertex* vertex;
    int weight;
  };

  std::unordered_map<std::string, Vertex> vertexMap_;
};

void Graph::addVertex(const std::string& str)
{
  vertexMap_.emplace(str, str);
}

void Graph::addEdge(const std::string& startVertex, const std::string& endVertex, int weight)
{
  auto startItr = vertexMap_.find(startVertex);
  auto endItr = vertexMap_.find(endVertex);
  if ((startItr != vertexMap_.end()) && (endItr != vertexMap_.end())) {
    startItr->second.addEdge(&(endItr->second), weight);
  }
}

std::vector<std::string> Graph::DFS() const
{
  std::unordered_set<std::string> visited;
  std::vector<std::string> vec;

  for (const auto& itr : vertexMap_) {
    itr.second.DFS(visited, vec);
  }

  return vec;
}

std::vector<std::string> Graph::topoSort() const
{
  std::unordered_set<std::string> visited;
  std::unordered_set<std::string> visited_rec;
  std::stack<std::string> vertex_stack;

  for (const auto& itr : vertexMap_) {
    if (itr.second.topoSort(visited, visited_rec, vertex_stack)) {
      /* cyclic, cannot do topo sort */
      return {};
    }
  }

  std::vector<std::string> vec;

  while (!vertex_stack.empty()) {
    vec.emplace_back(vertex_stack.top());
    vertex_stack.pop();
  }

  return vec;
}

std::vector<std::string> Graph::BFS() const
{
  if (vertexMap_.empty()) {
    return {};
  }

  std::vector<std::string> vec;
  std::unordered_set<std::string> visited;
  std::queue<const Vertex*> q;

  auto itr = vertexMap_.begin();
  visited.emplace(itr->first);
  q.push(&(itr->second));

  while (!q.empty()) {
    const Vertex* vertex = q.front();
    vec.emplace_back(vertex->name);
    q.pop();
    vertex->BFS(visited, q);
  }

  return vec;
}

bool Graph::pathExistsDFS(const std::string& startVertex,
                          const std::string& endVertex,
                          std::vector<std::string>& path) const
{
  auto startItr = vertexMap_.find(startVertex);
  auto endItr = vertexMap_.find(endVertex);

  if ((startItr == vertexMap_.end()) || (endItr == vertexMap_.end())) {
    return false;
  }

  std::unordered_set<std::string> visited;
  return startItr->second.pathExistsDFS(endItr->second, visited, path);
}

bool Graph::pathExistsBFS(const std::string& startVertex,
                          const std::string& endVertex,
                          std::vector<std::string>& path) const
{
  auto startItr = vertexMap_.find(startVertex);
  auto endItr = vertexMap_.find(endVertex);

  if ((startItr == vertexMap_.end()) || (endItr == vertexMap_.end())) {
    throw "invalid vertex";
  }

  std::unordered_set<std::string> visited;
  std::queue<const Vertex*> q;
  q.push(&(startItr->second));

  while (!q.empty()) {
    const Vertex* vertex = q.front();
    path.emplace_back(vertex->name);
    if (vertex == &endItr->second) {
      return true;
    }
    q.pop();
    vertex->pathExistsBFS(visited, q);
  }

  return false;
}

bool Graph::isCyclic() const
{
  std::unordered_set<std::string> visited;
  std::unordered_set<std::string> visited_rec;

  for (const auto& itr : vertexMap_) {
    if (itr.second.isCyclic(visited, visited_rec)) {
      return true;
    }
  }

  return false;
}

bool Graph::isTree() const
{
  std::unordered_set<std::string> visited;
  std::unordered_set<std::string> visited_rec;

  for (const auto& itr : vertexMap_) {
    if ((visited.find(itr.first) == visited.end()) && itr.second.isCyclic(visited, visited_rec)) {
      return false;
    }
  }

  /* Not cyclic, now check if graph is connected */
  for (const auto& itr : vertexMap_) {
    if (visited.find(itr.first) == visited.end()) {
      return false;
    }
  }

  return true;
}

Graph Graph::cloneGraph() const
{
  std::unordered_set<std::string> visited;
  Graph graph;

  std::queue<const Vertex*> q;

  auto itr = vertexMap_.begin();
  visited.emplace(itr->first);
  q.push(&(itr->second));

  while (!q.empty()) {
    const Vertex* vertex = q.front();
    graph.addVertex(vertex->name);
    q.pop();
    vertex->clone(visited, q);
  }

  for (const auto& itr : graph.vertexMap_) {
    auto vertex_itr = vertexMap_.find(itr.first);
    for (const Edge& edge : vertex_itr->second.edgeList) {
      graph.addEdge(itr.first, edge.vertex->name, edge.weight);
    }
  }

  return graph;
}

void Graph::Vertex::addEdge(const Vertex* vertex, int weight)
{
  edgeList.emplace_back(vertex, weight);
}

bool Graph::Vertex::isCyclic(std::unordered_set<std::string>& visited,
                             std::unordered_set<std::string>& visited_rec) const
{
  if (visited.find(name) != visited.end()) {
    return false;
  }

  if (visited_rec.find(name) != visited_rec.end()) {
    return true;
  }

  visited.emplace(name);
  visited_rec.emplace(name);

  for (const Edge& edge : edgeList) {
    if (edge.vertex->isCyclic(visited, visited_rec)) {
      return true;
    }
  }

  visited_rec.erase(name);
  return false;
}

void Graph::Vertex::DFS(std::unordered_set<std::string>& visited,
                        std::vector<std::string>& vec) const
{
  if (visited.find(name) == visited.end()) {
    visited.emplace(name);
    vec.emplace_back(name);

    for (const Edge& edge : edgeList) {
      edge.vertex->DFS(visited, vec);
    }
  }
}

bool Graph::Vertex::topoSort(std::unordered_set<std::string>& visited,
                             std::unordered_set<std::string>& visited_rec,
                             std::stack<std::string>& vertex_stack) const
{
  if (visited.find(name) != visited.end()) {
    return false;
  }

  if (visited_rec.find(name) != visited_rec.end()) {
    return true;
  }

  visited.emplace(name);
  visited_rec.emplace(name);

  for (const Edge& edge : edgeList) {
    if (edge.vertex->topoSort(visited, visited_rec, vertex_stack)) {
      return true;
    }
  }

  visited_rec.erase(name);
  vertex_stack.push(name);

  return false;
}

void Graph::Vertex::BFS(std::unordered_set<std::string>& visited,
                        std::queue<const Vertex*>& q) const
{
  for (const Edge& edge : edgeList) {
    if (visited.find(edge.vertex->name) == visited.end()) {
      visited.emplace(edge.vertex->name);
      q.push(edge.vertex);
    }
  }
}

bool Graph::Vertex::pathExistsDFS(const Vertex& endVertex,
                                  std::unordered_set<std::string>& visited,
                                  std::vector<std::string>& path) const
{
  if (visited.find(name) != visited.end()) {
    return false;
  }

  visited.emplace(name);

  if (this == &endVertex) {
    return true;
  }

  for (const Edge& edge : edgeList) {
    if (edge.vertex->pathExistsDFS(endVertex, visited, path)) {
      return true;
    }
  }

  return false;
}

void Graph::Vertex::pathExistsBFS(std::unordered_set<std::string>& visited,
                                  std::queue<const Vertex*>& q) const
{
  for (const Edge& edge : edgeList) {
    if (visited.find(edge.vertex->name) == visited.end()) {
      visited.emplace(edge.vertex->name);
      q.push(edge.vertex);
    }
  }
}

void Graph::Vertex::clone(std::unordered_set<std::string>& visited,
                          std::queue<const Vertex*>& q) const
{
  for (const Edge& edge : edgeList) {
    if (visited.find(edge.vertex->name) == visited.end()) {
      visited.emplace(edge.vertex->name);
      q.push(edge.vertex);
    }
  }
}

class TaskScheduler
{
public:
  void addTask(const std::string& name,
               const std::vector<std::string>& input_files,
               const std::vector<std::string>& output_files,
               int time);
  std::vector<std::string> getTaskSchedOrder() const;
  int getTotalTime() const;

private:
  struct Task
  {
    Task(std::string task_name,
         std::vector<std::string> input_files,
         std::vector<std::string> output_files,
         int time)
        : task_name_(std::move(task_name)),
          input_files_(std::move(input_files)),
          output_files_(std::move(output_files)),
          time_(time)
    {
    }

    std::string task_name_;
    std::vector<std::string> input_files_;
    std::vector<std::string> output_files_;
    int time_;
  };

  using TaskMap = std::unordered_map<std::string, Task>;
  using TaskEndTimeMap = std::unordered_map<std::string, int>;
  using FileMap = std::unordered_map<std::string, const Task&>;

  TaskMap taskMap;

  FileMap getFileMap() const;

  int getTaskEndTime(const Task& task,
                     const FileMap& fileMap,
                     std::unordered_set<std::string>& taskVisited,
                     TaskEndTimeMap& taskEndTimeMap) const;
};

void TaskScheduler::addTask(const std::string& taskName,
                            const std::vector<std::string>& input_files,
                            const std::vector<std::string>& output_files,
                            int time)
{
  taskMap.try_emplace(taskName, taskName, input_files, output_files, time);
}

std::vector<std::string> TaskScheduler::getTaskSchedOrder() const
{
  Graph graph;

  FileMap fileMap = getFileMap();

  if (fileMap.empty()) {
    return std::vector<std::string>();
  }

  for (const auto& taskItr : taskMap) {
    for (const std::string& fileName : taskItr.second.input_files_) {
      auto fileItr = fileMap.find(fileName);
      graph.addEdge(fileItr->first, taskItr.first, 0);
    }
  }

  return graph.topoSort();
}

TaskScheduler::FileMap TaskScheduler::getFileMap() const
{
  FileMap file_map;

  for (const auto& itr : taskMap) {
    for (const std::string& fileName : itr.second.output_files_) {
      auto pair = file_map.emplace(fileName, itr.second);
      if (!pair.second) {
        return FileMap();
      }
    }
  }

  return file_map;
}

int TaskScheduler::getTotalTime() const
{
  FileMap file_map = getFileMap();

  if (file_map.empty()) {
    return -1;
  }

  int endTime = 0;
  TaskEndTimeMap taskEndTimeMap;
  std::unordered_set<std::string> taskVisited;

  for (const auto& itr : taskMap) {
    int taskEndTime = getTaskEndTime(itr.second, file_map, taskVisited, taskEndTimeMap);
    if (taskEndTime == -1) {
      return -1;
    }
    taskVisited.erase(taskVisited.begin(), taskVisited.end());
    endTime = std::max(endTime, taskEndTime);
  }

  return endTime;
}

int TaskScheduler::getTaskEndTime(const Task& task,
                                  const FileMap& fileMap,
                                  std::unordered_set<std::string>& taskVisited,
                                  TaskEndTimeMap& taskEndTimeMap) const
{
  if (taskVisited.find(task.task_name_) != taskVisited.end()) {
    return -1;
  }

  taskVisited.emplace(task.task_name_);

  auto itr = taskEndTimeMap.find(task.task_name_);

  if (itr != taskEndTimeMap.end()) {
    return itr->second;
  } else {
    int startTime = 0;
    for (const std::string& fileName : task.input_files_) {
      auto itr = fileMap.find(fileName);
      if (itr == fileMap.end()) {
        return -1;
      }
      int dep_task_end_time = getTaskEndTime(itr->second, fileMap, taskVisited, taskEndTimeMap);
      if (dep_task_end_time == -1) {
        return -1;
      }
      startTime = std::max(startTime, dep_task_end_time);
    }
    int endTime = startTime + task.time_;
    taskEndTimeMap.emplace(task.task_name_, endTime);
    return endTime;
  }
}

int main() {}