Нечто, связанное с ГРАФами...

Тема в разделе "WASM.A&O", создана пользователем KeSqueer, 2 дек 2008.

  1. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Помогите осознать, что это такое :)

    Есть массив из 672 бит. Массив цикличный.
    Есть операции над такими массивами:
    CalculateDuration: вычисляет число не равных нулю битов (или сумму битов) и умножает на 15.
    Duration: если на входе 0, возвращает 10080 (672*15), в противном случае - CalculateDuration().
    MaxUnavailable: вычисляет максимальное расстояние в битах между двумя наиболее удаленными взведенными битами в этом масиве, между которыми остальные биты равны нулю, и умножает на 15. (Помним, что массив цикличный).
    Compare: сравнивает два массива. Оба массива представляются в виде 672-битных чисел и просто сравниваются - больше/меньше/равно.
    GetAlways: возвращает 0.
    CreateAlways: создает массив, в котором все биты равны 1.
    CreateDefault: на вход поступает число X, на выходе - массив, заполняемый по следующему принципу: все биты нулевые, кроме битов с индексами i*(X+14)/15 при целых i от нуля и увеличивается до тех пор, пока i*(X+14)/15 не будет больше или равно размеру массива (672).
    Merge: принимаются два указателя на два массива. Если один равен нулю, возвращается второй (и наоборот) и выставляется флаг результата = FALSE. Если обе ссылки ну нулевые, создается третий массив, равный поразрядному логическому "И"(&) двух исходных массивов. Флаг результата устанавливается в TRUE, если полученный массив имеет хотя бы один ненулевой бит, из функции возвращается созданный массив.

    Эти операции связаны, возможно слабо, с алгоритмами на графах.
    Compare используется для сортировки таких массивов в дереве.
    Duration каким-то образом используется в процедуре на алгоритме Дейкстры и в процедуре сравнения двух ребер. Обе эти процедуры используются в функции поиска минимального остового дерева (либо ребер графа, на котором строится дерево - не разобрался до конца).
    Остальные функции видимо нужны для внешнего использования, и, скорее всего, результаты некоторых из них передаются в процедуру поиска МОД (либо его ребер, хз).

    -----
    Для тех кто знает, что такое графы, можете предположить что можно с помощью этого соорудить?
    Кстати, 672-битный массив называется Schedule. В переводе с английского, на сколько мне известно, это что-то вроде графика/расписания или ?разложения како-го нибудь ключа на составляющие?. Может есть другие значения, но из этих двух разве что расписание можно хоть как-то прикрутить к графам...

    Тема для меня очень интересна, буду сильно рад, если кто-нибудь догадается до смысла:) ; мои силы на исходе ;-(
    Есть вопросы - пишите.
     
  2. AndreyMust19

    AndreyMust19 New Member

    Публикаций:
    0
    Регистрация:
    20 окт 2008
    Сообщения:
    714
    Что тут осозновать - ты и так вроде бы все рассказал?
     
  3. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Спасибо, что поднял тему, может кто-нибудь все же дойдет до ответа.
     
  4. Pavia

    Pavia Well-Known Member

    Публикаций:
    0
    Регистрация:
    17 июн 2003
    Сообщения:
    2.409
    Адрес:
    Fryazino
    Merge - поиск циклов в граффе. Для этого используется циклический список и два указателя.
     
  5. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Не совсем понимаю как это, можете чуть разъяснить?