SHOW:
|
|
- or go back to the newest paste.
| 1 | /////////////////////////////////// | |
| 2 | // Graph.h // | |
| 3 | /////////////////////////////////// | |
| 4 | ||
| 5 | #pragma once | |
| 6 | #include <iostream> | |
| 7 | #include <iomanip> | |
| 8 | #include <fstream> | |
| 9 | #include <vector> | |
| 10 | #include <map> | |
| 11 | using namespace std; | |
| 12 | ||
| 13 | /// <summary> | |
| 14 | /// Граф | |
| 15 | /// </summary> | |
| 16 | /// <typeparam name="Vertice"> тип вершин графа </typeparam> | |
| 17 | /// <typeparam name="Edge"> тип ребер графа (int по умолчанию) </typeparam> | |
| 18 | template <class Vertice, class Edge = int> | |
| 19 | - | /// <summary> |
| 19 | + | |
| 20 | - | /// Количество вершин и ребер в графе |
| 20 | + | |
| 21 | - | /// </summary> |
| 21 | + | /// <summary> |
| 22 | - | int _N = 0, _M = 0; |
| 22 | + | /// Количество вершин и ребер в графе |
| 23 | /// </summary> | |
| 24 | - | /// <summary> |
| 24 | + | int _N = 0, _M = 0; |
| 25 | - | /// Критерий ориентированности и взвешенности графа |
| 25 | + | |
| 26 | - | /// </summary> |
| 26 | + | /// <summary> |
| 27 | - | bool IsDirected = false, IsWeighted = false; |
| 27 | + | /// Критерий ориентированности и взвешенности графа |
| 28 | /// </summary> | |
| 29 | - | /// <summary> |
| 29 | + | bool IsDirected = false, IsWeighted = false; |
| 30 | - | /// Список смежности графа |
| 30 | + | |
| 31 | - | /// </summary> |
| 31 | + | /// <summary> |
| 32 | - | map <Vertice, map<Vertice, Edge>> graph; |
| 32 | + | /// Список смежности графа |
| 33 | /// </summary> | |
| 34 | map <Vertice, map<Vertice, Edge>> graph; | |
| 35 | ||
| 36 | - | /// <summary> |
| 36 | + | |
| 37 | - | /// Конструктор по умолчанию |
| 37 | + | |
| 38 | - | /// </summary> |
| 38 | + | /// <summary> |
| 39 | - | Graph() {};
|
| 39 | + | /// Конструктор по умолчанию |
| 40 | /// </summary> | |
| 41 | - | /// <summary> |
| 41 | + | Graph() {};
|
| 42 | - | /// Конструктор, создающий пустой граф, определяющий |
| 42 | + | |
| 43 | - | /// ориентированность и взвешенность графа |
| 43 | + | /// <summary> |
| 44 | - | /// </summary> |
| 44 | + | /// Конструктор, создающий пустой граф, определяющий |
| 45 | - | /// <param name="direction"> критерий ориентированности </param> |
| 45 | + | /// ориентированность и взвешенность графа |
| 46 | - | /// <param name="weighting"> критерий взвешенности </param> |
| 46 | + | /// </summary> |
| 47 | - | Graph(string direction, string weighting) |
| 47 | + | /// <param name="direction"> критерий ориентированности </param> |
| 48 | - | {
|
| 48 | + | /// <param name="weighting"> критерий взвешенности </param> |
| 49 | - | if (direction == "directed") IsDirected = true; |
| 49 | + | Graph(string direction, string weighting) |
| 50 | - | if (weighting == "weighted") IsWeighted = true; |
| 50 | + | {
|
| 51 | - | } |
| 51 | + | if (direction == "directed") IsDirected = true; |
| 52 | if (weighting == "weighted") IsWeighted = true; | |
| 53 | - | /// <summary> |
| 53 | + | } |
| 54 | - | /// Конструктор, считывающий информацию из файла |
| 54 | + | |
| 55 | - | /// или из консоли (stdin) |
| 55 | + | /// <summary> |
| 56 | - | /// </summary> |
| 56 | + | /// Конструктор, считывающий информацию из файла |
| 57 | - | /// <param name="filePath"> путь к файлу или ключевое слово stdin </param> |
| 57 | + | /// или из консоли (stdin) |
| 58 | - | Graph(string filePath) |
| 58 | + | /// </summary> |
| 59 | - | {
|
| 59 | + | /// <param name="filePath"> путь к файлу или ключевое слово stdin </param> |
| 60 | - | ifstream fin; |
| 60 | + | Graph(string filePath) |
| 61 | {
| |
| 62 | - | if (filePath == "stdin") fin = ifstream(stdin); |
| 62 | + | ifstream fin; |
| 63 | - | else fin = ifstream(filePath); |
| 63 | + | |
| 64 | if (filePath == "stdin") fin = ifstream(stdin); | |
| 65 | - | string cmd, direction, weighting; |
| 65 | + | else fin = ifstream(filePath); |
| 66 | - | fin >> cmd >> direction >> weighting; |
| 66 | + | |
| 67 | string cmd, direction, weighting; | |
| 68 | - | *this = Graph(direction, weighting); |
| 68 | + | fin >> cmd >> direction >> weighting; |
| 69 | ||
| 70 | - | fin >> cmd >> _N; |
| 70 | + | *this = Graph(direction, weighting); |
| 71 | ||
| 72 | - | for (int i = 0; i < _N; ++i) |
| 72 | + | fin >> cmd >> _N; |
| 73 | - | {
|
| 73 | + | |
| 74 | - | Vertice v; fin >> v; |
| 74 | + | for (int i = 0; i < _N; ++i) |
| 75 | - | graph.insert(pair<Vertice, map<Vertice, Edge>>(v, map<Vertice, Edge>())); |
| 75 | + | {
|
| 76 | - | } |
| 76 | + | Vertice v; fin >> v; |
| 77 | graph.insert(pair<Vertice, map<Vertice, Edge>>(v, map<Vertice, Edge>())); | |
| 78 | - | fin >> cmd >> _M; |
| 78 | + | } |
| 79 | ||
| 80 | - | for (int i = 0; i < _M; ++i) |
| 80 | + | fin >> cmd >> _M; |
| 81 | - | {
|
| 81 | + | |
| 82 | - | Vertice u, v; Edge w; fin >> u >> v; |
| 82 | + | for (int i = 0; i < _M; ++i) |
| 83 | {
| |
| 84 | - | if (!IsWeighted) w = 1; |
| 84 | + | Vertice u, v; Edge w; fin >> u >> v; |
| 85 | - | else fin >> w; |
| 85 | + | |
| 86 | if (!IsWeighted) w = 1; | |
| 87 | - | graph[u].insert(pair<Vertice, Edge>(v, w)); |
| 87 | + | else fin >> w; |
| 88 | - | if (!IsDirected) graph[v].insert(pair<Vertice, Edge>(u, w)); |
| 88 | + | |
| 89 | - | } |
| 89 | + | graph[u].insert(pair<Vertice, Edge>(v, w)); |
| 90 | if (!IsDirected) graph[v].insert(pair<Vertice, Edge>(u, w)); | |
| 91 | - | if (filePath != "stdin") fin.close(); |
| 91 | + | } |
| 92 | - | } |
| 92 | + | |
| 93 | if (filePath != "stdin") fin.close(); | |
| 94 | - | /// <summary> |
| 94 | + | } |
| 95 | - | /// Количество вершин графа |
| 95 | + | |
| 96 | - | /// </summary> |
| 96 | + | /// <summary> |
| 97 | - | /// <returns> количество вершин графа </returns> |
| 97 | + | /// Количество вершин графа |
| 98 | - | int n() { return _N; }
|
| 98 | + | /// </summary> |
| 99 | /// <returns> количество вершин графа </returns> | |
| 100 | - | /// <summary> |
| 100 | + | int n() { return _N; }
|
| 101 | - | /// Количество ребер графа |
| 101 | + | |
| 102 | - | /// </summary> |
| 102 | + | /// <summary> |
| 103 | - | /// <returns> количество ребер графа </returns> |
| 103 | + | /// Количество ребер графа |
| 104 | - | int m() { return _M; }
|
| 104 | + | /// </summary> |
| 105 | /// <returns> количество ребер графа </returns> | |
| 106 | - | /// <summary> |
| 106 | + | int m() { return _M; }
|
| 107 | - | /// Метод, выдающий информацию об |
| 107 | + | |
| 108 | - | /// ориентированности графа |
| 108 | + | /// <summary> |
| 109 | - | /// </summary> |
| 109 | + | /// Метод, выдающий информацию об |
| 110 | - | /// <returns> true, если граф ориентированный, иначе - false </returns> |
| 110 | + | /// ориентированности графа |
| 111 | - | bool isDirected() { return IsDirected; }
|
| 111 | + | /// </summary> |
| 112 | /// <returns> true, если граф ориентированный, иначе - false </returns> | |
| 113 | - | /// <summary> |
| 113 | + | bool isDirected() { return IsDirected; }
|
| 114 | - | /// Метод, выдающий информацию о |
| 114 | + | |
| 115 | - | /// взвешенности графа |
| 115 | + | /// <summary> |
| 116 | - | /// </summary> |
| 116 | + | /// Метод, выдающий информацию о |
| 117 | - | /// <returns> true, если граф взвешенный, иначе - false </returns> |
| 117 | + | /// взвешенности графа |
| 118 | - | bool isWeighted() { return IsWeighted; }
|
| 118 | + | /// </summary> |
| 119 | /// <returns> true, если граф взвешенный, иначе - false </returns> | |
| 120 | - | /// <summary> |
| 120 | + | bool isWeighted() { return IsWeighted; }
|
| 121 | - | /// Добавление вершины в граф |
| 121 | + | |
| 122 | - | /// </summary> |
| 122 | + | /// <summary> |
| 123 | - | /// <param name="v"> добавляемая в граф вершина </param> |
| 123 | + | /// Метод, возращающий список смежности графа |
| 124 | - | void addVertice(Vertice v) |
| 124 | + | /// </summary> |
| 125 | - | {
|
| 125 | + | /// <returns> список смежности графа </returns> |
| 126 | - | try |
| 126 | + | map<Vertice, map<Vertice, Edge>> edges() { return graph; }
|
| 127 | - | {
|
| 127 | + | |
| 128 | - | if (graph.find(v) != graph.end()) throw "Добавление вершины: заданная вершина уже есть в графе"; |
| 128 | + | /// <summary> |
| 129 | - | else |
| 129 | + | /// Добавление вершины в граф |
| 130 | - | {
|
| 130 | + | /// </summary> |
| 131 | - | ++_N; |
| 131 | + | /// <param name="v"> добавляемая в граф вершина </param> |
| 132 | - | graph.insert(pair<Vertice, map<Vertice, Edge>>(v, map<Vertice, Edge>())); |
| 132 | + | void addVertice(Vertice v) |
| 133 | - | } |
| 133 | + | {
|
| 134 | - | } |
| 134 | + | try |
| 135 | - | catch (const char* msg) |
| 135 | + | {
|
| 136 | - | {
|
| 136 | + | if (graph.find(v) != graph.end()) throw "Добавление вершины: заданная вершина уже есть в графе"; |
| 137 | - | cout << msg << "\n"; |
| 137 | + | else |
| 138 | - | } |
| 138 | + | {
|
| 139 | - | } |
| 139 | + | ++_N; |
| 140 | graph.insert(pair<Vertice, map<Vertice, Edge>>(v, map<Vertice, Edge>())); | |
| 141 | - | /// <summary> |
| 141 | + | } |
| 142 | - | /// Удаление вершины из графа |
| 142 | + | } |
| 143 | - | /// </summary> |
| 143 | + | catch (const char* msg) |
| 144 | - | /// <param name="v"> удаляемая из графа вершина </param> |
| 144 | + | {
|
| 145 | - | void removeVertice(Vertice v) |
| 145 | + | cout << msg << "\n"; |
| 146 | - | {
|
| 146 | + | } |
| 147 | - | try |
| 147 | + | } |
| 148 | - | {
|
| 148 | + | |
| 149 | - | if (graph.find(v) == graph.end()) throw "Удаление вершины: в графе отсутствует заданная вершина"; |
| 149 | + | /// <summary> |
| 150 | - | else |
| 150 | + | /// Удаление вершины из графа |
| 151 | - | {
|
| 151 | + | /// </summary> |
| 152 | - | --_N; _M -= graph[v].size(); |
| 152 | + | /// <param name="v"> удаляемая из графа вершина </param> |
| 153 | void removeVertice(Vertice v) | |
| 154 | - | graph.erase(v); |
| 154 | + | {
|
| 155 | try | |
| 156 | - | for (auto p : graph) |
| 156 | + | {
|
| 157 | - | if (graph[p.first].find(v) != graph[p.first].end()) |
| 157 | + | if (graph.find(v) == graph.end()) throw "Удаление вершины: в графе отсутствует заданная вершина"; |
| 158 | - | {
|
| 158 | + | else |
| 159 | - | if (IsDirected) --_M; |
| 159 | + | {
|
| 160 | - | graph[p.first].erase(v); |
| 160 | + | --_N; _M -= graph[v].size(); |
| 161 | - | } |
| 161 | + | |
| 162 | - | } |
| 162 | + | graph.erase(v); |
| 163 | - | } |
| 163 | + | |
| 164 | - | catch (const char* msg) |
| 164 | + | for (auto p : graph) |
| 165 | - | {
|
| 165 | + | if (graph[p.first].find(v) != graph[p.first].end()) |
| 166 | - | cout << msg << "\n"; |
| 166 | + | {
|
| 167 | - | } |
| 167 | + | if (IsDirected) --_M; |
| 168 | - | } |
| 168 | + | graph[p.first].erase(v); |
| 169 | } | |
| 170 | - | /// <summary> |
| 170 | + | } |
| 171 | - | /// Добавление ребра в граф |
| 171 | + | } |
| 172 | - | /// </summary> |
| 172 | + | catch (const char* msg) |
| 173 | - | /// <param name="u"> первая вершина ребра </param> |
| 173 | + | {
|
| 174 | - | /// <param name="v"> вторая вершина ребра </param> |
| 174 | + | cout << msg << "\n"; |
| 175 | - | /// <param name="w"> вес ребра (для невзвешенных графов w = 1) </param> |
| 175 | + | } |
| 176 | - | void addEdge(Vertice u, Vertice v, Edge w) |
| 176 | + | } |
| 177 | - | {
|
| 177 | + | |
| 178 | - | try |
| 178 | + | /// <summary> |
| 179 | - | {
|
| 179 | + | /// Добавление ребра в граф |
| 180 | - | if (graph.find(u) == graph.end() || graph.find(v) == graph.end()) throw "Добавление ребра: в графе отсутствует(ют) заданная(ые) вершина(ы)"; |
| 180 | + | /// </summary> |
| 181 | - | else if (!IsDirected && u == v) throw "Добавление ребра: невозможно добавить петлю в неориентированный граф"; |
| 181 | + | /// <param name="u"> первая вершина ребра </param> |
| 182 | - | else if (graph[u].find(v) != graph[u].end()) throw "Добавление ребра: заданное ребро уже есть в графе"; |
| 182 | + | /// <param name="v"> вторая вершина ребра </param> |
| 183 | - | else |
| 183 | + | /// <param name="w"> вес ребра (для невзвешенных графов w = 1) </param> |
| 184 | - | {
|
| 184 | + | void addEdge(Vertice u, Vertice v, Edge w) |
| 185 | - | ++_M; |
| 185 | + | {
|
| 186 | - | graph[u][v] = w; |
| 186 | + | try |
| 187 | - | if (!IsDirected) graph[v][u] = w; |
| 187 | + | {
|
| 188 | - | } |
| 188 | + | if (graph.find(u) == graph.end() || graph.find(v) == graph.end()) throw "Добавление ребра: в графе отсутствует(ют) заданная(ые) вершина(ы)"; |
| 189 | - | } |
| 189 | + | else if (!IsDirected && u == v) throw "Добавление ребра: невозможно добавить петлю в неориентированный граф"; |
| 190 | - | catch (const char* msg) |
| 190 | + | else if (graph[u].find(v) != graph[u].end()) throw "Добавление ребра: заданное ребро уже есть в графе"; |
| 191 | - | {
|
| 191 | + | else |
| 192 | - | cout << msg << "\n"; |
| 192 | + | {
|
| 193 | - | } |
| 193 | + | ++_M; |
| 194 | - | } |
| 194 | + | graph[u][v] = w; |
| 195 | if (!IsDirected) graph[v][u] = w; | |
| 196 | - | /// <summary> |
| 196 | + | } |
| 197 | - | /// Удаление ребра из графа |
| 197 | + | } |
| 198 | - | /// </summary> |
| 198 | + | catch (const char* msg) |
| 199 | - | /// <param name="u"> первая вершина ребра </param> |
| 199 | + | {
|
| 200 | - | /// <param name="v"> вторая вершина ребра </param> |
| 200 | + | cout << msg << "\n"; |
| 201 | - | void removeEdge(Vertice u, Vertice v) |
| 201 | + | } |
| 202 | - | {
|
| 202 | + | } |
| 203 | - | try |
| 203 | + | |
| 204 | - | {
|
| 204 | + | /// <summary> |
| 205 | - | if (graph.find(u) == graph.end() || graph.find(v) == graph.end()) throw "Удаление ребра: в графе отсутствует(ют) заданная(ые) вершина(ы)"; |
| 205 | + | /// Удаление ребра из графа |
| 206 | - | else |
| 206 | + | /// </summary> |
| 207 | - | {
|
| 207 | + | /// <param name="u"> первая вершина ребра </param> |
| 208 | - | if (graph[u].find(v) == graph[u].end()) throw "Удаление ребра: в графе отсутствует заданное ребро"; |
| 208 | + | /// <param name="v"> вторая вершина ребра </param> |
| 209 | - | else |
| 209 | + | void removeEdge(Vertice u, Vertice v) |
| 210 | - | {
|
| 210 | + | {
|
| 211 | - | --_M; |
| 211 | + | try |
| 212 | - | graph[u].erase(v); |
| 212 | + | {
|
| 213 | - | if (!IsDirected) graph[v].erase(u); |
| 213 | + | if (graph.find(u) == graph.end() || graph.find(v) == graph.end()) throw "Удаление ребра: в графе отсутствует(ют) заданная(ые) вершина(ы)"; |
| 214 | - | } |
| 214 | + | else |
| 215 | - | } |
| 215 | + | {
|
| 216 | - | } |
| 216 | + | if (graph[u].find(v) == graph[u].end()) throw "Удаление ребра: в графе отсутствует заданное ребро"; |
| 217 | - | catch (const char* msg) |
| 217 | + | else |
| 218 | - | {
|
| 218 | + | {
|
| 219 | - | cout << msg << "\n"; |
| 219 | + | --_M; |
| 220 | - | } |
| 220 | + | graph[u].erase(v); |
| 221 | - | } |
| 221 | + | if (!IsDirected) graph[v].erase(u); |
| 222 | } | |
| 223 | - | /// <summary> |
| 223 | + | } |
| 224 | - | /// Очищение графа (ориентированность |
| 224 | + | } |
| 225 | - | /// и взвешенность остаются прежними) |
| 225 | + | catch (const char* msg) |
| 226 | - | /// </summary> |
| 226 | + | {
|
| 227 | - | void clear() |
| 227 | + | cout << msg << "\n"; |
| 228 | - | {
|
| 228 | + | } |
| 229 | - | _N = 0; _M = 0; |
| 229 | + | } |
| 230 | - | graph.clear(); |
| 230 | + | |
| 231 | - | } |
| 231 | + | /// <summary> |
| 232 | /// Очищение графа (ориентированность | |
| 233 | - | /// <summary> |
| 233 | + | /// и взвешенность остаются прежними) |
| 234 | - | /// Вывод информации о графе в файл или |
| 234 | + | /// </summary> |
| 235 | - | /// на консоль (stdout) |
| 235 | + | void clear() |
| 236 | - | /// </summary> |
| 236 | + | {
|
| 237 | - | /// <param name="filePath"> путь к файлу или ключевое слово stdout </param> |
| 237 | + | _N = 0; _M = 0; |
| 238 | - | void print(string filePath) |
| 238 | + | graph.clear(); |
| 239 | - | {
|
| 239 | + | } |
| 240 | - | ofstream fout; |
| 240 | + | |
| 241 | /// <summary> | |
| 242 | - | if (filePath == "stdout") fout = ofstream(stdout); |
| 242 | + | /// Вывод информации о графе в файл или |
| 243 | - | else fout = ofstream(filePath); |
| 243 | + | /// на консоль (stdout) |
| 244 | /// </summary> | |
| 245 | - | if (filePath != "stdout") |
| 245 | + | /// <param name="filePath"> путь к файлу или ключевое слово stdout </param> |
| 246 | - | {
|
| 246 | + | void print(string filePath) |
| 247 | - | fout << "GRAPH "; |
| 247 | + | {
|
| 248 | ofstream fout; | |
| 249 | - | if (IsDirected) fout << "directed "; |
| 249 | + | |
| 250 | - | else fout << "undirected "; |
| 250 | + | if (filePath == "stdout") fout = ofstream(stdout); |
| 251 | else fout = ofstream(filePath); | |
| 252 | - | if (IsWeighted) fout << "weighted\n"; |
| 252 | + | |
| 253 | - | else fout << "unweighted\n"; |
| 253 | + | if (filePath != "stdout") |
| 254 | {
| |
| 255 | - | fout << "VERTICES: " << _N << "\n"; |
| 255 | + | fout << "GRAPH "; |
| 256 | ||
| 257 | - | for (auto p : graph) |
| 257 | + | if (IsDirected) fout << "directed "; |
| 258 | - | fout << p.first << "\n"; |
| 258 | + | else fout << "undirected "; |
| 259 | ||
| 260 | - | fout << "EDGES: " << _M << "\n"; |
| 260 | + | if (IsWeighted) fout << "weighted\n"; |
| 261 | else fout << "unweighted\n"; | |
| 262 | - | for (auto p1 : graph) |
| 262 | + | |
| 263 | - | {
|
| 263 | + | fout << "VERTICES: " << _N << "\n"; |
| 264 | - | Vertice u = p1.first; |
| 264 | + | |
| 265 | for (auto p : graph) | |
| 266 | - | for (auto p2 : p1.second) |
| 266 | + | fout << p.first << "\n"; |
| 267 | - | {
|
| 267 | + | |
| 268 | - | Vertice v = p2.first; Edge w = p2.second; |
| 268 | + | fout << "EDGES: " << _M << "\n"; |
| 269 | ||
| 270 | - | if (IsDirected || u < v) |
| 270 | + | for (auto p1 : graph) |
| 271 | - | {
|
| 271 | + | {
|
| 272 | - | fout << u << " " << v << " "; |
| 272 | + | Vertice u = p1.first; |
| 273 | - | if (IsWeighted) fout << w; |
| 273 | + | |
| 274 | - | fout << "\n"; |
| 274 | + | for (auto p2 : p1.second) |
| 275 | - | } |
| 275 | + | {
|
| 276 | - | } |
| 276 | + | Vertice v = p2.first; Edge w = p2.second; |
| 277 | - | } |
| 277 | + | |
| 278 | if (IsDirected || u < v) | |
| 279 | - | fout.close(); |
| 279 | + | {
|
| 280 | - | } |
| 280 | + | fout << u << " " << v << " "; |
| 281 | - | else |
| 281 | + | if (IsWeighted) fout << w; |
| 282 | - | {
|
| 282 | + | fout << "\n"; |
| 283 | - | fout << "GRAPH "; |
| 283 | + | } |
| 284 | } | |
| 285 | - | if (IsDirected) fout << "directed "; |
| 285 | + | } |
| 286 | - | else fout << "undirected "; |
| 286 | + | |
| 287 | fout.close(); | |
| 288 | - | if (IsWeighted) fout << "weighted\n"; |
| 288 | + | } |
| 289 | - | else fout << "unweighted\n"; |
| 289 | + | else |
| 290 | {
| |
| 291 | - | fout << "VERTICES: " << _N << "\n"; |
| 291 | + | fout << "GRAPH "; |
| 292 | ||
| 293 | - | for (auto p : graph) |
| 293 | + | if (IsDirected) fout << "directed "; |
| 294 | - | fout << p.first << "\n"; |
| 294 | + | else fout << "undirected "; |
| 295 | ||
| 296 | - | fout << "EDGES: " << _M << "\n"; |
| 296 | + | if (IsWeighted) fout << "weighted\n"; |
| 297 | else fout << "unweighted\n"; | |
| 298 | - | for (auto p1 : graph) |
| 298 | + | |
| 299 | - | {
|
| 299 | + | fout << "VERTICES: " << _N << "\n"; |
| 300 | - | Vertice u = p1.first; |
| 300 | + | |
| 301 | for (auto p : graph) | |
| 302 | - | fout << u << ": "; |
| 302 | + | fout << p.first << "\n"; |
| 303 | ||
| 304 | - | for (auto p2 : p1.second) |
| 304 | + | fout << "EDGES: " << _M << "\n"; |
| 305 | - | {
|
| 305 | + | |
| 306 | - | Vertice v = p2.first; Edge w = p2.second; |
| 306 | + | for (auto p1 : graph) |
| 307 | {
| |
| 308 | - | if (!IsWeighted) fout << v << " "; |
| 308 | + | Vertice u = p1.first; |
| 309 | - | else fout << "(" << v << ", " << w << ") ";
|
| 309 | + | |
| 310 | - | } |
| 310 | + | fout << u << ": "; |
| 311 | ||
| 312 | - | fout << "\n"; |
| 312 | + | for (auto p2 : p1.second) |
| 313 | - | } |
| 313 | + | {
|
| 314 | - | } |
| 314 | + | Vertice v = p2.first; Edge w = p2.second; |
| 315 | - | } |
| 315 | + | |
| 316 | if (!IsWeighted) fout << v << " "; | |
| 317 | else fout << "(" << v << ", " << w << ") ";
| |
| 318 | } | |
| 319 | ||
| 320 | fout << "\n"; | |
| 321 | } | |
| 322 | } | |
| 323 | } | |
| 324 | }; | |
| 325 | ||
| 326 | /// <summary> | |
| 327 | /// Задание 1a: степени вершин в орграфе | |
| 328 | /// </summary> | |
| 329 | /// <typeparam name="Vertice"> тип вершин орграфа </typeparam> | |
| 330 | /// <typeparam name="Edge"> тип дуг орграфа </typeparam> | |
| 331 | /// <param name="g"> граф </param> | |
| 332 | template <class Vertice, class Edge> | |
| 333 | void VerticesDegrees(Graph<Vertice, Edge> g) | |
| 334 | {
| |
| 335 | - | /// <summary> |
| 335 | + | try |
| 336 | - | /// Граф |
| 336 | + | {
|
| 337 | - | /// </summary> |
| 337 | + | if (!g.isDirected()) throw "Задание 1a: работаем с орграфом"; |
| 338 | - | Graph<Vertice, Edge> g; |
| 338 | + | else |
| 339 | {
| |
| 340 | - | /// <summary> |
| 340 | + | map <Vertice, int> in_degree, out_degree; |
| 341 | - | /// Вывод на консоль списка доступных команд |
| 341 | + | map <Vertice, map<Vertice, Edge>> edges = g.edges(); |
| 342 | - | /// </summary> |
| 342 | + | |
| 343 | - | void Hint() |
| 343 | + | for (auto p1 : edges) |
| 344 | - | {
|
| 344 | + | {
|
| 345 | - | cout << "+---------------------------------------+\n"; |
| 345 | + | Vertice u = p1.first; |
| 346 | - | cout << "| СПИСОК КОМАНД |\n"; |
| 346 | + | |
| 347 | - | cout << "+---------------------------------------+\n"; |
| 347 | + | for (auto p2 : p1.second) |
| 348 | - | cout << "| 1. CREATE GRAPH direction weighting |\n"; |
| 348 | + | {
|
| 349 | - | cout << "| 2. CREATE GRAPH filePath |\n"; |
| 349 | + | Vertice v = p2.first; |
| 350 | - | cout << "| 3. ADD VERTICE v |\n"; |
| 350 | + | |
| 351 | - | cout << "| 4. REMOVE VERTICE v |\n"; |
| 351 | + | in_degree[u]++; |
| 352 | - | cout << "| 5. ADD EDGE u v [w] |\n"; |
| 352 | + | out_degree[v]++; |
| 353 | - | cout << "| 6. REMOVE EDGE u w |\n"; |
| 353 | + | } |
| 354 | - | cout << "| 7. CLEAR GRAPH |\n"; |
| 354 | + | } |
| 355 | - | cout << "| 8. PRINT GRAPH filePath |\n"; |
| 355 | + | |
| 356 | - | cout << "| 9. GET HINT |\n"; |
| 356 | + | cout << "+---------------+-----------+------------+--------+\n"; |
| 357 | - | cout << "| 10. EXIT |\n"; |
| 357 | + | cout << "| Вершина | in_degree | out_degree | degree |\n"; |
| 358 | - | cout << "+---------------------------------------+\n"; |
| 358 | + | cout << "+---------------+-----------+------------+--------+\n"; |
| 359 | - | } |
| 359 | + | |
| 360 | for (auto p : edges) | |
| 361 | {
| |
| 362 | Vertice u = p.first; | |
| 363 | - | /// <summary> |
| 363 | + | |
| 364 | - | /// Конструктор по умолчанию |
| 364 | + | int u_in = in_degree[u]; |
| 365 | - | /// </summary> |
| 365 | + | int u_out = out_degree[u]; |
| 366 | - | ConsoleInterface() {};
|
| 366 | + | |
| 367 | cout << left << "| " << setw(14) << u << "| " << setw(10) << u_in << "| " << setw(11) << u_out << "| " << setw(7) << u_in + u_out << "|\n"; | |
| 368 | - | /// <summary> |
| 368 | + | } |
| 369 | - | /// Запуск интерфейса |
| 369 | + | |
| 370 | - | /// </summary> |
| 370 | + | cout << "+---------------+-----------+------------+--------+\n"; |
| 371 | - | void Start() |
| 371 | + | } |
| 372 | - | {
|
| 372 | + | } |
| 373 | - | Hint(); |
| 373 | + | catch (const char* msg) |
| 374 | {
| |
| 375 | - | while (true) |
| 375 | + | cout << msg << "\n"; |
| 376 | - | {
|
| 376 | + | } |
| 377 | - | cout << ">> "; |
| 377 | + | } |
| 378 | ||
| 379 | - | string w1; cin >> w1; |
| 379 | + | |
| 380 | /// Задание 1а: поиск вершины, соединенной с u и v | |
| 381 | - | if (w1 == "CREATE") |
| 381 | + | |
| 382 | - | {
|
| 382 | + | /// <typeparam name="Vertice"> тип вершин орграфа </typeparam> |
| 383 | - | string w2, w3; cin >> w2 >> w3; |
| 383 | + | /// <typeparam name="Edge"> тип дуг орграфа </typeparam> |
| 384 | /// <param name="g"> граф </param> | |
| 385 | - | if (w3 == "directed" || w3 == "undirected") |
| 385 | + | /// <param name="u"> первая вершина </param> |
| 386 | - | {
|
| 386 | + | /// <param name="v"> вторая вершина </param> |
| 387 | - | string w4; cin >> w4; |
| 387 | + | template <class Vertice, class Edge> |
| 388 | - | g = Graph<Vertice, Edge>(w3, w4); |
| 388 | + | void FindVertice(Graph<Vertice, Edge> g, Vertice u, Vertice v, bool allow_loop) |
| 389 | - | } |
| 389 | + | |
| 390 | - | else g = Graph<Vertice, Edge>(w3); |
| 390 | + | map<Vertice, map<Vertice, Edge>> edges = g.edges(); |
| 391 | - | } |
| 391 | + | |
| 392 | - | else if (w1 == "ADD") |
| 392 | + | try |
| 393 | - | {
|
| 393 | + | {
|
| 394 | - | string w2; cin >> w2; |
| 394 | + | if (!g.isDirected()) throw "Задание 1a: работаем с орграфом"; |
| 395 | else if (u == v) throw "Задание 1а: вершины u и v должны быть различны"; | |
| 396 | - | if (w2 == "VERTICE") |
| 396 | + | else if (edges.find(u) == edges.end() || edges.find(v) == edges.end()) throw "Задание 1а: в графе отсутствует(ют) заданная(ые) вершина(ы)"; |
| 397 | - | {
|
| 397 | + | else |
| 398 | - | Vertice w3; cin >> w3; |
| 398 | + | {
|
| 399 | - | g.addVertice(w3); |
| 399 | + | bool allow_loops = allow_loop; |
| 400 | - | } |
| 400 | + | vector <Vertice> ans; |
| 401 | - | else |
| 401 | + | |
| 402 | - | {
|
| 402 | + | for (auto p : edges[u]) |
| 403 | - | Vertice w3, w4; Edge w5; cin >> w3 >> w4; |
| 403 | + | {
|
| 404 | Vertice x = p.first; | |
| 405 | - | if (!g.isWeighted()) w5 = 1; |
| 405 | + | if ((allow_loops || (x != u && x != v)) && edges[v].find(x) != edges[v].end()) ans.push_back(x); |
| 406 | - | else cin >> w5; |
| 406 | + | } |
| 407 | ||
| 408 | - | g.addEdge(w3, w4, w5); |
| 408 | + | if (ans.size()) |
| 409 | - | } |
| 409 | + | {
|
| 410 | - | } |
| 410 | + | cout << "Существуют: "; |
| 411 | - | else if (w1 == "REMOVE") |
| 411 | + | |
| 412 | - | {
|
| 412 | + | for (int i = 0; i < ans.size(); ++i) |
| 413 | - | string w2; cin >> w2; |
| 413 | + | cout << ans[i] << " "; |
| 414 | } | |
| 415 | - | if (w2 == "VERTICE") |
| 415 | + | else cout << "НЕ существуют"; |
| 416 | - | {
|
| 416 | + | |
| 417 | - | Vertice w3; cin >> w3; |
| 417 | + | cout << "\n"; |
| 418 | - | g.removeVertice(w3); |
| 418 | + | } |
| 419 | - | } |
| 419 | + | } |
| 420 | - | else |
| 420 | + | catch (const char* msg) |
| 421 | - | {
|
| 421 | + | {
|
| 422 | - | Vertice w3, w4; cin >> w3 >> w4; |
| 422 | + | cout << msg << "\n"; |
| 423 | - | g.removeEdge(w3, w4); |
| 423 | + | } |
| 424 | - | } |
| 424 | + | } |
| 425 | - | } |
| 425 | + | |
| 426 | - | else if (w1 == "CLEAR") |
| 426 | + | |
| 427 | - | {
|
| 427 | + | /// Задание 1b: удаление ребер в графе с одинаковыми степенями |
| 428 | - | string w2; cin >> w2; |
| 428 | + | |
| 429 | - | g.clear(); |
| 429 | + | |
| 430 | - | } |
| 430 | + | /// <typeparam name="Edge"> тип вершин орграфа </typeparam> |
| 431 | - | else if (w1 == "PRINT") |
| 431 | + | /// <param name="g"> граф </param> |
| 432 | - | {
|
| 432 | + | template <class Vertice, class Edge> |
| 433 | - | string w2, w3; cin >> w2 >> w3; |
| 433 | + | void RemoveEdges(Graph<Vertice, Edge> g, string filePath) |
| 434 | - | g.print(w3); |
| 434 | + | |
| 435 | - | } |
| 435 | + | try |
| 436 | - | else if (w1 == "GET") |
| 436 | + | {
|
| 437 | - | {
|
| 437 | + | if (g.isDirected()) throw "Задание 1b: работаем с графом"; |
| 438 | - | string w2; cin >> w2; |
| 438 | + | else |
| 439 | - | Hint(); |
| 439 | + | {
|
| 440 | - | } |
| 440 | + | map<Vertice, int> degree; |
| 441 | - | else if (w1 == "EXIT") |
| 441 | + | map <Vertice, map<Vertice, Edge>> edges = g.edges(); |
| 442 | - | {
|
| 442 | + | |
| 443 | - | break; |
| 443 | + | for (auto p1 : edges) |
| 444 | - | } |
| 444 | + | degree[p1.first] = p1.second.size(); |
| 445 | - | } |
| 445 | + | |
| 446 | - | } |
| 446 | + | for (auto p1 : edges) |
| 447 | {
| |
| 448 | Vertice u = p1.first; | |
| 449 | ||
| 450 | for (auto p2 : p1.second) | |
| 451 | {
| |
| 452 | Vertice v = p2.first; | |
| 453 | if (degree[u] == degree[v] && u < v) | |
| 454 | g.removeEdge(u, v); | |
| 455 | } | |
| 456 | } | |
| 457 | ||
| 458 | g.print(filePath); | |
| 459 | } | |
| 460 | } | |
| 461 | catch (const char* msg) | |
| 462 | {
| |
| 463 | cout << msg << "\n"; | |
| 464 | } | |
| 465 | } | |
| 466 | ||
| 467 | ////////////////////////////////////////////// | |
| 468 | // ConsoleInterface.h // | |
| 469 | ////////////////////////////////////////////// | |
| 470 | ||
| 471 | #pragma once | |
| 472 | #include "Graph.h" | |
| 473 | #include <vector> | |
| 474 | #include <string> | |
| 475 | ||
| 476 | /// <summary> | |
| 477 | /// Консольный интерфейс, работающий с одним графом | |
| 478 | /// </summary> | |
| 479 | /// <typeparam name="Vertice"> тип вершин графа </typeparam> | |
| 480 | /// <typeparam name="Edge"> тип ребер графа </typeparam> | |
| 481 | template <class Vertice, class Edge = int> | |
| 482 | class ConsoleInterface | |
| 483 | {
| |
| 484 | /// <summary> | |
| 485 | /// Граф | |
| 486 | /// </summary> | |
| 487 | Graph<Vertice, Edge> g; | |
| 488 | ||
| 489 | /// <summary> | |
| 490 | /// Вывод на консоль списка доступных команд | |
| 491 | /// </summary> | |
| 492 | void Hint() | |
| 493 | {
| |
| 494 | cout << "+---------------------------------------+\n"; | |
| 495 | cout << "| СПИСОК КОМАНД |\n"; | |
| 496 | cout << "+---------------------------------------+\n"; | |
| 497 | cout << "| 1. CREATE GRAPH direction weighting |\n"; | |
| 498 | cout << "| 2. CREATE GRAPH filePath |\n"; | |
| 499 | cout << "| 3. ADD VERTICE v |\n"; | |
| 500 | cout << "| 4. REMOVE VERTICE v |\n"; | |
| 501 | cout << "| 5. ADD EDGE u v [w] |\n"; | |
| 502 | cout << "| 6. REMOVE EDGE u w |\n"; | |
| 503 | cout << "| 7. CLEAR GRAPH |\n"; | |
| 504 | cout << "| 8. PRINT GRAPH filePath |\n"; | |
| 505 | cout << "| 9. TASK 1 |\n"; | |
| 506 | cout << "| 10. TASK 2 u v allow_loop |\n"; | |
| 507 | cout << "| 11. TASK 3 filePath |\n"; | |
| 508 | cout << "| 12. GET HINT |\n"; | |
| 509 | cout << "| 13. EXIT |\n"; | |
| 510 | cout << "+---------------------------------------+\n"; | |
| 511 | } | |
| 512 | ||
| 513 | public: | |
| 514 | ||
| 515 | /// <summary> | |
| 516 | /// Конструктор по умолчанию | |
| 517 | /// </summary> | |
| 518 | ConsoleInterface() {};
| |
| 519 | ||
| 520 | /// <summary> | |
| 521 | /// Запуск интерфейса | |
| 522 | /// </summary> | |
| 523 | void Start() | |
| 524 | {
| |
| 525 | Hint(); | |
| 526 | ||
| 527 | while (true) | |
| 528 | {
| |
| 529 | cout << ">> "; | |
| 530 | ||
| 531 | string w1; cin >> w1; | |
| 532 | ||
| 533 | if (w1 == "CREATE") | |
| 534 | {
| |
| 535 | string w2, w3; cin >> w2 >> w3; | |
| 536 | ||
| 537 | if (w3 == "directed" || w3 == "undirected") | |
| 538 | {
| |
| 539 | string w4; cin >> w4; | |
| 540 | g = Graph<Vertice, Edge>(w3, w4); | |
| 541 | } | |
| 542 | else g = Graph<Vertice, Edge>(w3); | |
| 543 | } | |
| 544 | else if (w1 == "ADD") | |
| 545 | {
| |
| 546 | string w2; cin >> w2; | |
| 547 | ||
| 548 | if (w2 == "VERTICE") | |
| 549 | {
| |
| 550 | Vertice w3; cin >> w3; | |
| 551 | g.addVertice(w3); | |
| 552 | } | |
| 553 | else | |
| 554 | {
| |
| 555 | Vertice w3, w4; Edge w5; cin >> w3 >> w4; | |
| 556 | ||
| 557 | if (!g.isWeighted()) w5 = 1; | |
| 558 | else cin >> w5; | |
| 559 | ||
| 560 | g.addEdge(w3, w4, w5); | |
| 561 | } | |
| 562 | } | |
| 563 | else if (w1 == "REMOVE") | |
| 564 | {
| |
| 565 | string w2; cin >> w2; | |
| 566 | ||
| 567 | if (w2 == "VERTICE") | |
| 568 | {
| |
| 569 | Vertice w3; cin >> w3; | |
| 570 | g.removeVertice(w3); | |
| 571 | } | |
| 572 | else | |
| 573 | {
| |
| 574 | Vertice w3, w4; cin >> w3 >> w4; | |
| 575 | g.removeEdge(w3, w4); | |
| 576 | } | |
| 577 | } | |
| 578 | else if (w1 == "CLEAR") | |
| 579 | {
| |
| 580 | string w2; cin >> w2; | |
| 581 | g.clear(); | |
| 582 | } | |
| 583 | else if (w1 == "PRINT") | |
| 584 | {
| |
| 585 | string w2, w3; cin >> w2 >> w3; | |
| 586 | g.print(w3); | |
| 587 | } | |
| 588 | else if (w1 == "TASK") | |
| 589 | {
| |
| 590 | int w2; cin >> w2; | |
| 591 | ||
| 592 | if (w2 == 1) VerticesDegrees(g); | |
| 593 | else if (w2 == 2) | |
| 594 | {
| |
| 595 | Vertice u, v; bool b; cin >> u >> v >> b; | |
| 596 | FindVertice(g, u, v, b); | |
| 597 | } | |
| 598 | else if (w2 == 3) | |
| 599 | {
| |
| 600 | string w3; cin >> w3; RemoveEdges(g, w3); | |
| 601 | } | |
| 602 | } | |
| 603 | else if (w1 == "GET") | |
| 604 | {
| |
| 605 | string w2; cin >> w2; | |
| 606 | Hint(); | |
| 607 | } | |
| 608 | else if (w1 == "EXIT") | |
| 609 | {
| |
| 610 | break; | |
| 611 | } | |
| 612 | } | |
| 613 | } | |
| 614 | }; | |
| 615 | ||
| 616 | ///////////////////////////////////// | |
| 617 | // Graph.cpp // | |
| 618 | ///////////////////////////////////// | |
| 619 | ||
| 620 | #include "ConsoleInterface.h" | |
| 621 | #include <Windows.h> | |
| 622 | ||
| 623 | int main() | |
| 624 | {
| |
| 625 | SetConsoleCP(1251); | |
| 626 | SetConsoleOutputCP(1251); | |
| 627 | ||
| 628 | ConsoleInterface<string, string> consoleInterface; | |
| 629 | consoleInterface.Start(); | |
| 630 | ||
| 631 | return 0; | |
| 632 | } |