Лабораторные работы / Лабораторная работа 5 / Перемножение матриц и поиск минимального остовного дерева (Машеров).source / prims_algorithm

Data List['t]
{
List = c_nil ++ 't * List['t].c_cons;
}

Data Pair
{
Pair = int * int.c_pair;
}

Scheme Prims_algorithm
{
/// readSize - читает количество вершин в файле
// [1]: файловая строка
// -> [1]: файловая строчка с элементами матрицы
// -> [2]: число вершин
readSize = readNumber;

/// readNumber - читает число в файле
// [1]: файловая строка
// -> [1]: остаток файловой строки
// -> [2]: прочитанное число
readNumber = ([1] *"[\\d]+").getToken.([2] * [1].toInt);

/// readElements - читает элементы матрицы в файле
// [1]: файловая строка
// [2]: количество строк
// -> [1]: список строчек (строчка - список элементов строки)
readElements = ([1] * "").equal -> c_nil ,
(([1] * [2] * 0).readLine * [2]).([1] * ([2] * [3]).readElements).c_cons;

/// readLine - читает элементы строки матрицы в файле
// [1]: файловая строка
// [2]: количество строк
// [3]: номер текущего элемента
// -> [1]: список прочитанной строки
// -> [2]: остаток файловой строки
readLine = ([2] * [3]).equal -> c_nil * [1],
(([1].readNumber * id).([2] * ([1] * [4] * ([5] * 1).add).readLine)).(([1] * [2]).c_cons * [3]);


/// orderList: создает список вида (N - 1, N - 2, ..., 2, 1)
// [1]: число элементов в списке
// -> [1]: список с упорядоченными значениями
orderList = ([1] * [1]).orderList1;
orderList1 = ([2] * 1).equal -> c_nil,
([1] * ([2] * 1).sub).([2] * orderList1).c_cons;

/// in,notIn: проверяет, есть ли элемент в списке
// in, notIn
// [1]: список
// [2]: элемент
// -> [1]: true или false
in = ~c_nil -> false,
([1].~c_cons.[1] * [2]).equal -> true,
([1].~c_cons.[2] * [2]).in;
notIn = in -> false, true;

/// nth: возвращает n-ый элемент списка
// nth
// [1]: список
// [2]: номер
// -> [1] : элемент списка
nth = ([1]*[2] * 0).nth1;
nth1 = ([2] * [3]).equal -> [1].~c_cons.[1],
([1].~c_cons.[2] * [2] * ([3]*1).add).nth1;


// nnth: возвращает элемент в списке списков (типа S[i,j])
// nth
// [1]: список
// [2]: номер внутреннего списка
// [3]: номер элемента внутреннего списка
// -> [1] : элемент списка
nnth = (([1] * [2]).nth * [3]).nth;

/// delete : возвращает n:ый элемент списка
// nth
// [1]: список
// [2]: элемент
// -> [1] : cписок
delete = ~c_nil -> c_nil,
([1].~c_cons.[1] * [2]).equal -> [1].~c_cons.[2],
([1].~c_cons.[1] * ([1].~c_cons.[2] * [2]).delete).c_cons;

// Алгоритм
maxWeightValue = 99;

// ------------------------------
// prims
// [1] - матрица смежности
// [2] - множество вершин, которые осталось обработать
// [3] - номер текущей итерации
// [4] - размер
// [5] - текущий остов
// -> [1] - остов
prims = ([3] * ([4] * 1).sub).equal -> [5],
([1] * // [1]
(id * ([1] *[2] * 0 * [4] * 99 * 0 * 0).Iteration).
(([2] * [8]).delete * // [2]
([3] * 1).add * // [3]
[4] * // [4]
(([8] * [7]).c_pair * [5]).c_cons)).prims; // [5]

// ------------------------------
// Iteration - итерация алгоритма Прима
// [1] - матрица смежности
// [2] - множество вершин, которые осталось обработать
// [3] - номер вершины для обработки
// [4] - размер
// [5] - текущее минимальное значение
// [6] - текущий номер минимальной вершины
// [7] - текущий номер минимальной вершины
// -> [1] - минимальное значение
// -> [2] - номер минимальной вершины
// -> [3] - номер минимальной вершины
Iteration = ([3] * [4]).less ->
(([2] * [3]).notIn -> checkForMin,
([1] *[2] * ([3] * 1).add * [4] * [5] * [6] * [7]).Iteration),
[5] * [6] * [7];

checkForMin = (id * minEdge).
(([8] * [5]).less -> ([1] *[2] * ([3] * 1).add * [4] * [8] * [3] *[9]).Iteration,
([1] *[2] * ([3] * 1).add * [4] * [5] * [6] * [7]).Iteration);

minEdge = ([1] * [2] * [3] * 0 * [4] * 99 * 0).adjIteration;
// ------------------------------
// adjIteration,adjCheckForMin
// [1] - матрица смежности
// [2] - множество вершин, которые осталось обработать
// [3] - номер вершины для обработки
// [4] - номер вершины, смежной c [3]
// [5] - размер
// [6] - текущее минимальное значение
// [7] - текущий номер минимальной вершины
// -> [1] - минимальное значение
// -> [2] - номер минимальной вершины
adjIteration = ([4] * [5]).less ->
(([2] * [4]).in -> adjCheckForMin,
([1] *[2] * [3] * ([4] * 1).add * [5] * [6] * [7]).adjIteration),
[6] * [7];

adjCheckForMin = (id * ([1] * [3] * [4]).nnth).
(([8] * [6]).less -> ([1] * [2] * [3] * ([4] * 1).add * [5] * [8] * [4]).adjIteration,
([1] *[2] * [3] * ([4] * 1).add * [5] * [6] * [7]).adjIteration);

test = ([1] *[2] * 0 * [4] * 99 * 0 * 0).Iteration;
//test = ([2] * 5).delete;

@ = ([1].readFile.readSize * 0 * c_nil).(readElements * [2].orderList * 0 * [2] * c_nil).prims.print;
// 1 = Итерация * [2] - Размер
}

Application
% Prims_algorithm("m7.txt")