Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ///////////////////////////////////
- // Graph.h //
- ///////////////////////////////////
- #pragma once
- #include <iostream>
- #include <iomanip>
- #include <fstream>
- #include <vector>
- #include <map>
- using namespace std;
- /// <summary>
- /// Граф
- /// </summary>
- /// <typeparam name="Vertice"> тип вершин графа </typeparam>
- /// <typeparam name="Edge"> тип ребер графа (int по умолчанию) </typeparam>
- template <class Vertice, class Edge = int>
- class Graph
- {
- /// <summary>
- /// Количество вершин и ребер в графе
- /// </summary>
- int _N = 0, _M = 0;
- /// <summary>
- /// Критерий ориентированности и взвешенности графа
- /// </summary>
- bool IsDirected = false, IsWeighted = false;
- /// <summary>
- /// Список смежности графа
- /// </summary>
- map <Vertice, map<Vertice, Edge>> graph;
- public:
- /// <summary>
- /// Конструктор по умолчанию
- /// </summary>
- Graph() {};
- /// <summary>
- /// Конструктор, создающий пустой граф, определяющий
- /// ориентированность и взвешенность графа
- /// </summary>
- /// <param name="direction"> критерий ориентированности </param>
- /// <param name="weighting"> критерий взвешенности </param>
- Graph(string direction, string weighting)
- {
- if (direction == "directed") IsDirected = true;
- if (weighting == "weighted") IsWeighted = true;
- }
- /// <summary>
- /// Конструктор, считывающий информацию из файла
- /// или из консоли (stdin)
- /// </summary>
- /// <param name="filePath"> путь к файлу или ключевое слово stdin </param>
- Graph(string filePath)
- {
- ifstream fin;
- if (filePath == "stdin") fin = ifstream(stdin);
- else fin = ifstream(filePath);
- string cmd, direction, weighting;
- fin >> cmd >> direction >> weighting;
- *this = Graph(direction, weighting);
- fin >> cmd >> _N;
- for (int i = 0; i < _N; ++i)
- {
- Vertice v; fin >> v;
- graph.insert(pair<Vertice, map<Vertice, Edge>>(v, map<Vertice, Edge>()));
- }
- fin >> cmd >> _M;
- for (int i = 0; i < _M; ++i)
- {
- Vertice u, v; Edge w; fin >> u >> v;
- if (!IsWeighted) w = 1;
- else fin >> w;
- graph[u].insert(pair<Vertice, Edge>(v, w));
- if (!IsDirected) graph[v].insert(pair<Vertice, Edge>(u, w));
- }
- if (filePath != "stdin") fin.close();
- }
- /// <summary>
- /// Количество вершин графа
- /// </summary>
- /// <returns> количество вершин графа </returns>
- int n() { return _N; }
- /// <summary>
- /// Количество ребер графа
- /// </summary>
- /// <returns> количество ребер графа </returns>
- int m() { return _M; }
- /// <summary>
- /// Метод, выдающий информацию об
- /// ориентированности графа
- /// </summary>
- /// <returns> true, если граф ориентированный, иначе - false </returns>
- bool isDirected() { return IsDirected; }
- /// <summary>
- /// Метод, выдающий информацию о
- /// взвешенности графа
- /// </summary>
- /// <returns> true, если граф взвешенный, иначе - false </returns>
- bool isWeighted() { return IsWeighted; }
- /// <summary>
- /// Метод, возращающий список смежности графа
- /// </summary>
- /// <returns> список смежности графа </returns>
- map<Vertice, map<Vertice, Edge>> edges() { return graph; }
- /// <summary>
- /// Добавление вершины в граф
- /// </summary>
- /// <param name="v"> добавляемая в граф вершина </param>
- void addVertice(Vertice v)
- {
- try
- {
- if (graph.find(v) != graph.end()) throw "Добавление вершины: заданная вершина уже есть в графе";
- else
- {
- ++_N;
- graph.insert(pair<Vertice, map<Vertice, Edge>>(v, map<Vertice, Edge>()));
- }
- }
- catch (const char* msg)
- {
- cout << msg << "\n";
- }
- }
- /// <summary>
- /// Удаление вершины из графа
- /// </summary>
- /// <param name="v"> удаляемая из графа вершина </param>
- void removeVertice(Vertice v)
- {
- try
- {
- if (graph.find(v) == graph.end()) throw "Удаление вершины: в графе отсутствует заданная вершина";
- else
- {
- --_N; _M -= graph[v].size();
- graph.erase(v);
- for (auto p : graph)
- if (graph[p.first].find(v) != graph[p.first].end())
- {
- if (IsDirected) --_M;
- graph[p.first].erase(v);
- }
- }
- }
- catch (const char* msg)
- {
- cout << msg << "\n";
- }
- }
- /// <summary>
- /// Добавление ребра в граф
- /// </summary>
- /// <param name="u"> первая вершина ребра </param>
- /// <param name="v"> вторая вершина ребра </param>
- /// <param name="w"> вес ребра (для невзвешенных графов w = 1) </param>
- void addEdge(Vertice u, Vertice v, Edge w)
- {
- try
- {
- if (graph.find(u) == graph.end() || graph.find(v) == graph.end()) throw "Добавление ребра: в графе отсутствует(ют) заданная(ые) вершина(ы)";
- else if (!IsDirected && u == v) throw "Добавление ребра: невозможно добавить петлю в неориентированный граф";
- else if (graph[u].find(v) != graph[u].end()) throw "Добавление ребра: заданное ребро уже есть в графе";
- else
- {
- ++_M;
- graph[u][v] = w;
- if (!IsDirected) graph[v][u] = w;
- }
- }
- catch (const char* msg)
- {
- cout << msg << "\n";
- }
- }
- /// <summary>
- /// Удаление ребра из графа
- /// </summary>
- /// <param name="u"> первая вершина ребра </param>
- /// <param name="v"> вторая вершина ребра </param>
- void removeEdge(Vertice u, Vertice v)
- {
- try
- {
- if (graph.find(u) == graph.end() || graph.find(v) == graph.end()) throw "Удаление ребра: в графе отсутствует(ют) заданная(ые) вершина(ы)";
- else
- {
- if (graph[u].find(v) == graph[u].end()) throw "Удаление ребра: в графе отсутствует заданное ребро";
- else
- {
- --_M;
- graph[u].erase(v);
- if (!IsDirected) graph[v].erase(u);
- }
- }
- }
- catch (const char* msg)
- {
- cout << msg << "\n";
- }
- }
- /// <summary>
- /// Очищение графа (ориентированность
- /// и взвешенность остаются прежними)
- /// </summary>
- void clear()
- {
- _N = 0; _M = 0;
- graph.clear();
- }
- /// <summary>
- /// Вывод информации о графе в файл или
- /// на консоль (stdout)
- /// </summary>
- /// <param name="filePath"> путь к файлу или ключевое слово stdout </param>
- void print(string filePath)
- {
- ofstream fout;
- if (filePath == "stdout") fout = ofstream(stdout);
- else fout = ofstream(filePath);
- if (filePath != "stdout")
- {
- fout << "GRAPH ";
- if (IsDirected) fout << "directed ";
- else fout << "undirected ";
- if (IsWeighted) fout << "weighted\n";
- else fout << "unweighted\n";
- fout << "VERTICES: " << _N << "\n";
- for (auto p : graph)
- fout << p.first << "\n";
- fout << "EDGES: " << _M << "\n";
- for (auto p1 : graph)
- {
- Vertice u = p1.first;
- for (auto p2 : p1.second)
- {
- Vertice v = p2.first; Edge w = p2.second;
- if (IsDirected || u < v)
- {
- fout << u << " " << v << " ";
- if (IsWeighted) fout << w;
- fout << "\n";
- }
- }
- }
- fout.close();
- }
- else
- {
- fout << "GRAPH ";
- if (IsDirected) fout << "directed ";
- else fout << "undirected ";
- if (IsWeighted) fout << "weighted\n";
- else fout << "unweighted\n";
- fout << "VERTICES: " << _N << "\n";
- for (auto p : graph)
- fout << p.first << "\n";
- fout << "EDGES: " << _M << "\n";
- for (auto p1 : graph)
- {
- Vertice u = p1.first;
- fout << u << ": ";
- for (auto p2 : p1.second)
- {
- Vertice v = p2.first; Edge w = p2.second;
- if (!IsWeighted) fout << v << " ";
- else fout << "(" << v << ", " << w << ") ";
- }
- fout << "\n";
- }
- }
- }
- };
- /// <summary>
- /// Задание 1a: степени вершин в орграфе
- /// </summary>
- /// <typeparam name="Vertice"> тип вершин орграфа </typeparam>
- /// <typeparam name="Edge"> тип дуг орграфа </typeparam>
- /// <param name="g"> граф </param>
- template <class Vertice, class Edge>
- void VerticesDegrees(Graph<Vertice, Edge> g)
- {
- try
- {
- if (!g.isDirected()) throw "Задание 1a: работаем с орграфом";
- else
- {
- map <Vertice, int> in_degree, out_degree;
- map <Vertice, map<Vertice, Edge>> edges = g.edges();
- for (auto p1 : edges)
- {
- Vertice u = p1.first;
- for (auto p2 : p1.second)
- {
- Vertice v = p2.first;
- in_degree[u]++;
- out_degree[v]++;
- }
- }
- cout << "+---------------+-----------+------------+--------+\n";
- cout << "| Вершина | in_degree | out_degree | degree |\n";
- cout << "+---------------+-----------+------------+--------+\n";
- for (auto p : edges)
- {
- Vertice u = p.first;
- int u_in = in_degree[u];
- int u_out = out_degree[u];
- cout << left << "| " << setw(14) << u << "| " << setw(10) << u_in << "| " << setw(11) << u_out << "| " << setw(7) << u_in + u_out << "|\n";
- }
- cout << "+---------------+-----------+------------+--------+\n";
- }
- }
- catch (const char* msg)
- {
- cout << msg << "\n";
- }
- }
- /// <summary>
- /// Задание 1а: поиск вершины, соединенной с u и v
- /// </summary>
- /// <typeparam name="Vertice"> тип вершин орграфа </typeparam>
- /// <typeparam name="Edge"> тип дуг орграфа </typeparam>
- /// <param name="g"> граф </param>
- /// <param name="u"> первая вершина </param>
- /// <param name="v"> вторая вершина </param>
- template <class Vertice, class Edge>
- void FindVertice(Graph<Vertice, Edge> g, Vertice u, Vertice v, bool allow_loop)
- {
- map<Vertice, map<Vertice, Edge>> edges = g.edges();
- try
- {
- if (!g.isDirected()) throw "Задание 1a: работаем с орграфом";
- else if (u == v) throw "Задание 1а: вершины u и v должны быть различны";
- else if (edges.find(u) == edges.end() || edges.find(v) == edges.end()) throw "Задание 1а: в графе отсутствует(ют) заданная(ые) вершина(ы)";
- else
- {
- bool allow_loops = allow_loop;
- vector <Vertice> ans;
- for (auto p : edges[u])
- {
- Vertice x = p.first;
- if ((allow_loops || (x != u && x != v)) && edges[v].find(x) != edges[v].end()) ans.push_back(x);
- }
- if (ans.size())
- {
- cout << "Существуют: ";
- for (int i = 0; i < ans.size(); ++i)
- cout << ans[i] << " ";
- }
- else cout << "НЕ существуют";
- cout << "\n";
- }
- }
- catch (const char* msg)
- {
- cout << msg << "\n";
- }
- }
- /// <summary>
- /// Задание 1b: удаление ребер в графе с одинаковыми степенями
- /// </summary>
- /// <typeparam name="Vertice"> тип вершин графа </typeparam>
- /// <typeparam name="Edge"> тип вершин орграфа </typeparam>
- /// <param name="g"> граф </param>
- template <class Vertice, class Edge>
- void RemoveEdges(Graph<Vertice, Edge> g, string filePath)
- {
- try
- {
- if (g.isDirected()) throw "Задание 1b: работаем с графом";
- else
- {
- map<Vertice, int> degree;
- map <Vertice, map<Vertice, Edge>> edges = g.edges();
- for (auto p1 : edges)
- degree[p1.first] = p1.second.size();
- for (auto p1 : edges)
- {
- Vertice u = p1.first;
- for (auto p2 : p1.second)
- {
- Vertice v = p2.first;
- if (degree[u] == degree[v] && u < v)
- g.removeEdge(u, v);
- }
- }
- g.print(filePath);
- }
- }
- catch (const char* msg)
- {
- cout << msg << "\n";
- }
- }
- //////////////////////////////////////////////
- // ConsoleInterface.h //
- //////////////////////////////////////////////
- #pragma once
- #include "Graph.h"
- #include <vector>
- #include <string>
- /// <summary>
- /// Консольный интерфейс, работающий с одним графом
- /// </summary>
- /// <typeparam name="Vertice"> тип вершин графа </typeparam>
- /// <typeparam name="Edge"> тип ребер графа </typeparam>
- template <class Vertice, class Edge = int>
- class ConsoleInterface
- {
- /// <summary>
- /// Граф
- /// </summary>
- Graph<Vertice, Edge> g;
- /// <summary>
- /// Вывод на консоль списка доступных команд
- /// </summary>
- void Hint()
- {
- cout << "+---------------------------------------+\n";
- cout << "| СПИСОК КОМАНД |\n";
- cout << "+---------------------------------------+\n";
- cout << "| 1. CREATE GRAPH direction weighting |\n";
- cout << "| 2. CREATE GRAPH filePath |\n";
- cout << "| 3. ADD VERTICE v |\n";
- cout << "| 4. REMOVE VERTICE v |\n";
- cout << "| 5. ADD EDGE u v [w] |\n";
- cout << "| 6. REMOVE EDGE u w |\n";
- cout << "| 7. CLEAR GRAPH |\n";
- cout << "| 8. PRINT GRAPH filePath |\n";
- cout << "| 9. TASK 1 |\n";
- cout << "| 10. TASK 2 u v allow_loop |\n";
- cout << "| 11. TASK 3 filePath |\n";
- cout << "| 12. GET HINT |\n";
- cout << "| 13. EXIT |\n";
- cout << "+---------------------------------------+\n";
- }
- public:
- /// <summary>
- /// Конструктор по умолчанию
- /// </summary>
- ConsoleInterface() {};
- /// <summary>
- /// Запуск интерфейса
- /// </summary>
- void Start()
- {
- Hint();
- while (true)
- {
- cout << ">> ";
- string w1; cin >> w1;
- if (w1 == "CREATE")
- {
- string w2, w3; cin >> w2 >> w3;
- if (w3 == "directed" || w3 == "undirected")
- {
- string w4; cin >> w4;
- g = Graph<Vertice, Edge>(w3, w4);
- }
- else g = Graph<Vertice, Edge>(w3);
- }
- else if (w1 == "ADD")
- {
- string w2; cin >> w2;
- if (w2 == "VERTICE")
- {
- Vertice w3; cin >> w3;
- g.addVertice(w3);
- }
- else
- {
- Vertice w3, w4; Edge w5; cin >> w3 >> w4;
- if (!g.isWeighted()) w5 = 1;
- else cin >> w5;
- g.addEdge(w3, w4, w5);
- }
- }
- else if (w1 == "REMOVE")
- {
- string w2; cin >> w2;
- if (w2 == "VERTICE")
- {
- Vertice w3; cin >> w3;
- g.removeVertice(w3);
- }
- else
- {
- Vertice w3, w4; cin >> w3 >> w4;
- g.removeEdge(w3, w4);
- }
- }
- else if (w1 == "CLEAR")
- {
- string w2; cin >> w2;
- g.clear();
- }
- else if (w1 == "PRINT")
- {
- string w2, w3; cin >> w2 >> w3;
- g.print(w3);
- }
- else if (w1 == "TASK")
- {
- int w2; cin >> w2;
- if (w2 == 1) VerticesDegrees(g);
- else if (w2 == 2)
- {
- Vertice u, v; bool b; cin >> u >> v >> b;
- FindVertice(g, u, v, b);
- }
- else if (w2 == 3)
- {
- string w3; cin >> w3; RemoveEdges(g, w3);
- }
- }
- else if (w1 == "GET")
- {
- string w2; cin >> w2;
- Hint();
- }
- else if (w1 == "EXIT")
- {
- break;
- }
- }
- }
- };
- /////////////////////////////////////
- // Graph.cpp //
- /////////////////////////////////////
- #include "ConsoleInterface.h"
- #include <Windows.h>
- int main()
- {
- SetConsoleCP(1251);
- SetConsoleOutputCP(1251);
- ConsoleInterface<string, string> consoleInterface;
- consoleInterface.Start();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement