367 lines
13 KiB
Dart
367 lines
13 KiB
Dart
import 'src/graph.dart';
|
||
import 'dart:convert';
|
||
import 'dart:io';
|
||
|
||
int getIntLine() => int.parse(stdin.readLineSync(encoding: utf8)!);
|
||
String getStrLine() => stdin.readLineSync(encoding: utf8)!;
|
||
|
||
void printGraphsName(List<Graphs> inp) {
|
||
print("Графы: ");
|
||
for (int i = 0; i < inp.length; i++) {
|
||
print("$i: ${inp[i].getName()}");
|
||
}
|
||
}
|
||
|
||
void main(List<String> arguments) {
|
||
/* Map<int, int> x = {2: 10};
|
||
var p = Dot.fromMap("Т1", x);
|
||
p.printD();
|
||
x = <int, int>{};
|
||
|
||
x[3] = 11;
|
||
var p2 = Dot.fromMap("Т2", {});
|
||
x = <int, int>{};
|
||
|
||
var x1 = Graphs.fromList("Граф 1", [p, p2], true, false);
|
||
x1.addIsolated("T3");
|
||
x1.addIsolated("T4");
|
||
x1.addPath(2, 3, 21);
|
||
//print(x1.addPath(4, 1, 10));
|
||
x1.printG();
|
||
x1.printToFile("o.txt");
|
||
var x2 = Graphs.fromFile("o.txt");
|
||
x2.printG();
|
||
|
||
print(x2.bfsPath(1, 3));
|
||
*/
|
||
/*var x1 = Graphs("Gt", false, true);
|
||
x1.addIsolated("T1");
|
||
x1.addIsolated("T2");
|
||
x1.addIsolated("T3");
|
||
x1.addIsolated("T4");
|
||
x1.addPath(1, 3, 1);
|
||
x1.addPath(3, 2, 5);
|
||
x1.addPath(2, 4, 10);
|
||
x1.printG();*/
|
||
var x1 = Graphs.fromFile("star.txt");
|
||
for (var i in x1.getSortedPathList()) {
|
||
print("${i.l} ${i.d} ${i.p}");
|
||
}
|
||
x1.kruskal()!.printG();
|
||
//print(x1.getSortedPathList());
|
||
//print(x1.bfsPath(1, 4));
|
||
//print(x1.dfsIterative(1));
|
||
//print(x1.dijkstra(2));
|
||
/* var x1 = Graphs.fromFile("star.txt");
|
||
print(x1.prim());
|
||
|
||
|
||
int deistvie = 1;
|
||
List<Graphs> graphs = <Graphs>[];
|
||
String name;
|
||
String str = "";
|
||
while (deistvie != 0) {
|
||
stdout.write(
|
||
"1 - создать граф, 2 - удалить граф, 3 - добавить в граф вершину,\n4 - удалить вершину, 5 - добавить ребро/дугу, 6 - удалить ребро/дугу,\n7 - вывести граф на экран, 8 - вывести граф в файл, 9 - алгоритмы,\n0 - выход\nDeistvie: ");
|
||
deistvie = getIntLine();
|
||
switch (deistvie) {
|
||
case 1:
|
||
{
|
||
// создать граф
|
||
print("1 - ввести из файла, 2 - ввести вручную\nDeistvie: ");
|
||
int d = getIntLine();
|
||
List<Dot> list = <Dot>[];
|
||
switch (d) {
|
||
case 1:
|
||
{
|
||
// из файла
|
||
stdout.write("Имя файла: ");
|
||
name = getStrLine();
|
||
graphs.add(Graphs.fromFile(name));
|
||
graphs.last.printG();
|
||
break;
|
||
}
|
||
case 2:
|
||
{
|
||
// с консоли
|
||
stdout.write("Имя графа: ");
|
||
name = getStrLine();
|
||
|
||
stdout.write(
|
||
"Граф: 1 - ориентированный, 2 - не ориентированный: ");
|
||
bool isOriented;
|
||
String x = getStrLine();
|
||
if (x == "1") {
|
||
isOriented = true;
|
||
} else {
|
||
isOriented = false;
|
||
}
|
||
|
||
stdout.write("Граф: 1 - взвешенный, 2 - не взвешенный: ");
|
||
bool hasLength;
|
||
x = getStrLine();
|
||
if (x == "1") {
|
||
hasLength = true;
|
||
} else {
|
||
hasLength = false;
|
||
}
|
||
|
||
stdout.write("Количество вершин: ");
|
||
int n = getIntLine();
|
||
|
||
list = <Dot>[];
|
||
for (int i = 0; i < n; i++) {
|
||
stdout.write("Имя вершины: ");
|
||
String dotName = getStrLine();
|
||
|
||
stdout.write(
|
||
"Ввод: *куда*|*вес* через пробел. Если граф не взвешенный, то *вес* можно не указывать.\nВершина №${i + 1}. Смежна с: ");
|
||
str = getStrLine();
|
||
|
||
List<int> inn = <int>[];
|
||
List<int> len = <int>[];
|
||
List<String> a = str.split(Separators.space);
|
||
for (var splitted in a) {
|
||
var dt = splitted.split(Separators.dotToLength);
|
||
if (dt.length == 2) {
|
||
inn.add(int.parse(dt[0]));
|
||
len.add(int.parse(dt[1]));
|
||
} else if (dt.length == 1) {
|
||
inn.add(int.parse(splitted));
|
||
len.add(0);
|
||
}
|
||
}
|
||
list.add(Dot.fromTwoLists(dotName, inn, len));
|
||
}
|
||
Graphs newG =
|
||
Graphs.fromList(name, list, hasLength, isOriented);
|
||
newG.printG();
|
||
graphs.add(newG);
|
||
break;
|
||
}
|
||
}
|
||
break;
|
||
}
|
||
case 2:
|
||
{
|
||
// удалить граф
|
||
int num = graphs.length;
|
||
printGraphsName(graphs);
|
||
stdout.write("Удалить граф с номером: ");
|
||
int x = getIntLine();
|
||
if (x >= 0 && x < num) {
|
||
graphs.removeAt(x);
|
||
} else {
|
||
print("Не найден граф с таким номером");
|
||
}
|
||
break;
|
||
}
|
||
case 3:
|
||
{
|
||
// добавить вершину
|
||
List<int> inn = <int>[];
|
||
List<int> len = <int>[];
|
||
|
||
stdout.write("Имя вершины: ");
|
||
String dotName = getStrLine();
|
||
|
||
/*stdout.write(
|
||
"Ввод: *куда*|*вес* через пробел. Если граф не взвешенный, то *вес* можно не указывать.\nВершина cмежна с: ");
|
||
str = getStrLine();
|
||
|
||
List<String> a = str.split(Separators.space);
|
||
for (var splitted in a) {
|
||
var dt = splitted.split(Separators.dotToLength);
|
||
if (dt.length == 2) {
|
||
inn.add(int.parse(dt[0]));
|
||
len.add(int.parse(dt[1]));
|
||
} else if (dt.length == 1) {
|
||
inn.add(int.parse(splitted));
|
||
len.add(0);
|
||
}
|
||
}*/
|
||
printGraphsName(graphs);
|
||
stdout.write("Вставка в графа с номером: ");
|
||
int y = getIntLine();
|
||
if (y >= 0 && y < graphs.length) {
|
||
graphs[y].addIsolated(dotName);
|
||
} else {
|
||
print("Не найден граф с таким номером");
|
||
}
|
||
graphs[y].printG();
|
||
break;
|
||
}
|
||
case 4:
|
||
{
|
||
// удалить вершину
|
||
int num = graphs.length;
|
||
printGraphsName(graphs);
|
||
stdout.write("Вывод графа с номером: ");
|
||
int y = getIntLine();
|
||
if (y >= 0 && y < num) {
|
||
graphs[y].printG();
|
||
num = graphs[y].getDotAmount();
|
||
stdout.write("Количество вершин: $num. Вершина для удаления: ");
|
||
int x = getIntLine();
|
||
if (x >= 0 && x < num) {
|
||
graphs[y].delDot(x);
|
||
} else {
|
||
print("Не найдены вершины в графе\n");
|
||
}
|
||
} else {
|
||
print("Не найден граф с таким номером");
|
||
}
|
||
break;
|
||
}
|
||
case 5:
|
||
{
|
||
// добавить ребро/дугу
|
||
int num = graphs.length;
|
||
printGraphsName(graphs);
|
||
stdout.write("Вставка в граф с номером: ");
|
||
int y = getIntLine();
|
||
if (y >= 0 && y < num) {
|
||
graphs[y].printG();
|
||
num = graphs[y].getDotAmount();
|
||
stdout.write("Количество вершин: $num. Вершина куда вствляется: ");
|
||
int x1 = getIntLine();
|
||
stdout.write("Вершина, которую вставляют: ");
|
||
int x2 = getIntLine();
|
||
stdout.write("Вес ребра, вствить 0 если граф не взвешенный: ");
|
||
int w = getIntLine();
|
||
if (x1 >= 0 && x1 < num && x2 >= 0 && x2 < num) {
|
||
graphs[y].addPath(x1, x2, w);
|
||
} else {
|
||
print("Не найдены вершины в графе\n");
|
||
}
|
||
} else {
|
||
print("Не найден граф с таким номером");
|
||
}
|
||
break;
|
||
}
|
||
case 6:
|
||
{
|
||
// удалить ребро/дугу
|
||
int num = graphs.length;
|
||
printGraphsName(graphs);
|
||
stdout.write("Удаление из графа с номером: ");
|
||
int y = getIntLine();
|
||
int x1, x2;
|
||
if (y >= 0 && y < num) {
|
||
graphs[y].printG();
|
||
num = graphs[y].getDotAmount();
|
||
stdout.write(
|
||
"Количество вершин: $num. Введите через пробел 2 вершины, между которыми удалить ребро: ");
|
||
List<String> x = getStrLine().split(Separators.space);
|
||
x1 = int.parse(x[0]);
|
||
x2 = int.parse(x[1]);
|
||
if (x1 >= 0 && x1 < num && x2 >= 0 && x2 < num) {
|
||
graphs[y].delPath(x1, x2);
|
||
} else {
|
||
print("Не найдены вершины в графе\n");
|
||
}
|
||
} else {
|
||
print("Не найден граф с таким номером");
|
||
}
|
||
break;
|
||
}
|
||
case 7: // вывод в консоль
|
||
{
|
||
int num = graphs.length;
|
||
printGraphsName(graphs);
|
||
stdout.write("Вывод графа с номером: ");
|
||
int x = getIntLine();
|
||
if (x >= 0 && x < num) {
|
||
graphs[x].printG();
|
||
} else {
|
||
print("Не найден граф с таким номером");
|
||
}
|
||
break;
|
||
}
|
||
case 8:
|
||
{
|
||
// вывод в файл
|
||
int num = graphs.length;
|
||
printGraphsName(graphs);
|
||
stdout.write("Вывод графа с номером: ");
|
||
int x = getIntLine();
|
||
stdout.write("В файл: ");
|
||
String out = getStrLine();
|
||
if (x >= 0 && x < num) {
|
||
graphs[x].printToFile(out);
|
||
} else {
|
||
print("Не найден граф с таким номером");
|
||
}
|
||
break;
|
||
}
|
||
case 9:
|
||
{
|
||
print("1 - BFS, 2 - DFS, 3 - Дейкстра. Действие:");
|
||
int d = getIntLine();
|
||
printGraphsName(graphs);
|
||
int num = graphs.length;
|
||
stdout.write("Работаем в графе с номером: ");
|
||
int y = getIntLine();
|
||
graphs[y].printG();
|
||
if (y >= 0 && y < num) {
|
||
num = graphs[y].getDotAmount();
|
||
stdout.write("Вершина, из которой выходят: ");
|
||
int x1 = getIntLine();
|
||
switch (d) {
|
||
case 1:
|
||
{
|
||
stdout.write("Вершина, в которую идут: ");
|
||
int x2 = getIntLine();
|
||
if (x1 >= 0 && x1 <= num && x2 >= 0 && x2 <= num) {
|
||
print("BFS: ${graphs[y].bfsPath(x1, x2)}");
|
||
} else {
|
||
print("Не найдены введеные вершины в графе\n");
|
||
}
|
||
break;
|
||
}
|
||
case 2:
|
||
{
|
||
if (x1 >= 0 && x1 <= num) {
|
||
print("DFS: ${graphs[y].dfsIterative(x1)}");
|
||
} else {
|
||
print("Не найдена введеныая вершина в графе\n");
|
||
}
|
||
break;
|
||
}
|
||
case 3:
|
||
{
|
||
if (x1 >= 0 && x1 <= num) {
|
||
print("Dijkstra: ${graphs[y].dijkstra(x1)}");
|
||
if (!graphs[y].getUseLengthBool()) {
|
||
print("*Т.к. граф не взвешенный, то вес пути = 1.\n");
|
||
}
|
||
} else {
|
||
print("Не найдена введеная вершина в графе\n");
|
||
}
|
||
break;
|
||
}
|
||
default:
|
||
{
|
||
break;
|
||
}
|
||
}
|
||
} else {
|
||
print("Не найден граф с таким номером");
|
||
}
|
||
break;
|
||
}
|
||
case 10:
|
||
{
|
||
print(graphs[0].prim());
|
||
break;
|
||
}
|
||
case 0:
|
||
getStrLine();
|
||
exit(0);
|
||
default:
|
||
print("Действие не распознано");
|
||
break;
|
||
}
|
||
}*/
|
||
}
|