itlab_2024/src/graph/graph.cpp at 38a2cbf9bffdc739ff5dcb65695f643c4c35855a · embedded-dev-research/itlab_2024 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include "./graph/graph.h"

#include <iostream>
#include <list>
#include <queue>
#include <unordered_map>
#include <vector>

Vertex::Vertex(int id_) : id_(id_) {}

void Vertex::addNeighbor(int neighbor) {
  if (neighbor != id_) {
    neighbors_.push_back(neighbor);
  }
}

void Vertex::removeNeighbor(int neighbor) { neighbors_.remove(neighbor); }

void Vertex::print() const {
  std::cout << id_ << ": ";
  for (const int& neighbor : neighbors_) {
    std::cout << neighbor << " ";
  }
  std::cout << '\n';
}

int Vertex::getId() const { return id_; }

const std::list<int>& Vertex::getNeighbors() const { return neighbors_; }

Graph::Graph() = default;

void Graph::addVertex(int id_) {
  if (vertices_.find(id_) == vertices_.end()) {
    vertices_[id_] = new Vertex(id_);
  }
}

void Graph::addEdge(int u, int v) {
  if (vertices_.find(u) == vertices_.end()) {
    addVertex(u);
  }
  if (vertices_.find(v) == vertices_.end()) {
    addVertex(v);
  }
  vertices_[u]->addNeighbor(v);
}

void Graph::removeEdge(int u, int v) {
  if (vertices_.find(u) != vertices_.end()) {
    vertices_[u]->removeNeighbor(v);
  }
}

void Graph::removeVertex(int id_) {
  for (auto& pair : vertices_) {
    pair.second->removeNeighbor(id_);
  }
  auto it = vertices_.find(id_);
  if (it != vertices_.end()) {
    delete it->second;
    vertices_.erase(it);
  }
}

int Graph::getVertices() const { return static_cast<int>(vertices_.size()); }

int Graph::getEdges() const {
  int count = 0;
  for (const auto& vertice : vertices_) {
    count += (vertice.second->getNeighbors()).size();
  }
  return count;
}

bool Graph::empty() const { return vertices_.empty(); }

void Graph::printGraph() const {
  for (const auto& pair : vertices_) {
    pair.second->print();
  }
}

bool Graph::bfs_helper(int start, int vert, bool flag,
                       std::vector<int>* v_ord) {
  std::unordered_map<int, bool> visited;
  std::queue<int> queue;
  queue.push(start);
  visited[start] = true;

  while (!queue.empty()) {
    int current = queue.front();
    queue.pop();

    if (flag && current == vert) {
      return true;
    }
    if (v_ord != nullptr) {
      v_ord->push_back(current);
    }

    if (vertices_.find(current) != vertices_.end()) {
      for (const int& neighbor : vertices_[current]->getNeighbors()) {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      }
    }
  }
  return false;
}

bool Graph::hasPath(int u, int v) {
  if (vertices_.find(u) == vertices_.end() ||
      vertices_.find(v) == vertices_.end()) {
    return false;
  }
  return bfs_helper(u, v, true, nullptr);
}

std::vector<int> Graph::BFS(int start) {
  std::vector<int> v_ord;
  bfs_helper(start, -1, false, &v_ord);
  return v_ord;
}

Graph::~Graph() {
  for (auto& pair : vertices_) {
    delete pair.second;
  }
}