#include <string>
#include <time.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
#include <map>
using namespace std;
typedef struct vertex {
int x, y;
int index;
vector <pair<int, int>> edge_list;
};
typedef struct to_edge_list { // Структура чтобы переделать граф из списка смежностей в список ребер для алгоритма Б-Ф
int from, to, len;
};
typedef struct My_graph { // Сам граф для
map<string, vertex> v_list;
string fname;
};
//Заголовки
vector<string> msgs = { "0. Quit", "1. Add vertex.", "2. Add edge", "3. Delete vertex", "4. Show vertex list", "5. Find path" };
int dialog();
int D_Save(My_graph* G);
void save(std::ofstream& fout, My_graph* G);
bool D_Load(My_graph* G);
bool loaded(My_graph* G);
int D_Show(My_graph* G);
int D_Add_Vertex(My_graph* G);
int D_Add_Edge(My_graph* G);
int D_Delete_Vertex(My_graph* G);
bool add_edge(My_graph* G, string a, string b, int len);
bool StrToInt(string str, int* k)
{
try
{
*k = std::stoi(str);
return true;
}
catch (const std::exception&)
{
return false;
}
}
int dialog()
{
string errmsg = "";
string result;
int i, rc;
cout << endl;
while (true)
{
for (i = 0; i < msgs.size(); ++i)
cout << msgs[i] << endl;
cin >> result;
if (StrToInt(result, &rc) && rc >= 0 && rc <= 6)
return rc;
else
cout << "Wrong. Repeat.";
}
return 0;
}
//Добавление ребра
int D_Add_Edge(My_graph* G)
{
string name1, name2, str;
int len;
cout << "Enter vertex A name:";
cin >> name1;
while (G->v_list.find(name1) == G->v_list.end())
{
cout << "This name is not found in graph:";
cin >> name1;
}
cout << "Enter vertex B name:";
cin >> name2;
while (G->v_list.find(name2) == G->v_list.end())
{
cout << "This name is not found in graph:";
cin >> name2;
}
do
{
cout << "Input length:";
cin >> str;
} while (!StrToInt(str, &len));
add_edge(G, name1, name2, len);
return 1;
}
bool add_edge(My_graph* G, string a, string b, int len)
{
if (G->v_list.find(a) == G->v_list.end() || G->v_list.find(b) == G->v_list.end()) //Проверяем чтобы вершины были в графе
return false;
int index_a = G->v_list[a].index;
int index_b = G->v_list[b].index;
//Сделаем проверку что такого ребра мы не добавляли, у нас не МУЛЬТИГРАФ
if (G->v_list[a].edge_list.size() < G->v_list[b].edge_list.size())
{
for (int i = 0; i < G->v_list[a].edge_list.size(); i++)
if (G->v_list[a].edge_list[i].first == index_b)
return false;
}
else
{
for (int i = 0; i < G->v_list[b].edge_list.size(); i++)
if (G->v_list[b].edge_list[i].first == index_a)
return false;
}
G->v_list[a].edge_list.push_back(make_pair(index_b, len));
G->v_list[b].edge_list.push_back(make_pair(index_a, len));
return true;
}
//Вывод графа
int D_Show(My_graph* G)
{
map <string, vertex> ::iterator it = G->v_list.begin();
for (int i = 0; it != G->v_list.end(); it++, i++)
{
cout << it->first << " (" << it->second.x << "," << it->second.y << ") :" << endl;
for (int i = 0; i < it->second.edge_list.size(); i++)
{
map <string, vertex> ::iterator it_1 = G->v_list.begin();
int ind = it->second.edge_list[i].first; //Получаем в номер вершины в графе
int len = it->second.edge_list[i].second;//Получаем длину пути
advance(it_1, ind);
cout << " " << it_1->first << " " << len << endl;
}
}
return 1;
}
//Добавление вершины
int D_Add_Vertex(My_graph* G)
{
string name, str;
int x, y;
cout << "Enter vertex name:";
cin >> name;
while (G->v_list.find(name) != G->v_list.end())
{
cout << "This name is busy< enter another name:";
cin >> name;
}
do
{
cout << "Input x:";
cin >> str;
} while (!StrToInt(str, &x));
do
{
cout << "Input y:";
cin >> str;
} while (!StrToInt(str, &y));
vertex t;
t.x = x;
t.y = y;
if (G->v_list.size() == 0)//Если граф пустой то просто добавляем
{
t.index = 0;
G->v_list.insert(make_pair(name, t));
}
else//Если нет то необходимо найдем номер куда встанет наша вершина, и все остальные номер сделаем +1
{
t.index = -1;
G->v_list.insert(make_pair(name, t));
map <string, vertex> ::iterator it = G->v_list.begin();
int find_ind = -1;
for (int i = 0; it != G->v_list.end(); it++, i++)
if (it->first == name)
{
find_ind = i;
break;
}
for (it = G->v_list.begin(); it != G->v_list.end(); it++)
{
if (it->second.index >= find_ind)
it->second.index++;
for (int i = 0; i < it->second.edge_list.size(); i++)
if (it->second.edge_list[i].first >= find_ind)
it->second.edge_list[i].first++;
}
G->v_list[name].index = find_ind;
}
return 1;
}
//Удаление вершины
int D_Delete_Vertex(My_graph* G)
{
string name, str;
cout << "Enter vertex name:";
cin >> name;
if (G->v_list.find(name) == G->v_list.end())
{
cout << "Vertex not found.";
return 1;
}
int v_index = G->v_list[name].index;
//Удалим эту вершину
G->v_list.erase(name);
//Понизим все индексы которые лежат после этой вершины
for (map <string, vertex> ::iterator it = G->v_list.begin(); it != G->v_list.end(); it++)
{
if (it->second.index >= v_index)
it->second.index--;
}
//Удалим все ребра которые были с ней связаны + понизим индексы остальные
for (map <string, vertex> ::iterator it = G->v_list.begin(); it != G->v_list.end(); it++)
{
for (int i = 0; i < it->second.edge_list.size(); i++)
if (it->second.edge_list[i].first == v_index) //Если это ребро соединялось с вершиной которую мы удалили то удаляем это ребро
{
it->second.edge_list.erase(it->second.edge_list.begin() + i);
i--;
}
else
if (it->second.edge_list[i].first > v_index) // Восстанавливаем нумерацию
it->second.edge_list[i].first--;
}
}
#pragma region Load_Save
bool D_Load(My_graph* G)
{
int rc;
cout << "Enter file name: -->";
//getline(cin, G->fname);
G->fname = "D:\\graph.txt";
if (G->fname == "")
return true;
if (loaded(G))
return true;
else
{
cout << "The appropriate date file is not exists" << endl;
false;
}
}
bool loaded(My_graph* G)
{
std::ifstream fin;
fin.open(G->fname);
G->v_list.clear();
if (fin.is_open())
{
int count, x, y;
fin >> count;
string name;
//Заполняем вершины графа в ассоциативный контейнер map
for (int i = 0; i < count; i++)
{
fin >> name >> x >> y;
vertex t;
t.x = x;
t.y = y;
G->v_list.insert(make_pair(name, t));
}
//Перенумеруем все вершины в графе для удобного поиска в нем
map <string, vertex> ::iterator it = G->v_list.begin();
for (int i = 0; it != G->v_list.end(); it++, i++)
it->second.index = i;
//Считываем ребра графа из файла
fin >> count;
string a, b;
int len;
for (int i = 0; i < count; i++)
{
fin >> a >> b >> len;
add_edge(G, a, b, len);
}
fin.close();
return true;
}
else
return false;
}
int D_Save(My_graph* G)
{
std::ofstream fout;
fout.open(G->fname, ios_base::trunc);
if (fout.is_open())
{
save(fout, G);
fout.close();
}
else
return 0;
return 1;
}
void save(std::ofstream& fout, My_graph* G)
{
int count = G->v_list.size();
fout << count << endl;
int count_edge = 0;
for (map <string, vertex> ::iterator it = G->v_list.begin(); it != G->v_list.end(); it++)
{
fout << it->first << " " << it->second.x << " " << it->second.y << endl;
count_edge += it->second.edge_list.size();
}
count_edge /= 2;
fout << count_edge << endl;
for (map <string, vertex> ::iterator it = G->v_list.begin(); it != G->v_list.end(); it++)
{
int ind_from = it->second.index;
string name_from = it->first;
for (int i = 0; i < it->second.edge_list.size(); i++)
{
int ind_to = it->second.edge_list[i].first;
int len = it->second.edge_list[i].second;
if (ind_from < ind_to)
{
map <string, vertex> ::iterator it_1 = G->v_list.begin();
advance(it_1, ind_to);
fout << name_from << " " << it_1->first << " " << len << endl;
}
}
}
}
#pragma endregion
int main() {
My_graph* G = new My_graph();
int rc, kc;
int (*fptr[])(My_graph*) = { NULL, D_Add_Vertex ,D_Add_Edge ,D_Delete_Vertex,D_Show,NULL,NULL };
if (!D_Load(G))
return 1;
while (rc = dialog())
if (!fptr[rc](G))
break;
kc = D_Save(G);
if (kc == 0)
cout << "Invalid save";
cout << "That all";
return 0;
}