Поиск содержащихся граничных областей из импорта Excel

Question

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

Установка данных:
Я импортирую непосредственно из Office Open XML с использованием VB6 и MSXML. Данные анализируются из XML в словарь данных сот. Это замечательно и так же быстро, как использование docmd.transferspreadsheet в Access, но дает гораздо лучшие результаты. Каждая ячейка содержит указатель на элемент стиля, который содержит указатель на элемент границы, который определяет видимость и вес каждой границы (так же структурируются данные внутри OpenXML).

Задача:
Что я пытаюсь сделать, это найти каждый регион, который заключен внутри границ, и создать список ячеек, находящихся внутри этого региона.

Что я сделал:
Первоначально я создал процедуру заполнения BFS (ширина первого поиска), чтобы найти эти области. Это работает прекрасно и быстро для «обычных» размеров таблиц, но слишком медленным для импорта в тысячи строк. Одна из проблем заключается в том, что граница в Excel может быть сохранена в проверяемой ячейке или противоположной границе в соседней ячейке. Это нормально, я могу консолидировать эти данные по импорту, чтобы уменьшить количество необходимых проверок.

Одна вещь, о которой я думал, заключается в создании отдельного графика, который отображает ячейки, использующие границы в качестве моих ребер, и используя алгоритм графа, чтобы найти области таким образом, но мне трудно понять, как реализовать алгоритм , Я использовал Dijkstra в прошлом и думал, что смогу с этим справиться. Таким образом, я могу рассчитывать без использования конечной точки для поиска по всему графику, и если я столкнулся с закрытым узлом, я знаю, что я только что нашел замкнутую область, но как я могу узнать, является ли найденный мной маршрут оптимальным? Думаю, я мог бы отметить, что для выполнения отдельной проверки для найденного закрытого узла предыдущему узлу игнорируется это одно ребро.

Это может сработать, но на плотных графах это будет не намного лучше. Может ли кто-нибудь предложить лучший метод? Спасибо, что нашли время, чтобы прочитать это.

Answer 1

Ваш вопрос довольно сложный, но кажется, что вам нужен алгоритм для поиска связанных компонентов графа (подключенный компонент = набор узлов, все соединенные друг с другом, но не с любыми другими узлами), что может быть выполнено в линейном времени с помощью повторных обходов. Псевдокод:

FindComponents(G): 
    For all vertices v in G: 
     Let C be a mutable empty collection 
     Traverse(G, C, v) 
     If C is nonempty, then it is a connected component 

Traverse(G, C, v): 
    If v has not been visited: 
     Mark v as visited 
     Add v to C 
     For each neighbor w of v in G: 
      Traverse(G, C, w) 

итерационный вариант Traverse:

Traverse(G, C, r): 
    Let S be an empty stack 
    Push r onto S 
    While S is not empty: 
     Pop the top element v of S 
     If v is not marked as visited: 
      Mark v as visited 
      Add v to C 
      For each neighbor w of v in G: 
       Push w onto S