Парсер таблиц по шаблону. Автоматическая корректировка парсера. Сравнение графов

Описание 1го пункта здесь.

Важный момент, это не просто графы, а именно таблицы представленные в виде графа. То есть, считаю что таблицы ориентированы одинаково, исходя из этого, самые верхние левые ячейки таблиц (0 узлы) считаю одинаковыми, и так как нумерация проходит определенным способом, то если таблицы структурно одинаковы, то нумерация каждого из узлов должна совпадать, более того у каждого узла должны быть одинаковые рёбра.

Идея алгоритма очень проста. Граф 1 назову шаблон, граф 2 — граф. Из шаблона и графа построю новый граф. Рассмотрим i-ый узел у шаблона и графа. Берём i+1 узлы и сравниваем. Если рёбра у них одинаковы, то добавляем i узел в новый граф и его рёбра(здесь и далее "добавлять/вставлять рёбра узла" означает "добавлять/вставлять рёбра узла, которые меньше i"). Если отличаются, то есть 3 действия (сортировка по приоритету):

1) ничего не делаю

2) вставляю узел из шаблона

3) вставляю узел из графа.

Для каждого действия рассчитаю i+1 узел шаблона и графа. Для 1 — это просто i+1 узлы. Для 2 i+1 узел графа- это i, у которого часть рёбер убраны, часть увеличено на 1 (подробнее ниже). i+1 шаблона остаётся прежним. Для 3 у i узла шаблона изменятся рёбра, а у i+1 графа остаётся как есть.

Теперь для каждого действия  рассчитываю функцию ошибки между i+1 узлами. Выбираю то действие, у которого функция ошибки меньше. Если есть равенство, то выбираю по приоритету. 

На выходе получается новый граф с узлами из шаблона и графа. Я знаю какие узлы, откуда вставлял, какие новые рёбра и откуда. Из этого можно сделать вывод какие ячейки объединены, какие разделены. 

функция ВыделитьПервыеЗначенияИзСписка(Список,Предел)
спис = новый СписокЗначений;
Для каждого стр из Список цикл
Если стр.Значение>Предел тогда
Прервать;
КонецЕсли;
спис.Добавить(стр.Значение);
КонецЦикла;
возврат спис;
КонецФункции

функция КоэфициентВхожденияСписка1ВСписке2(список1,список2)

//критерий. максимум насколько одна вершина входит во вторую
Если типЗнч(список1) = тип("Массив") тогда
_список1 = новый СписокЗначений;
_список1.ЗагрузитьЗначения(список1);
иначе
_список1 = список1;
КонецЕсли;

Если типЗнч(список2) = тип("Массив") тогда
_список2 = новый СписокЗначений;
_список2.ЗагрузитьЗначения(список2);
иначе
_список2 = список2;
КонецЕсли;

Вхождений1 = 0;
Для каждого стр из _список1 цикл
Если _список2.найтиПоЗначению(стр.Значение)<> Неопределено тогда
Вхождений1 = Вхождений1+1;
КонецЕсли;
КонецЦикла;

//0 - всё входит, 1 - ничего
Если _список1.Количество() = 0 или _список2.Количество() = 0 тогда
возврат 1;
КонецЕсли;

КоэффициентВхождений = 1-окр(Вхождений1/_список1.Количество(),2);//макс(окр(Вхождений1/_список1.Количество(),2),окр(Вхождений2/_список2.Количество(),2));
возврат КоэффициентВхождений;
КонецФункции

функция ВычислитьКоличествоОшибок(список1,список2)

//критерий. насколько отличаются списке в абсолютном значении
Если типЗнч(список1) = тип("Массив") тогда
_список1 = новый СписокЗначений;
_список1.ЗагрузитьЗначения(список1);
иначе
_список1 = список1;
КонецЕсли;

Если типЗнч(список2) = тип("Массив") тогда
_список2 = новый СписокЗначений;
_список2.ЗагрузитьЗначения(список2);
иначе
_список2 = список2;
КонецЕсли;


если _список1.Количество()< _список2.Количество() тогда
расСпис = _список1;
СЧемСравнивать = _список2;
иначе
расСпис = _список2;
СЧемСравнивать = _список1;
КонецЕсли;
КоэффициентВхождений = 0;
Для каждого стр из расСпис цикл
Если СЧемСравнивать.найтиПоЗначению(стр.Значение)<> Неопределено тогда
КоэффициентВхождений = КоэффициентВхождений+1;
КонецЕсли;
КонецЦикла;

если КоэффициентВхождений = _список1.Количество() и КоэффициентВхождений = _список2.Количество() тогда
//это абсолютно одинаковые узлы
возврат 0;
иначе
возврат ?(КоэффициентВхождений = 0,100,1/КоэффициентВхождений);
КонецЕсли;

КонецФункции

Процедура ДобавитьСвязиВпрошлыеУзлыСТекущим(Куда, что, Индекс)
Для каждого узел из что цикл
если Куда[узел.значение].найтиПоЗначению(Индекс) = Неопределено тогда
Куда[узел.значение].Добавить(Индекс);
Куда[узел.значение].СортироватьПоЗначению();
КонецЕсли;
КонецЦикла;
КонецПроцедуры

Процедура Прибавить1КНомеруУзла(МассивУзлов, Индекс)
Для инт = 0 по МассивУзлов.Количество()-1 цикл
НовСписокКуда = новый СписокЗначений;
Для каждого УзелГрафа из МассивУзлов[инт] цикл
Если УзелГрафа.Значение>=Индекс тогда
НовСписокКуда.Добавить(УзелГрафа.Значение + 1);
иначе
НовСписокКуда.Добавить(УзелГрафа.Значение);
КонецЕсли;
КонецЦикла;
МассивУзлов[инт] = НовСписокКуда;
КонецЦикла;
КонецПроцедуры

функция РассчитатьСледующийУзел(ИзЧегоСчитать,ВставляемыйУзел,Индекс,УзлыОставлять=Неопределено)
//если в ВставляемыйУзел есть связь с узлом, которая есть в ИзЧегоСчитать, то её надо поменять на индекс
//типа разбиваем связь
если УзлыОставлять = Неопределено тогда
УзлыОставлять = новый СписокЗначений;
КонецЕсли;
РассчетныйСледующийШаблона = новый СписокЗначений;
Для каждого узел из ИзЧегоСчитать цикл
Если ВставляемыйУзел.найтиПоЗначению(узел.Значение) <> Неопределено и УзлыОставлять.найтиПоЗначению(узел.Значение) = Неопределено тогда
если РассчетныйСледующийШаблона.найтиПоЗначению(Индекс) = Неопределено тогда
РассчетныйСледующийШаблона.Добавить(Индекс);
КонецЕсли;
иначеесли узел.Значение>Индекс тогда
РассчетныйСледующийШаблона.Добавить(Узел.Значение+1);
иначе
РассчетныйСледующийШаблона.Добавить(Узел.Значение);
КонецЕсли;
КонецЦикла;
возврат РассчетныйСледующийШаблона;
КонецФункции

Процедура  ВставитьНовыйУзелВГраф(НовыйГраф,Индекс,НовыеУзлы,ВставляемыеУзлы,Источник,ДругойГраф,АтрибутыДругойГраф)
НовыйГраф.Вставить(Индекс,НовыеУзлы);
ДобавитьСвязиВпрошлыеУзлыСТекущим(НовыйГраф, НовыеУзлы,Индекс);
Прибавить1КНомеруУзла(ДругойГраф,Индекс);
ДругойГраф.Вставить(Индекс,новый СписокЗначений);
АтрибутыДругойГраф.Вставить(индекс);
нов = ВставляемыеУзлы.Добавить();
нов.Источник = Источник;
нов.Индекс = Индекс;
КонецПроцедуры

Процедура ОбъединитьРёбраУзла(ВставляемыеРёбра,УзлыГраф,УзлыШаблон,НовыйГраф,Индекс)
СписокВставляемыРёбер = ВставляемыеРёбра.Получить(Индекс);
Если СписокВставляемыРёбер = Неопределено тогда
СписокВставляемыРёбер = новый СписокЗначений;
КонецЕсли;

НовыеУзлы = новый СписокЗначений;
Для каждого стр из УзлыГраф цикл
если НовыеУзлы.найтиПоЗначению(стр.значение) = Неопределено тогда
НовыеУзлы.Добавить(стр.значение);
КонецЕсли;
Если УзлыШаблон.найтиПоЗначению(стр.значение) = Неопределено тогда
СписокВставляемыРёбер.Добавить(стр.значение);
найд = ВставляемыеРёбра.Получить(стр.значение);
Если найд = Неопределено тогда
найд = новый СписокЗначений;
КонецЕсли;
найд.Добавить(Индекс);
ВставляемыеРёбра.Вставить(стр.значение,найд);
КонецЕсли;
КонецЦикла;
Для каждого стр из УзлыШаблон цикл
если НовыеУзлы.найтиПоЗначению(стр.значение) = Неопределено тогда
НовыеУзлы.Добавить(стр.значение);
КонецЕсли;
Если УзлыГраф.найтиПоЗначению(стр.значение) = Неопределено тогда
СписокВставляемыРёбер.Добавить(стр.значение);
найд = ВставляемыеРёбра.Получить(стр.значение);
Если найд = Неопределено тогда
найд = новый СписокЗначений;
КонецЕсли;
найд.Добавить(Индекс);
ВставляемыеРёбра.Вставить(стр.значение,найд);
КонецЕсли;
КонецЦикла;
НовыйГраф.Вставить(Индекс,НовыеУзлы);
ДобавитьСвязиВпрошлыеУзлыСТекущим(НовыйГраф, НовыеУзлы,Индекс);
ВставляемыеРёбра.Вставить(Индекс,СписокВставляемыРёбер);
КонецПроцедуры

функция РассчитатьОшибкиПриВставкеУзла(Откуда,ИндексОткуда,Индекс,Куда,ВставляемыйУзел)
РассчетныйСледующийОткуда = Откуда[ИндексОткуда];
РассчетныйСледующийКуда = РассчитатьСледующийУзел(Куда[Индекс],ВставляемыйУзел,Индекс);
количествоОшибок = ВычислитьКоличествоОшибок(РассчетныйСледующийКуда,РассчетныйСледующийОткуда);
//расмматриваются все возможные сочетания (без учета места)
Для инт=0 по ВставляемыйУзел.Количество()-1 цикл
УзлыОставлять = новый СписокЗначений;
УзлыОставлять.Добавить(ВставляемыйУзел[инт].Значение);
РассчетныйСледующийКуда = РассчитатьСледующийУзел(Куда[Индекс],ВставляемыйУзел,Индекс,УзлыОставлять);
количествоОшибок = мин(ВычислитьКоличествоОшибок(РассчетныйСледующийКуда,РассчетныйСледующийОткуда),количествоОшибок);

Для йцу = инт+1 по  ВставляемыйУзел.Количество()-1 цикл
УзлыОставлять.Добавить(ВставляемыйУзел[йцу].Значение);
РассчетныйСледующийКуда = РассчитатьСледующийУзел(Куда[Индекс],ВставляемыйУзел,Индекс,УзлыОставлять);
количествоОшибок = мин(количествоОшибок,ВычислитьКоличествоОшибок(РассчетныйСледующийКуда,РассчетныйСледующийОткуда));
КонецЦикла;
КонецЦикла;
возврат КоличествоОшибок;
КонецФункции

&НаСервере
процедура ЗаполнитьНовыйГраф(НовыйГраф,Шаблон,Граф,ВставляемыеУзлы,ВставляемыеРёбра,АтрибутыШаблона,АтрибутыГрафа)
МаксРазмер = макс(Шаблон.Количество(), Граф.Количество());
Индекс=0;
Пока Индекс<=МаксРазмер-1 цикл
//рассматриваем только узлы, которые меньше текущего индекса
если Шаблон.ВГраница()<Индекс и Граф.ВГраница()<Индекс тогда
Прервать;
иначеесли Шаблон.ВГраница()<Индекс тогда
НовыеУзлы = ВыделитьПервыеЗначенияИзСписка(Граф[Индекс],Индекс);
ВставитьНовыйУзелВГраф(НовыйГраф,Индекс,НовыеУзлы,ВставляемыеУзлы,"Граф",Шаблон,АтрибутыШаблона);
Индекс = Индекс + 1;
Продолжить;
иначеесли Граф.ВГраница()<Индекс тогда
НовыеУзлы = ВыделитьПервыеЗначенияИзСписка(Шаблон[Индекс],Индекс);
ВставитьНовыйУзелВГраф(НовыйГраф,Индекс,НовыеУзлы,ВставляемыеУзлы,"Шаблон",Граф,АтрибутыГрафа);
Индекс = Индекс + 1;
Продолжить;
КонецЕсли;

УзлыШаблон = Шаблон[Индекс];
УзлыГраф = граф[Индекс];

если строка(УзлыГраф) = строка(УзлыШаблон) тогда
//вставим рёбра в прошлые узлы
Узлы = ВыделитьПервыеЗначенияИзСписка(УзлыШаблон,Индекс);
НовыйГраф.Вставить(Индекс,Узлы);
ДобавитьСвязиВпрошлыеУзлыСТекущим(НовыйГраф, Узлы,Индекс);
иначе
//рассмотрим 3 действия
//1)объединим рёбра узлов графа и шаблона
//2)Добавим узел шаблона
//3)Добавим узел графа
//Сравним следующие узлы в каждом из случаев. Выберу тот случай, в котором ошибка наименьше.
//если это последняя узел для одной, то сравниваем следующую с ней.
//если обе последние, то соединяем
если Индекс=Шаблон.ВГраница() и Граф.ВГраница()=Индекс тогда
УзлыГраф = ВыделитьПервыеЗначенияИзСписка(УзлыГраф,Индекс);
УзлыШаблон = ВыделитьПервыеЗначенияИзСписка(УзлыШаблон,Индекс);
ОбъединитьРёбраУзла(ВставляемыеРёбра,УзлыГраф,УзлыШаблон,НовыйГраф,Индекс);
иначе
ИндексШаблон = ?(Индекс=Шаблон.ВГраница(),Индекс,Индекс+1);
ИндексГраф = ?(Индекс=Граф.ВГраница(),Индекс,Индекс+1);
//1
СледующийУзелГраф = Граф[ИндексГраф];
СледующийУзелШаблон = Шаблон[ИндексШаблон];
количествоОшибокНичего = ВычислитьКоличествоОшибок(СледующийУзелГраф,СледующийУзелШаблон);
//бывает ситуация когда ошибка влияет на рёбра узла. К примеру, рассматриваем 9 узел, ошибка в 11
//рёбра 9 {12,13,14}. Корректнее ничего не делать, 11 узел добавляю, все корректно.
//НО, если просто смотреть, то рёбра на текущий момент у одного графа {13,14,15} а у второго {12,13,14}
//тогда программа решает что выгоднее производить другое действия.
//поэтому имеет смысл рассматривать варианты +1 к следующим за индексом узлам.
РассчетныйСледующийШаблона = РассчитатьСледующийУзел(СледующийУзелШаблон,новый СписокЗначений,Индекс,новый СписокЗначений);
РассчетныйСледующийГраф = РассчитатьСледующийУзел(СледующийУзелГраф ,новый СписокЗначений,Индекс,новый СписокЗначений);
количествоОшибокНичего = мин(количествоОшибокНичего,ВычислитьКоличествоОшибок(СледующийУзелГраф,РассчетныйСледующийШаблона),ВычислитьКоличествоОшибок(СледующийУзелШаблон,РассчетныйСледующийГраф));
//2
//при вставке узла, есть вариант когда рёбра расчётного следующего разрушаются, а могут и не разрушаться
//просмотрю все варианты и выберу наименьшую ошибку
ВставляемыйУзелГраф = ВыделитьПервыеЗначенияИзСписка(Граф[Индекс],Индекс);
КоличествоОшибокВставитьГраф = РассчитатьОшибкиПриВставкеУзла(Граф,ИндексГраф,Индекс,Шаблон,ВставляемыйУзелГраф);
//3
ВставляемыйУзелШаблон = ВыделитьПервыеЗначенияИзСписка(Шаблон[Индекс],Индекс);
количествоОшибокВставитьШаблон = РассчитатьОшибкиПриВставкеУзла(Шаблон,ИндексШаблон,Индекс,граф,ВставляемыйУзелШаблон);

МинОшибка = мин(количествоОшибокНичего ,количествоОшибокВставитьГраф,количествоОшибокВставитьШаблон);

НичегоНеДелать = МинОшибка =  количествоОшибокНичего;
ДобавитьУзелИзГрафа = МинОшибка =  количествоОшибокВставитьГраф;
ДобавитьУзелИзШаблона = МинОшибка =  количествоОшибокВставитьШаблон;

//также конкретно следующий узел может быть ошибочным, поэтому сравнение следующих узлов может выдать некорректное действие.
//Попробую вставить не текущий узел, а следующий, заодно рассчитать послеследующий узел и ошибки в нём
//Если ошибка меньше чем текущая ошибка вставки, то выгоднее ничего не делать.
Если  КоличествоОшибокВставитьГраф<>0 и количествоОшибокВставитьШаблон<>0 тогда
если ДобавитьУзелИзШаблона и ИндексШаблон<Шаблон.ВГраница()и Индекс<Граф.ВГраница() тогда
КоличествоОшибокВставитьСледующий = ВычислитьКоличествоОшибок(РассчитатьСледующийУзел(Граф[Индекс+1],ВыделитьПервыеЗначенияИзСписка(Шаблон[Индекс+1],Индекс+1),Индекс+1),Шаблон[ИндексШаблон+1]);
если  КоличествоОшибокВставитьСледующий< количествоОшибокВставитьШаблон тогда
НичегоНеДелать = истина;
КонецЕсли;
КонецЕсли;
если ДобавитьУзелИзГрафа и ИндексГраф<Граф.ВГраница() и Индекс<Шаблон.ВГраница() тогда
КоличествоОшибокВставитьСледующий = ВычислитьКоличествоОшибок(РассчитатьСледующийУзел(Шаблон[Индекс+1],ВыделитьПервыеЗначенияИзСписка(Граф[Индекс+1],Индекс+1),Индекс+1),Граф[ИндексГраф+1]);
если  КоличествоОшибокВставитьСледующий< КоличествоОшибокВставитьГраф тогда
НичегоНеДелать = истина;
КонецЕсли;
КонецЕсли;
КонецЕсли;

Если НичегоНеДелать тогда
//1) объединяем
//надо запомнить какие узлы откуда были добавлены
ОбъединитьРёбраУзла(ВставляемыеРёбра,ВставляемыйУзелГраф,ВставляемыйУзелШаблон,НовыйГраф,Индекс);
ИначеЕсли ДобавитьУзелИзШаблона тогда
//2)Добавим узел Шаблона
НовыеУзлы = новый СписокЗначений;
НовыеУзлы.ЗагрузитьЗначения(ВставляемыйУзелШаблон.ВыгрузитьЗначения());
ВставитьНовыйУзелВГраф(НовыйГраф,Индекс,НовыеУзлы,ВставляемыеУзлы,"Шаблон",Граф,АтрибутыГрафа);
ИначеЕсли ДобавитьУзелИзГрафа тогда
//3)Добавим узел графа
НовыеУзлы = новый СписокЗначений;
НовыеУзлы.ЗагрузитьЗначения(ВставляемыйУзелГраф.ВыгрузитьЗначения());
ВставитьНовыйУзелВГраф(НовыйГраф,Индекс,НовыеУзлы,ВставляемыеУзлы,"Граф",Шаблон,АтрибутыШаблона);
КонецЕсли;
КонецЕсли;
КонецЕсли;
МаксРазмер = макс(Шаблон.Количество(), Граф.Количество());
Индекс = Индекс + 1;
КонецЦикла;
КонецПроцедуры

&НаСервере
функция  СгруппироватьОбъединенияВычислитьОшибку(ТабОбъединений,АтрибутыШаблона,АтрибутыГрафа,НовыйГраф,ВставляемыеРёбра,ВставляемыеУзлы)
СчетчикОшибок = 0;
КолДобавленныйСвязей = 0;
Правки = новый Массив;

//в предыдущеё операции получили объединеннные пары узлов. Тут сгруппирую.
ЗАпрос = новый запрос("ВЫБРАТЬ
| таб.ДобавляемыУзел КАК ДобавляемыУзел,
| таб.Объединен КАК Объединен,
| таб.Источник КАК Источник
|ПОМЕСТИТЬ Объеденения
|ИЗ
| &таб КАК таб
|;
|
|////////////////////////////////////////////////////////////////////////////////
|ВЫБРАТЬ РАЗЛИЧНЫЕ
| Объеденения.Объединен КАК Объединен,
| Объеденения1.ДобавляемыУзел КАК ДобавляемыУзел,
| Объеденения1.Источник КАК Источник
|ИЗ
| Объеденения КАК Объеденения
|  ЛЕВОЕ СОЕДИНЕНИЕ Объеденения КАК Объеденения1
|  ПО Объеденения.Объединен = Объеденения1.Объединен
|ИТОГИ ПО
| Объединен");
ЗАпрос.УстановитьПараметр("таб", ТабОбъединений);
Рез = Запрос.Выполнить().Выбрать(ОбходРезультатаЗапроса.ПоГруппировкам);

РасмотренныеУзлы= новый Массив;

Пока рез.Следующий() цикл
//паралельно вычислю ошибку по размеру объединённых ячеек.
//Известно что либо в графе была разбита ясйека, либо в шаблоне,
//знаю, какие конкретно, а значит могу сравнить суммы разбитых и исходную
ДобавленоШаблоном = ложь;
ДобавленоГрафом = ложь;
Дет = рез.Выбрать();
Спис = новый СписокЗначений;
спис.Добавить(рез.Объединен);
РасмотренныеУзлы.Добавить(рез.Объединен);
РазмерШаблон = АтрибутыШаблона[рез.Объединен].РазмерХ*АтрибутыШаблона[рез.Объединен].РазмерУ;
РазмерГраф = АтрибутыГрафа[рез.Объединен].РазмерХ*АтрибутыГрафа[рез.Объединен].РазмерУ;

пока дет.Следующий() цикл
спис.Добавить(дет.ДобавляемыУзел);
ДобавленоШаблоном = макс(ДобавленоШаблоном,дет.Источник = "Шаблон");
ДобавленоГрафом =макс(ДобавленоГрафом,дет.Источник = "Граф");
РасмотренныеУзлы.Добавить(дет.ДобавляемыУзел);
РазмерШаблон = РазмерШаблон + АтрибутыШаблона[дет.ДобавляемыУзел].РазмерХ*АтрибутыШаблона[дет.ДобавляемыУзел].РазмерУ;
РазмерГраф = РазмерГраф + АтрибутыГрафа[дет.ДобавляемыУзел].РазмерХ*АтрибутыГрафа[дет.ДобавляемыУзел].РазмерУ;
КонецЦикла;
если ДобавленоШаблоном и ДобавленоГрафом тогда
источник = "Непонятно что";
иначеесли ДобавленоШаблоном тогда
источник = "Шаблон";
иначеесли ДобавленоГрафом тогда
источник = "Граф";
КонецЕсли;
Правки.Добавить(новый Структура("Источник,Тип,Узлы",источник,"Объединили",спис));
Если   источник = "Непонятно что" тогда
СчетчикОшибок = СчетчикОшибок + спис.Количество();
ИначеЕсли РазмерШаблон<>РазмерГраф Тогда
СчетчикОшибок = СчетчикОшибок + 1;
КонецЕсли;
КонецЦикла;

//тут рассмотри все остальные ячейки
Для инт=0 по НовыйГраф.Количество()-1 цикл
если РасмотренныеУзлы.Найти(инт)<>Неопределено тогда
Продолжить;
КонецЕсли;
если не АтрибутыГрафа[инт].РазмерХ*АтрибутыГрафа[инт].РазмерУ =  АтрибутыШаблона[инт].РазмерХ*АтрибутыШаблона[инт].РазмерУ тогда
СчетчикОшибок = СчетчикОшибок + 1;
КонецЕсли;
КонецЦикла;

//количество новых рёбер с недобавленными узлами
МасПроверенныйСвязей = новый массив();
Для каждого Узел из ВставляемыеРёбра цикл
Для каждого ребро из Узел.Значение цикл
поиск = ""+Узел.Ключ+"_"+ ребро.Значение;
если МасПроверенныйСвязей.Найти(поиск)<>Неопределено тогда
Продолжить;
КонецЕсли;
поиск = ""+ ребро.Значение+"_"+ Узел.Ключ;
если МасПроверенныйСвязей.Найти(поиск)<>Неопределено тогда
Продолжить;
КонецЕсли;
Если ВставляемыеУзлы.найти(ребро.Значение,"Индекс") = Неопределено и  ВставляемыеУзлы.найти(Узел.Ключ,"Индекс") = Неопределено тогда
КолДобавленныйСвязей = КолДобавленныйСвязей + 1;
МасПроверенныйСвязей.Добавить(""+Узел.Ключ+"_"+ ребро.Значение);
КонецЕсли;
КонецЦикла;
КонецЦикла;

//количество новых рёбер с добавленными узлами
Для каждого стр из ВставляемыеУзлы цикл
КолДобавленныйСвязей = КолДобавленныйСвязей + НовыйГраф[стр.индекс].Количество();
КонецЦикла;

возврат новый Структура("СчетчикОшибок,КолДобавленныйСвязей,Правки",СчетчикОшибок,КолДобавленныйСвязей,Правки);
КонецФункции

&НаСервере
функция СравнитьГрафы(Знач Шаблон,Знач Граф,Знач АтрибутыШаблона,Знач АтрибутыГрафа)

//Строим новый граф
НовыйГраф = новый Массив;

ВставляемыеУзлы = новый ТаблицаЗначений;
ВставляемыеУзлы.Колонки.Добавить("Индекс");
ВставляемыеУзлы.Колонки.Добавить("Источник");

ВставляемыеРёбра = новый Соответствие;

ЗаполнитьНовыйГраф(НовыйГраф,Шаблон,Граф,ВставляемыеУзлы,ВставляемыеРёбра,АтрибутыШаблона,АтрибутыГрафа);

//интерпритируем полученные данные.
ТабОбъединений = новый ТаблицаЗначений;
ТабОбъединений.Колонки.Добавить("ДобавляемыУзел",новый ОписаниеТипов("Число"));
ТабОбъединений.Колонки.Добавить("Объединен",новый ОписаниеТипов("Число"));
ТабОбъединений.Колонки.Добавить("Источник",новый ОписаниеТипов("Строка",,,,новый КвалификаторыСтроки(20)));

ЗаполнитьТаблицуОбъединений(ВставляемыеУзлы,НовыйГраф,ТабОбъединений,ВставляемыеРёбра);

Ответ = СгруппироватьОбъединенияВычислитьОшибку(ТабОбъединений,АтрибутыШаблона,АтрибутыГрафа,НовыйГраф,ВставляемыеРёбра,ВставляемыеУзлы);

КоличествоСвязей = 0;
Для каждого стр из НовыйГраф цикл
КоличествоСвязей = КоличествоСвязей + стр.Количество();
КонецЦикла;

//Все новые рёбра, все новые узлы, все несовпадения по размерам влияют на результат.
Похожесть = окр(((КоличествоСвязей - Ответ.КолДобавленныйСвязей) + (НовыйГраф.Количество()-Ответ.СчетчикОшибок))/(НовыйГраф.Количество()+КоличествоСвязей)*100);

Для каждого стр из Ответ.Правки цикл
Сообщить(стр.Источник + " "+стр.узлы);
КонецЦикла;

возврат Похожесть;

КонецФункции

&НаСервере
Процедура ЗаполнитьТаблицуОбъединений(ВставляемыеУзлы,НовыйГраф,ТабОбъединений,ВставляемыеРёбра)
//Сформируем все рёбра добавленных узлов, без самих добавленных
СоседниеУзлы = новый СписокЗначений;
Для каждого Узел из ВставляемыеУзлы цикл
Соседние = НовыйГраф[Узел.Индекс];
Для каждого СоседнийУзел из Соседние цикл
Если ВставляемыеУзлы.Найти(СоседнийУзел.Значение,"Индекс")=Неопределено тогда
если СоседниеУзлы.НайтиПоЗначению(СоседнийУзел.Значение) = Неопределено тогда
СоседниеУзлы.Добавить(СоседнийУзел.Значение);
КонецЕсли;
КонецЕсли;
КонецЦикла;
КонецЦикла;

Для каждого Узел из ВставляемыеУзлы цикл
Для каждого СосоеднийУзел из СоседниеУзлы цикл
//Добавленный узел означает, что узел шаблона/графа разбивается на 2. Нужно выяснить какой конкретно узел разбивается.
//Если исходный узел разбился, то часть рёбер попадёт в добавленные. Нужно проверить если у соседнего узла
//добавлённые рёбра полностью включают определённую часть рёбер добавленного узла, то эти узлы должны быть объединенны.
//Определенная часть  =  все рёбра - добавленные узлы - текущий соседний узел - узлы, иницдентные и добавленному узлу, и соседнему, но ребро не добавлено в соседний узел
Соседние = НовыйГраф[Узел.Индекс].ВыгрузитьЗначения();
СоседниеСоседнего = НовыйГраф[СосоеднийУзел.Значение].ВыгрузитьЗначения();
//удаляю из соседних вставляемые узлы
Для каждого УдаляемыУзел из ВставляемыеУзлы цикл
найд = Соседние.найти(УдаляемыУзел.Индекс);
Если не найд = Неопределено тогда
Соседние.Удалить(найд);
КонецЕсли;
КонецЦикла;
//найдем массив вставленных
найд = ВставляемыеРёбра.Получить(СосоеднийУзел.Значение);
если найд = Неопределено тогда МассивВставленныхРёберДляТекущегоУзла = новый Массив иначе МассивВставленныхРёберДляТекущегоУзла = найд.ВыгрузитьЗначения() КонецЕсли;

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

Основная функция — СравнитьГрафы. В комментариях более-менее описаны нюансы. Пример использования

РезультатШаблон = РазобратьТаблицу_Область(макет,макет.области.Область1);
РезультатМатрица = РазобратьТаблицу_Область(макет,макет.области.Область2);
сообщить(""+СравнитьГрафы(РезультатШаблон.СписокСмежности,РезультатМатрица.СписокСмежности,РезультатШаблон.АтрибутыУзлов,РезультатМатрица.АтрибутыУзлов) +" % похожи");

Это функции из предыдущей статьи.

Теперь на простом примере опишу как работает сам алгоритм. Возьмём две таблицы.

Их графы следующие.

Списки смежностей такие

 

Шаблон	Граф	Новый
( {1,4}  {0,2,5}  {1,3,6}  {2,7}  {0,5,8}  {1,4,6,9}  {2,5,7,10}  {3,6,11}  {4,9,12}  {5,8,10,13}  {6,9,11,14}  {7,10,15}  {8,13}  {9,12,14}  {10,13,15}  {11,14})	( {1,4}  {0,2,5}  {1,3,5}  {2,6}  {0,5,7}  {1,2,4,6,7,8,10,11}  {3,5,8}  {4,5,9}  {5,6,12}  {7,10}  {5,9,11}  {5,10,12}  {8,11})	()

 

Строим новый граф. Смотрим 0 узел. И в шаблоне и в графе одинаковы. Пишем в новый граф.

1 узел, аналогично.

2 узел, рёбра отличаются. Рассмотрим следующие узлы {2,7} и {2,6}. Так как ошибка может быть в следующих узлах, это может влиять на нумерацию. Увеличим номер тех узлов, которые больше 2 и сравним. Получаем {2,8} и {2,7}. Теперь сравниваем {2,8} и {2,6}, {2,7} и {2,7}. Рёбра совпадают, значит ничего не делаем, добавляем в новый граф.

3 узел — аналогично. Возникают следующие рёбра {0,6,9} и {0,5,7}, {0,5,8} и {0,6,8}. При сравнении ошибка при ничего не делать — 0.5, при вставке узла из шаблона — 100, при вставке из графа — 100. Ничего не делаем, добавляем в новый граф.

4 узел — аналогично 3, ничего не делаем, добавляем в новый граф.

5 узел. Если ничего не делать, то следующие узлы будут {3,5,8} и {2,5,7,10}. Даже если увеличивать номера, то минимальная ошибка будет 0.5. Если добавить узел из графа, ошибка — 1, если добавить из шаблона узел {1,4}, то следующие узлы должны быть {2,5,7,10} и {2,5,7,8,9,11,12}. Ошибка — 0.33. Поэтому вставляем узел из шаблона в граф, в новый граф.

И так далее. 6, 7, 8, 11, 12, 13, 14, 15  узлы оставляются, 9,10 — добавляются. По итогу получается.

Шаблон	Граф	Новый
( {1,4}  {0,2,5}  {1,3,6}  {2,7}  {0,5,8}  {1,4,6,9}  {2,5,7,10}  {3,6,11}  {4,9,12}  {5,8,10,13}  {6,9,11,14}  {7,10,15}  {8,13}  {9,12,14}  {10,13,15}  {11,14})	( {1,4}  {0,2,6}  {1,3,6}  {2,7}  {0,6,8}  {}  {1,2,4,7,8,11,13,14}  {3,6,11}  {4,6,12}  {}  {}  {6,7,15}  {8,13}  {6,12,14}  {6,13,15}  {11,14})	( {1,4}  {0,2,5,6}  {1,3,6}  {2,7}  {0,5,6,8}  {1,4,6,9}  {1,2,4,5,7,8,10,11,13,14}  {3,6,11}  {4,6,9,12}  {5,8,10,13}  {6,9,11,14}  {6,7,10,15}  {8,13}  {6,9,12,14}  {6,10,13,15}  {11,14})

 

На рисунке оранжевым цветом выделены добавленные узлы и рёбра.

Достаточно чётко видно, что в рёбрах всех добавленных узлов есть узлы инцидентные с 6 и более того, данные рёбра отмечены как добавленные. По данному критерию можно сказать какие узлы должны быть объединены. Для i-го узла рассмотрим все соседние, не добавленные узлы. Если из рёбер i-го узла удалить все другие добавленные узлы, удалить текущий рассматриваемый соседний, а также удалить те узлы, которые инцидентны и i и соседнему, но не являются добавленным для соседнего. То в итоге, оставшиеся рёбра должны полностью включаться в добавленным для соседнего.

То есть, к примеру, у узла 5 рёбра {1,4,6,9}, у узла 6 добавленные  {1,4,5,8,11,13,14}. Удалим узел 6, так как его рассматриваем и узел 9, так как он добавленный. {1,4} оставляем, так как они инцидентны, но в списке добавленных. {1,4} полностью включается в {1,4,5,8,11,13,14}. Значит 5 и 6 объединены.

Рассматривается именно так, потому что смысл добавления узла — это дробление ячейки таблицы, а это значит, что добавленный узел перенимает на себя часть рёбер узла, который дробят.

В итоге, программа поймёт что необходимо объединить {5,6,9,10}. Также программа будет понимать, что узлы вставлены из шаблона, а значит в графе они объединены.

Коэффициент похожести рассчитывается так:

(Количество узлов — количество добавленных узлов — ошибки размеров ячеек)  + (количество рёбер узлов — количество добавленных рёбер, не инцедентных добавленным узлам + количество рёбер добавленных узлов))/(Количество узлов +Количество рёбер)*100

В данном случае: ((16 — 3  — 0) + (60 — 6 — 12))/(60+16) = 72

То есть на 72 % похожи.

Теперь на примере 2 графов из предыдущей статьи. Были такие графы:

Построили новый, получили такой.

 

Если провести расчет описанный выше для добавленных узлов здесь, то получится, что для преобразования шаблона в граф, нужно в шаблоне объединить узлы 4,5 и 6,9, что правильно. 2 графа похожи на 83%.

Данный метод не универсален, на мелких графах (менее 6 узлов) может давать ошибки. Так как знания математического аппарата теории графов недостаточно для обоснования, либо опровержения алгоритма, то, дать гарантий на то, что будет 100% работать на больших графах тоже нельзя. Скорее всего, есть какие-нибудь контрпримеры. Пока такого не встречал.