446 lines
12 KiB
C++
446 lines
12 KiB
C++
#include <algorithm>
|
|
#include <climits>
|
|
#include <fstream>
|
|
#include <sstream>
|
|
#include <string>
|
|
#include <tuple>
|
|
#include <set>
|
|
#include <vector>
|
|
|
|
using namespace std;
|
|
|
|
// Базовый класс представления
|
|
class IGRepr {
|
|
public:
|
|
virtual void from_file(string filepath) = 0;
|
|
virtual void to_file(string filepath,bool is_oriented, bool is_weighted) = 0;
|
|
virtual void add_edge(int vertex_a, int vertex_b, int weight) = 0;
|
|
virtual void remove_edge(int vertex_a, int vertex_b) = 0;
|
|
virtual int change_weight(int vertex_a, int vertex_b, int new_weight) = 0;
|
|
virtual vector<tuple<int,int,int>> get_edges() = 0;
|
|
virtual ~IGRepr() {};
|
|
virtual int count_vertices() = 0;
|
|
};
|
|
|
|
// Представление в виде матрицы смежности
|
|
class AdjMatrix: public IGRepr {
|
|
private:
|
|
vector<vector<int>> matrix;
|
|
public:
|
|
AdjMatrix(int n = 0);
|
|
virtual void from_file(string filepath) override;
|
|
virtual void to_file(string filepath,bool is_oriented, bool is_weighted) override;
|
|
virtual void add_edge(int vertex_a, int vertex_b, int weight) override;
|
|
virtual void remove_edge(int vertex_a, int vertex_b) override;
|
|
virtual int change_weight(int vertex_a, int vertex_b, int new_weight) override;
|
|
virtual vector<tuple<int,int,int>> get_edges() override;
|
|
virtual int count_vertices() override;
|
|
};
|
|
|
|
AdjMatrix::AdjMatrix(int n) {
|
|
for (int i = 0; i < n; i++){
|
|
vector<int> temp;
|
|
for (int j = 0; j < n; j++)
|
|
temp.push_back(0);
|
|
matrix.push_back(temp);
|
|
}
|
|
}
|
|
|
|
void AdjMatrix::add_edge(int vertex_a, int vertex_b, int weight){
|
|
if (matrix[vertex_a][vertex_b] != 0) return;
|
|
matrix[vertex_a][vertex_b] = weight;
|
|
}
|
|
|
|
void AdjMatrix::remove_edge(int vertex_a, int vertex_b) {
|
|
matrix[vertex_a][vertex_b] = 0;
|
|
}
|
|
int AdjMatrix::change_weight(int vertex_a, int vertex_b, int new_weight) {
|
|
int old_weight = matrix[vertex_a][vertex_b];
|
|
|
|
matrix[vertex_a][vertex_b] = new_weight;
|
|
|
|
return old_weight;
|
|
}
|
|
void AdjMatrix::from_file(string filepath) {
|
|
ifstream file{filepath};
|
|
string buffer;
|
|
|
|
// Чтение первых двух строк
|
|
|
|
getline(file,buffer);
|
|
istringstream initial_iss{buffer};
|
|
char _type;
|
|
initial_iss >> _type;
|
|
int vertices;
|
|
initial_iss >> vertices;
|
|
for(int i = 0; i < vertices; i++) {
|
|
matrix.push_back(vector<int>{});
|
|
for(int j = 0; j < vertices; j++) {
|
|
matrix[i].push_back(0);
|
|
}
|
|
}
|
|
|
|
getline(file,buffer);
|
|
|
|
int from_vertex = 0;
|
|
// Чтение непосредственно данных
|
|
while(getline(file,buffer)) {
|
|
istringstream iss{buffer};
|
|
int to_vertex = 0;
|
|
int weight;
|
|
while (iss >> weight) {
|
|
matrix[from_vertex][to_vertex] = weight;
|
|
to_vertex += 1;
|
|
}
|
|
from_vertex += 1;
|
|
}
|
|
|
|
file.close();
|
|
}
|
|
void AdjMatrix::to_file(string filepath,bool is_oriented, bool is_weighted) {
|
|
ofstream file{filepath};
|
|
|
|
file << 'C' << matrix.size() << " " << endl;
|
|
file << (int)is_oriented << " " << (int)is_weighted << endl;
|
|
for(int i = 0; i < matrix.size(); i++){
|
|
for(int j = 0; j < matrix[i].size(); j++)
|
|
file << matrix[i][j] << " ";
|
|
file << endl;
|
|
}
|
|
}
|
|
|
|
vector<tuple<int,int,int>> AdjMatrix::get_edges() {
|
|
vector<tuple<int,int,int>> result;
|
|
for(int i = 0; i < matrix.size(); i++)
|
|
for (int j = 0; j < matrix[i].size(); j++)
|
|
if (matrix[i][j] != 0)
|
|
result.push_back({i,j,matrix[i][j]});
|
|
return result;
|
|
}
|
|
|
|
int AdjMatrix::count_vertices() {
|
|
return matrix.size();
|
|
}
|
|
|
|
// Представление в виде списка смежных вершин
|
|
class AdjList: public IGRepr {
|
|
private:
|
|
vector<set<pair<int, int>>> list;
|
|
public:
|
|
AdjList(int n=0);
|
|
virtual void from_file(string filepath) override;
|
|
virtual void to_file(string filepath,bool is_oriented, bool is_weighted) override;
|
|
virtual void add_edge(int vertex_a, int vertex_b, int weight) override;
|
|
virtual void remove_edge(int vertex_a, int vertex_b) override;
|
|
virtual int change_weight(int vertex_a, int vertex_b, int new_weight) override;
|
|
virtual vector<tuple<int,int,int>> get_edges() override;
|
|
virtual int count_vertices() override;
|
|
};
|
|
|
|
AdjList::AdjList(int n){
|
|
for(int i = 0; i < n; i++)
|
|
list.push_back({});
|
|
}
|
|
|
|
void AdjList::add_edge(int vertex_a, int vertex_b, int weight){
|
|
auto found = list[vertex_a].lower_bound({vertex_b,INT_MIN});
|
|
if (found != list[vertex_a].end() && found->first == vertex_b)
|
|
return;
|
|
list[vertex_a].insert({vertex_b,weight});
|
|
}
|
|
|
|
void AdjList::remove_edge(int vertex_a, int vertex_b) {
|
|
auto found = list[vertex_a].lower_bound({vertex_b,INT_MIN});
|
|
if (found == list[vertex_a].end() || found->first != vertex_b)
|
|
return;
|
|
list[vertex_a].erase(*found);
|
|
}
|
|
int AdjList::change_weight(int vertex_a, int vertex_b, int new_weight) {
|
|
auto found = list[vertex_a].lower_bound({vertex_b,INT_MIN});
|
|
int old_weight = found->second;
|
|
|
|
list[vertex_a].erase(found);
|
|
list[vertex_a].insert({vertex_b,new_weight});
|
|
|
|
return old_weight;
|
|
|
|
}
|
|
void AdjList::from_file(string filepath) {
|
|
ifstream file{filepath};
|
|
string buffer;
|
|
|
|
// Чтение первых двух строк
|
|
|
|
getline(file,buffer);
|
|
istringstream initial_iss{buffer};
|
|
char _type;
|
|
initial_iss >> _type;
|
|
int vertices;
|
|
initial_iss >> vertices;
|
|
for(int i = 0; i < vertices; i++) {
|
|
list.push_back(set<pair<int,int>>{});
|
|
}
|
|
|
|
getline(file,buffer);
|
|
istringstream meta_iss{buffer};
|
|
bool _oriented, weighted;
|
|
meta_iss >> _oriented >> weighted;
|
|
|
|
int from_vertex = 0;
|
|
// Чтение непосредственно данных
|
|
if (weighted) {
|
|
while(getline(file,buffer)) {
|
|
istringstream iss{buffer};
|
|
int to_vertex, weight;
|
|
while (iss >> to_vertex >> weight) {
|
|
list[from_vertex].insert({to_vertex,weight});
|
|
}
|
|
from_vertex += 1;
|
|
}
|
|
}
|
|
else {
|
|
while(getline(file,buffer)) {
|
|
istringstream iss{buffer};
|
|
int to_vertex;
|
|
while (iss >> to_vertex) {
|
|
list[from_vertex].insert({to_vertex,1});
|
|
}
|
|
from_vertex += 1;
|
|
}
|
|
}
|
|
file.close();
|
|
}
|
|
void AdjList::to_file(string filepath,bool is_oriented, bool is_weighted) {
|
|
ofstream file{filepath};
|
|
|
|
file << 'L' << " " << list.size() << endl;
|
|
file << (int)is_oriented << " " << (int)is_weighted << endl;
|
|
if (is_weighted)
|
|
for(int i = 0; i < list.size(); i++){
|
|
for(auto j = list[i].begin(); j != list[i].end(); ++j)
|
|
file << j->first << " " << j-> second << " ";
|
|
file << endl;
|
|
}
|
|
else
|
|
for(int i = 0; i < list.size(); i++){
|
|
for(auto j = list[i].begin(); j != list[i].end(); ++j)
|
|
file << j->first << " ";
|
|
file << endl;
|
|
}
|
|
}
|
|
|
|
vector<tuple<int,int,int>> AdjList::get_edges() {
|
|
vector<tuple<int,int,int>> result;
|
|
for(int i = 0; i < list.size(); i++)
|
|
for (auto j = list[i].begin(); j != list[i].end(); ++j)
|
|
result.push_back({i,j->first,j->second});
|
|
return result;
|
|
}
|
|
|
|
int AdjList::count_vertices() {
|
|
return list.size();
|
|
}
|
|
|
|
// Представление в виде списка рёбер
|
|
class EdgeList: public IGRepr {
|
|
public:
|
|
vector<tuple<int,int,int>> list;
|
|
virtual void from_file(string filepath) override;
|
|
virtual void to_file(string filepath,bool is_oriented, bool is_weighted) override;
|
|
virtual void add_edge(int vertex_a, int vertex_b, int weight) override;
|
|
virtual void remove_edge(int vertex_a, int vertex_b) override;
|
|
virtual int change_weight(int vertex_a, int vertex_b, int new_weight) override;
|
|
virtual vector<tuple<int,int,int>> get_edges() override;
|
|
virtual int count_vertices() override;
|
|
};
|
|
void EdgeList::add_edge(int vertex_a, int vertex_b, int weight){
|
|
auto found = find_if(list.begin(),list.end(),
|
|
[vertex_a,vertex_b](const tuple<int,int,int>& edge) {
|
|
return get<0>(edge) == vertex_a && get<1>(edge) == vertex_b;
|
|
}
|
|
);
|
|
if (found != list.end())
|
|
return;
|
|
list.push_back({vertex_a,vertex_b,weight});
|
|
}
|
|
|
|
void EdgeList::remove_edge(int vertex_a, int vertex_b) {
|
|
auto found = find_if(list.begin(),list.end(),
|
|
[vertex_a,vertex_b](const tuple<int,int,int>& edge) {
|
|
return get<0>(edge) == vertex_a && get<1>(edge) == vertex_b;
|
|
}
|
|
);
|
|
|
|
list.erase(found);
|
|
}
|
|
int EdgeList::change_weight(int vertex_a, int vertex_b, int new_weight) {
|
|
auto found = find_if(list.begin(),list.end(),
|
|
[vertex_a,vertex_b](const tuple<int,int,int>& edge) {
|
|
return get<0>(edge) == vertex_a && get<1>(edge) == vertex_b;
|
|
}
|
|
);
|
|
int old_weight = get<2>(*found);
|
|
|
|
list.erase(found);
|
|
list.push_back({vertex_a,vertex_b,new_weight});
|
|
|
|
return old_weight;
|
|
|
|
}
|
|
void EdgeList::from_file(string filepath) {
|
|
ifstream file{filepath};
|
|
string buffer;
|
|
|
|
// Чтение первых двух строк
|
|
|
|
getline(file,buffer);
|
|
istringstream initial_iss{buffer};
|
|
char _type;
|
|
initial_iss >> _type;
|
|
int _vertices,edges;
|
|
initial_iss >> _vertices >> edges;
|
|
getline(file,buffer);
|
|
istringstream meta_iss{buffer};
|
|
bool _oriented, weighted;
|
|
meta_iss >> _oriented >> weighted;
|
|
|
|
// Чтение непосредственно данных
|
|
if (weighted) {
|
|
while(getline(file,buffer)) {
|
|
istringstream iss{buffer};
|
|
int from_vertex, to_vertex, weight;
|
|
iss >> from_vertex >> to_vertex >> weight;
|
|
list.push_back({from_vertex,to_vertex,weight});
|
|
}
|
|
}
|
|
else {
|
|
while(getline(file,buffer)) {
|
|
istringstream iss{buffer};
|
|
int from_vertex, to_vertex;
|
|
iss >> from_vertex >> to_vertex;
|
|
list.push_back({from_vertex,to_vertex,1});
|
|
}
|
|
}
|
|
file.close();
|
|
}
|
|
void EdgeList::to_file(string filepath,bool is_oriented, bool is_weighted) {
|
|
ofstream file{filepath};
|
|
|
|
file << 'E' << " " << count_vertices() << " " << list.size() << endl;
|
|
file << (int)is_oriented << " " << (int)is_weighted << endl;
|
|
if (is_weighted)
|
|
for(auto i = list.begin(); i < list.end(); ++i){
|
|
file << get<0>(*i) << " " << get<1>(*i) << " " << get<2>(*i) << endl;
|
|
}
|
|
else
|
|
for(auto i = list.begin(); i < list.end(); ++i){
|
|
file << get<0>(*i) << " " << get<1>(*i) << endl;
|
|
}
|
|
}
|
|
vector<tuple<int,int,int>> EdgeList::get_edges() {
|
|
return list;
|
|
}
|
|
int EdgeList::count_vertices() {
|
|
int max_vertex = 0;
|
|
for(int i = 0; i < list.size(); i++)
|
|
max_vertex = max(max_vertex,max(get<0>(list[i]),get<1>(list[i])));
|
|
return max_vertex + 1;
|
|
}
|
|
|
|
// Непосредственно граф
|
|
class Graph {
|
|
private:
|
|
IGRepr* repr;
|
|
bool oriented;
|
|
bool weighted;
|
|
void transformTo(IGRepr* new_repr);
|
|
public:
|
|
void readGraph(string fileName);
|
|
void writeGraph(string fileName);
|
|
void addEdge(int from, int to, int weight);
|
|
void removeEdge(int from, int to);
|
|
int changeEdge(int from, int to, int newWeight);
|
|
void transformToAdjList();
|
|
void transformToAdjMatrix();
|
|
void transformToListOfEdges();
|
|
~Graph();
|
|
};
|
|
|
|
void Graph::readGraph(string fileName) {
|
|
ifstream file{fileName};
|
|
string buffer;
|
|
getline(file,buffer);
|
|
switch (buffer[0]) {
|
|
case 'C':
|
|
repr = new AdjMatrix;
|
|
break;
|
|
case 'E':
|
|
repr = new EdgeList;
|
|
break;
|
|
case 'L':
|
|
repr = new AdjList;
|
|
break;
|
|
}
|
|
|
|
repr->from_file(fileName);
|
|
getline(file,buffer);
|
|
istringstream stream {buffer};
|
|
stream >> oriented >> weighted;
|
|
file.close();
|
|
}
|
|
|
|
void Graph::writeGraph(string fileName){
|
|
repr->to_file(fileName,oriented,weighted);
|
|
}
|
|
|
|
void Graph::addEdge(int from, int to, int weight) {
|
|
repr->add_edge(from, to, weight);
|
|
if (oriented == false)
|
|
repr->add_edge(to, from, weight);
|
|
}
|
|
|
|
void Graph::removeEdge(int from, int to) {
|
|
repr->remove_edge(from, to);
|
|
if (oriented == false)
|
|
repr->remove_edge(to, from);
|
|
}
|
|
int Graph::changeEdge(int from, int to, int newWeight){
|
|
if (weighted && newWeight != 1)
|
|
weighted = false;
|
|
return repr->change_weight(from, to, newWeight);
|
|
}
|
|
|
|
Graph::~Graph() {
|
|
delete repr;
|
|
}
|
|
|
|
void Graph::transformTo(IGRepr* new_repr) {
|
|
auto edges = repr->get_edges();
|
|
for (int i = 0; i < edges.size(); i++)
|
|
new_repr->add_edge(get<0>(edges[i]),get<1>(edges[i]) ,get<2>(edges[i]) );
|
|
delete repr;
|
|
repr = new_repr;
|
|
}
|
|
void Graph::transformToAdjList() {
|
|
transformTo(new AdjList(repr->count_vertices()));
|
|
}
|
|
void Graph::transformToAdjMatrix(){
|
|
transformTo(new AdjMatrix(repr->count_vertices()));
|
|
}
|
|
|
|
void Graph::transformToListOfEdges() {
|
|
transformTo(new EdgeList);
|
|
}
|
|
|
|
int main() {
|
|
Graph graph;
|
|
graph.readGraph("input.txt");
|
|
graph.transformToAdjList();
|
|
graph.writeGraph("output_adj_list.txt");
|
|
graph.transformToListOfEdges();
|
|
graph.writeGraph("output_edge_list.txt");
|
|
graph.transformToAdjMatrix();
|
|
graph.writeGraph("output_adj_matrix.txt");
|
|
|
|
return 0;
|
|
}
|