Esc (esc) wrote,
Esc
esc

  • Mood:

возвращение

С завтрашнего дня возвращаюсь в нормальный режим работы. Задача не завершена ещё, но ровно столько, сколько обещано боссу - сделано. За что я получил свои 3 отгула взамен 2-х отработанных выходных и ещё мне обещан вкусный ланч за счёт фирмы. Мням-ням, я уже загадал, куда я хочу пойти. Сегодня же я весь день просидел дома, отдыхая. Правда смог допинать провайдерщиков, и мне наконец починили интернет. Заменой модема.
Завтра опять вкалывать, хоть и менее интенсивно. Для тех, кому совсем нечего делать, я сейчас под катом попытаюсь обрисовать суть решаемой проблемы.

Наврал я. Это на самом деле я для себя сейчас напишу, на память. А то все позабыли, что дневник - это в первую очередь для себя. И только во вторую - рупор гласности. Но вы тоже читайте, если хотите. Но потом не жалуйтесь, что я вас не предупреждал о занудстве.
Если абстрагироваться от подробностей, то задача сводится к обработке графов. Я напрочь уже забыл всё, чему меня учили в МАИ, так что приходится изобретать велосипеды. Но я хотя бы в состоянии их изобретать, что ставит меня в выгодне положение. Ибо босс мой, инженер-нефтяник по образованию, не может и этого. Он долго бился над этой проблемой, пока не сдался и не перепоручил её мне.
Проблема босса в том, что он не в состоянии абстрагироваться от жизненных реалий. Он видел все эти нефтяные платформы и газовые заводы. Все эти incremental и recompletions для него не пустой звук, а реальные рабочие процессы. Для меня пустой, и поэтому я не могу даже перевести эти понятия на русский. По этой самой причине босс не в состоянии оторваться от земли и перейти в плоскость чистых математических моделей, чтобы решать проблему в ней. Моя же проблема обратная. Я витаю в облаках чистых понятий, и мне приходится клещами вытягивать из него всякие интимные подробности нефтяной жизни, которые по его мнению очевидны и озвучке не подлежат.
Итак, проблема сводится к построению ориентированного графа и поиску в нём всяких штук. Поначалу выглядело довольно просто и мило. Это потом уже полезли всякие уродливые подробности.
На первом этапе мы строим ориентированный граф на основании всяких там связей из базы. Затем нам нужно этот граф показать юзеру. Рисовать - не моя специальность, да и на самом деле работать с настоящим графом в графическом виде конечному пользователю неудобно. Особенно когда число узлов перевалило за сотню. Поэтому граф необходимо разбить на цепочки, которые уже можно показывать в виде древовидного списка. Первая проблема - циклы. Если у вас циклы в графе, то прости-прощай, дерево, и здравствуй, переполнение стека. Значит при посторении дерева надо постоянно бегать вверх по веткам и проверять, а не зациклились ли мы. Когда я справился с первой проблемой - вылезла вторая. А с чего начинать? Простое и естественное математическое решение начинать со всех узлов по очереди было немедленно забраковано ввиду всё той же невозможности обозрения сотни частично повторяющихся ветвей нормальным человеком, а тем более пользователем. Значит надо найти все узлы не имеющие родителей и начинать только с них. И тут снова вылезают циклы. Вот ты думал, что покончил с ними молодецким ударом, а они тут как тут. Лыбятся и корчат рожи из-за угла. С кого начинать в цикле? Если с произвольной точки, то как быть с пересекающимися и вложенными циклами? Как отследить все циклы одновременно, чтобы не запутаться, какие именно циклы мы разрешаем выбором данной конкретной точки, а какие остались в стороне? Да и надо ли выбирать внутри данного цикла что-то или мы приходим в него извне? Короче я не в курсе, как данная проблема решается в идеале, но я надумал обойти граф и убрать по одному ребру из каждого обнаруженного цикла. Таким образом граф перестаёт быть циклическим и задача нахождения стартовых вершин становится реальной. Дублирование веток при этом возможно, но в незначительных масштабах. Но как только стартовые вершины найдены, нам нужен обратно полный граф, чтобы корректно отобразить все связи. То есть фактически графов должно быть два. Я убил кучу времени в бесплодных попытках найти решение в одном графе, но так и не смог. И это был первый этап.
Второй этап, на который я собственно и угробил выходные, заключался в том, что в графе появлялись группы. Если взять и обвести несколько узлов графа в некую область, вот вам и будет группа. По-хорошему, группы не пересекаются. А по-плохому пересекаются. То есть один узел может принадлежать к нескольким группам и это ошибка. Слава Спящему, мне не пришлось ввязываться в этот кошмар и узел решено расматривать принадлежащим первой группе, заявившей на него свои права. Узлы внутри группы могут быть связаны, а могут быть и нет. Узлы также могут остаться свободными, то есть не принадлежащими ни к одной из групп. То есть полная анархия. И теперь уже необходимо искать получившиеся связи между группами. И циклы тоже. И дерево строить. Я долго боролся с желанием построить на основе этого графа ещё один, состоящий из одних групп. Потому что опять же хотел иметь один единый граф для разных этапов. Но все иные способы решения провалились один за другим. Этапы оказались абсолютно несовместимыми. Поэтому я сначала заменил узлы внутри каждой группы одним большим узлом, перенаправив на него все связи всех бывших членов. А затем вывел один за одним все свободные узлы, спрямляя проходившие через них рёбра. После этого второй этап делал практически всё тоже самое, что и первый, с незначительными отличиями.
На третьем же этапе, которым я займусь завтра, мне снова нужно вернуться к полному графу и построить в нем волну. То есть присвоить всем узлам некий ранг, так чтобы переход от узла к узлу всегда осуществлялся только в повышением ранга. Разумеется, треклятые неугомонные циклы для этого должны быть в последний раз разорваны. Группы при этом должны считаться как один узел, но внутри группы должна быть своя маленькая внутренняя волна. Безхозные же узлы уже никуда не пропадают, а участвуют в общем веселье наравне с группами. Я не знаю, как я это буду реализовывать, но как-то придётся.
Если вы честно прочитали всё до конца, то вы - маньяк. Сообщите мне об этом, мы подружимся. Я весь этот бред набивал 2 часа и времени уже полвторого ночи. Кто я, если не маньяк?
Subscribe

  • Dark age

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

  • маленькие радости возвращения

    Вернулся я в Калифорнию после 7 месяцев отсутствия. И сразу в бой. Хотя лучше бы на бал. В обеих машинах конечно же насмерть сдохли батареи. И…

  • Экскурс в заморскую политику

    Сегодня в городе Окланде состоялся приём меня в американские пионеры граждане. В связи с чем я ощутил острую необходимость проголосовать за…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 6 comments