322 lines
9.6 KiB
C++
322 lines
9.6 KiB
C++
#include "Graph.h"
|
|
#include <fstream>
|
|
#include <sstream>
|
|
#include <algorithm>
|
|
#include <climits>
|
|
|
|
Graph::Graph() : n(0), directed(false), weighted(false), form('C') {
|
|
matrix.assign(1, std::vector<int>(1, 0));
|
|
}
|
|
|
|
Graph::Graph(int n_) : n(n_), directed(false), weighted(true), form('L') {
|
|
adj.assign(n + 1, std::set<std::pair<int, int>>());
|
|
}
|
|
|
|
Graph::Graph(int n_, bool directed_, bool weighted_, char form_)
|
|
: n(n_), directed(directed_), weighted(weighted_), form(form_) {
|
|
if (form == 'C') matrix.assign(n + 1, std::vector<int>(n + 1, 0));
|
|
else if (form == 'L') adj.assign(n + 1, std::set<std::pair<int, int>>());
|
|
}
|
|
|
|
void Graph::readGraph(std::string fileName) {
|
|
std::ifstream in(fileName);
|
|
if (!in.is_open()) return;
|
|
|
|
char t;
|
|
in >> t;
|
|
form = t;
|
|
|
|
int m = 0;
|
|
if (form == 'E') in >> n >> m;
|
|
else in >> n;
|
|
|
|
int d, w;
|
|
in >> d >> w;
|
|
directed = (d == 1);
|
|
weighted = (w == 1);
|
|
|
|
matrix.clear();
|
|
adj.clear();
|
|
edges.clear();
|
|
|
|
if (form == 'C') {
|
|
matrix.assign(n + 1, std::vector<int>(n + 1, 0));
|
|
for (int i = 1; i <= n; ++i)
|
|
for (int j = 1; j <= n; ++j) in >> matrix[i][j];
|
|
if (!directed) {
|
|
for (int i = 1; i <= n; ++i)
|
|
for (int j = i + 1; j <= n; ++j) {
|
|
if (matrix[i][j] == 0) matrix[i][j] = matrix[j][i];
|
|
if (matrix[j][i] == 0) matrix[j][i] = matrix[i][j];
|
|
}
|
|
}
|
|
} else if (form == 'L') {
|
|
adj.assign(n + 1, std::set<std::pair<int, int>>());
|
|
std::string line;
|
|
std::getline(in, line); // rest of the "D W" line
|
|
for (int i = 1; i <= n; ++i) {
|
|
std::getline(in, line);
|
|
std::istringstream ss(line);
|
|
if (weighted) {
|
|
int v, wgt;
|
|
while (ss >> v >> wgt) adj[i].insert({v, wgt});
|
|
} else {
|
|
int v;
|
|
while (ss >> v) adj[i].insert({v, 1});
|
|
}
|
|
}
|
|
if (!directed) {
|
|
for (int u = 1; u <= n; ++u) {
|
|
std::vector<std::pair<int, int>> snapshot(adj[u].begin(), adj[u].end());
|
|
for (auto& pr : snapshot) adj[pr.first].insert({u, pr.second});
|
|
}
|
|
}
|
|
} else { // 'E'
|
|
edges.reserve(m);
|
|
std::set<std::pair<int, int>> seen;
|
|
for (int i = 0; i < m; ++i) {
|
|
int a, b, wgt = 1;
|
|
in >> a >> b;
|
|
if (weighted) in >> wgt;
|
|
if (!directed) {
|
|
auto key = std::minmax(a, b);
|
|
if (!seen.insert({key.first, key.second}).second) continue;
|
|
}
|
|
edges.push_back({a, b, wgt});
|
|
}
|
|
}
|
|
}
|
|
|
|
void Graph::writeGraph(std::string fileName) {
|
|
std::ofstream out(fileName);
|
|
if (!out.is_open()) return;
|
|
|
|
if (form == 'E') out << "E " << n << ' ' << edges.size() << '\n';
|
|
else out << form << ' ' << n << '\n';
|
|
out << (directed ? 1 : 0) << ' ' << (weighted ? 1 : 0) << '\n';
|
|
|
|
if (form == 'C') {
|
|
for (int i = 1; i <= n; ++i) {
|
|
for (int j = 1; j <= n; ++j) out << matrix[i][j] << ' ';
|
|
out << '\n';
|
|
}
|
|
} else if (form == 'L') {
|
|
for (int i = 1; i <= n; ++i) {
|
|
bool first = true;
|
|
for (auto& e : adj[i]) {
|
|
if (!first) out << ' ';
|
|
first = false;
|
|
out << e.first;
|
|
if (weighted) out << ' ' << e.second;
|
|
}
|
|
out << '\n';
|
|
}
|
|
} else {
|
|
for (auto& e : edges) {
|
|
out << std::get<0>(e) << ' ' << std::get<1>(e);
|
|
if (weighted) out << ' ' << std::get<2>(e);
|
|
out << '\n';
|
|
}
|
|
}
|
|
out << '\n';
|
|
}
|
|
|
|
bool Graph::hasEdge(int from, int to) const {
|
|
if (from < 1 || from > n || to < 1 || to > n) return false;
|
|
if (form == 'C') return matrix[from][to] != 0;
|
|
if (form == 'L') {
|
|
auto it = adj[from].lower_bound({to, INT_MIN});
|
|
return it != adj[from].end() && it->first == to;
|
|
}
|
|
for (auto& e : edges)
|
|
if ((std::get<0>(e) == from && std::get<1>(e) == to) ||
|
|
(!directed && std::get<0>(e) == to && std::get<1>(e) == from))
|
|
return true;
|
|
return false;
|
|
}
|
|
|
|
int Graph::weightOf(int from, int to) const {
|
|
if (from < 1 || from > n || to < 1 || to > n) return 0;
|
|
if (form == 'C') return matrix[from][to];
|
|
if (form == 'L') {
|
|
auto it = adj[from].lower_bound({to, INT_MIN});
|
|
if (it != adj[from].end() && it->first == to) return it->second;
|
|
return 0;
|
|
}
|
|
for (auto& e : edges)
|
|
if ((std::get<0>(e) == from && std::get<1>(e) == to) ||
|
|
(!directed && std::get<0>(e) == to && std::get<1>(e) == from))
|
|
return std::get<2>(e);
|
|
return 0;
|
|
}
|
|
|
|
void Graph::addEdge(int from, int to, int weight) {
|
|
if (!weighted) weight = 1;
|
|
if (hasEdge(from, to)) return;
|
|
if (form == 'C') {
|
|
matrix[from][to] = weight;
|
|
if (!directed) matrix[to][from] = weight;
|
|
} else if (form == 'L') {
|
|
adj[from].insert({to, weight});
|
|
if (!directed) adj[to].insert({from, weight});
|
|
} else {
|
|
edges.push_back({from, to, weight});
|
|
}
|
|
}
|
|
|
|
void Graph::removeEdge(int from, int to) {
|
|
if (form == 'C') {
|
|
if (matrix[from][to] == 0) return;
|
|
matrix[from][to] = 0;
|
|
if (!directed) matrix[to][from] = 0;
|
|
} else if (form == 'L') {
|
|
auto it = adj[from].lower_bound({to, INT_MIN});
|
|
if (it != adj[from].end() && it->first == to) adj[from].erase(it);
|
|
if (!directed) {
|
|
auto jt = adj[to].lower_bound({from, INT_MIN});
|
|
if (jt != adj[to].end() && jt->first == from) adj[to].erase(jt);
|
|
}
|
|
} else {
|
|
for (auto it = edges.begin(); it != edges.end(); ++it) {
|
|
bool match = (std::get<0>(*it) == from && std::get<1>(*it) == to) ||
|
|
(!directed && std::get<0>(*it) == to && std::get<1>(*it) == from);
|
|
if (match) {
|
|
edges.erase(it);
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
int Graph::changeEdge(int from, int to, int newWeight) {
|
|
if (!weighted) newWeight = 1;
|
|
if (form == 'C') {
|
|
int old = matrix[from][to];
|
|
if (old == 0) return 0;
|
|
matrix[from][to] = newWeight;
|
|
if (!directed) matrix[to][from] = newWeight;
|
|
return old;
|
|
}
|
|
if (form == 'L') {
|
|
auto it = adj[from].lower_bound({to, INT_MIN});
|
|
if (it == adj[from].end() || it->first != to) return 0;
|
|
int old = it->second;
|
|
adj[from].erase(it);
|
|
adj[from].insert({to, newWeight});
|
|
if (!directed) {
|
|
auto jt = adj[to].lower_bound({from, INT_MIN});
|
|
if (jt != adj[to].end() && jt->first == from) {
|
|
adj[to].erase(jt);
|
|
adj[to].insert({from, newWeight});
|
|
}
|
|
}
|
|
return old;
|
|
}
|
|
for (auto& e : edges) {
|
|
bool match = (std::get<0>(e) == from && std::get<1>(e) == to) ||
|
|
(!directed && std::get<0>(e) == to && std::get<1>(e) == from);
|
|
if (match) {
|
|
int old = std::get<2>(e);
|
|
std::get<2>(e) = newWeight;
|
|
return old;
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
std::vector<std::set<std::pair<int, int>>> Graph::toAdjList() const {
|
|
if (form == 'L') return adj;
|
|
|
|
std::vector<std::set<std::pair<int, int>>> g(n + 1);
|
|
if (form == 'C') {
|
|
for (int i = 1; i <= n; ++i)
|
|
for (int j = 1; j <= n; ++j) {
|
|
if (i == j || matrix[i][j] == 0) continue;
|
|
g[i].insert({j, matrix[i][j]});
|
|
if (!directed) g[j].insert({i, matrix[i][j]});
|
|
}
|
|
} else {
|
|
for (auto& e : edges) {
|
|
int a = std::get<0>(e), b = std::get<1>(e), w = std::get<2>(e);
|
|
g[a].insert({b, w});
|
|
if (!directed) g[b].insert({a, w});
|
|
}
|
|
}
|
|
return g;
|
|
}
|
|
|
|
std::vector<std::vector<int>> Graph::toMatrix() const {
|
|
if (form == 'C') return matrix;
|
|
|
|
std::vector<std::vector<int>> M(n + 1, std::vector<int>(n + 1, 0));
|
|
if (form == 'L') {
|
|
for (int u = 1; u <= n; ++u)
|
|
for (auto& e : adj[u]) {
|
|
M[u][e.first] = e.second;
|
|
if (!directed) M[e.first][u] = e.second;
|
|
}
|
|
} else {
|
|
for (auto& e : edges) {
|
|
int a = std::get<0>(e), b = std::get<1>(e), w = std::get<2>(e);
|
|
M[a][b] = w;
|
|
if (!directed) M[b][a] = w;
|
|
}
|
|
}
|
|
return M;
|
|
}
|
|
|
|
std::vector<std::tuple<int, int, int>> Graph::toEdgeList() const {
|
|
if (form == 'E') return edges;
|
|
|
|
std::vector<std::tuple<int, int, int>> el;
|
|
if (form == 'L') {
|
|
for (int u = 1; u <= n; ++u)
|
|
for (auto& e : adj[u]) {
|
|
if (!directed && e.first < u) continue;
|
|
el.push_back({u, e.first, e.second});
|
|
}
|
|
} else {
|
|
for (int i = 1; i <= n; ++i)
|
|
for (int j = (directed ? 1 : i); j <= n; ++j) {
|
|
if (matrix[i][j] == 0) continue;
|
|
el.push_back({i, j, matrix[i][j]});
|
|
}
|
|
}
|
|
return el;
|
|
}
|
|
|
|
std::vector<std::set<int>> Graph::toSimpleAdj() const {
|
|
auto g = toAdjList();
|
|
std::vector<std::set<int>> nb(n + 1);
|
|
for (int u = 1; u <= n; ++u)
|
|
for (auto& e : g[u]) {
|
|
nb[u].insert(e.first);
|
|
nb[e.first].insert(u);
|
|
}
|
|
return nb;
|
|
}
|
|
|
|
void Graph::transformToAdjList() {
|
|
if (form == 'L') return;
|
|
adj = toAdjList();
|
|
matrix.clear();
|
|
edges.clear();
|
|
form = 'L';
|
|
}
|
|
|
|
void Graph::transformToAdjMatrix() {
|
|
if (form == 'C') return;
|
|
matrix = toMatrix();
|
|
adj.clear();
|
|
edges.clear();
|
|
form = 'C';
|
|
}
|
|
|
|
void Graph::transformToListOfEdges() {
|
|
if (form == 'E') return;
|
|
edges = toEdgeList();
|
|
matrix.clear();
|
|
adj.clear();
|
|
form = 'E';
|
|
}
|