РасчетСистемЛинейныхУравнений.ПолучитьГлубинуГрафа

Найти группы зависимостей в собственном графе и отличить связность от решения уравнений

Два двусторонне связанных блока соединены одной направленной связью. Слабая связность объединяет их, сильная оставляет два блока.

Подготовка

1. Учебная база платформы 8.5.1.1343, серверный общий модуль УчебныеЗадачи. Фрагмент вставьте в тело ВыполнитьПример() Экспорт и вызовите из серверной команды собственной обработки.

2. Все таблицы создаются в памяти. Документы, регистры, расчёт себестоимости конфигурации и внешние сервисы не используются.

3. Номера уравнений и переменных 0 и 1 в этих задачах — собственные ключи. Имена колонок передаются явно; индексы коллекций начинаются с 0.

4. Не запускайте расчёт больших матриц на рабочем сервере по аналогии с уроком: здесь только две неизвестные и контроль заранее известного решения.

5. Эта задача только анализирует граф. Не задавайте источник свободных членов и не запускайте РассчитатьСистемыЛинейныхУравнений для этой матрицы связности.

Связи = Новый ТаблицаЗначений;
Связи.Колонки.Добавить("Уравнение", Новый ОписаниеТипов("Число"));
Связи.Колонки.Добавить("Переменная", Новый ОписаниеТипов("Число"));
Связи.Колонки.Добавить("Вес", Новый ОписаниеТипов("Число"));
Ребра = Новый Массив;
Ребра.Добавить(Новый Структура("Уравнение,Переменная,Вес", 0, 1, 1));
Ребра.Добавить(Новый Структура("Уравнение,Переменная,Вес", 1, 0, 1));
Ребра.Добавить(Новый Структура("Уравнение,Переменная,Вес", 1, 2, 1));
Ребра.Добавить(Новый Структура("Уравнение,Переменная,Вес", 2, 1, 1));
Ребра.Добавить(Новый Структура("Уравнение,Переменная,Вес", 3, 4, 1));
Ребра.Добавить(Новый Структура("Уравнение,Переменная,Вес", 4, 3, 1));
Ребра.Добавить(Новый Структура("Уравнение,Переменная,Вес", 2, 3, 1));
Для Каждого Ребро Из Ребра Цикл
    НоваяСвязь = Связи.Добавить();
    ЗаполнитьЗначенияСвойств(НоваяСвязь, Ребро);
КонецЦикла;
Расчет = Новый РасчетСистемЛинейныхУравнений;
Расчет.ИсточникДанныхСвязей = Связи;
Расчет.КолонкаУравненияВСвязях = "Уравнение";
Расчет.КолонкаПеременныеВСвязях = "Переменная";
Описание = Расчет.ОписанияСистем.Добавить();
Описание.КолонкаКоэффициентовВСвязях = "Вес";
// Для методов графа КолонкаКоэффициентовВУзлах не задаётся.
Слабые = Расчет.ПолучитьКомпонентыСвязности(СпособПолученияКомпонентСвязностиРасчетаСистемЛинейныхУравнений.КомпонентыСлабойСвязности);
Сильные = Расчет.ПолучитьКомпонентыСвязности(СпособПолученияКомпонентСвязностиРасчетаСистемЛинейныхУравнений.КомпонентыСильнойСвязности);
СлабыеПоУзлу = Новый Соответствие;
Для Каждого СтрокаКомпоненты Из Слабые Цикл
    СлабыеПоУзлу.Вставить(СтрокаКомпоненты[0], СтрокаКомпоненты[1]);
КонецЦикла;
СильныеПоУзлу = Новый Соответствие;
Для Каждого СтрокаКомпоненты Из Сильные Цикл
    СильныеПоУзлу.Вставить(СтрокаКомпоненты[0], СтрокаКомпоненты[1]);
КонецЦикла;
Сообщить(Слабые.Количество() = 5 И Сильные.Количество() = 5);
Сообщить(СлабыеПоУзлу.Получить(0) = СлабыеПоУзлу.Получить(4));
Сообщить(СильныеПоУзлу.Получить(0) = СильныеПоУзлу.Получить(1));
Сообщить(СильныеПоУзлу.Получить(1) = СильныеПоУзлу.Получить(2));
Сообщить(СильныеПоУзлу.Получить(3) = СильныеПоУзлу.Получить(4));
Сообщить(СильныеПоУзлу.Получить(0) <> СильныеПоУзлу.Получить(3));
Глубина = Расчет.ПолучитьГлубинуГрафа(0);
Сообщить(ТипЗнч(Глубина) = Тип("Число") И Глубина > 0);
Сообщить("Глубина поиска от собственной вершины 0 по API: " + Строка(Глубина));

Разбор по шагам

1. Собственные вершины 0/1/2 взаимно достижимы, 3/4 тоже. Между блоками есть только одна направленная связь.

2. По текущей справке методы графа требуют источника связей, двух ключевых колонок и одного описания только с колонкой коэффициентов в связях.

3. Явно выбираем слабые и сильные компоненты. Не полагаемся на меняющееся с режимом совместимости значение по умолчанию.

4. Результат содержит номер узла в первой колонке и номер компоненты во второй. Сохраняем соответствие и сравниваем членство, не выдумываем постоянные номера компонент.

5. В слабом графе блоки связаны; в сильном единственного направления между ними недостаточно для взаимной достижимости.

6. ПолучитьГлубинуГрафа использует существующую вершину 0. Выводим значение API, не подменяем его числом неизвестных или минимальным расстоянием.

Как проверить результат

1. Семь булевых сообщений Истина: по пять узлов, нужные совпадения/различия компонент и числовая положительная глубина.

2. Первая и последняя вершины принадлежат одной слабой, но разным сильным компонентам; конкретные номера компонент не фиксируются.

Ожидаемый результат

Структура зависимостей разобрана отдельно от численного решения системы.

На что обратить внимание

1. Связность не доказывает существование единственного решения или невырожденность матрицы.

2. Глубина поиска в глубину не равна кратчайшему расстоянию и не является временем расчёта.

3. Графовые методы здесь вызываются с одним описанием без свободных членов, согласно специальному контракту API.

Пример не запускался в вашей базе. Перед применением проверьте его в указанном учебном контексте.