1. Oleg Sychev Avatar Oleg Sychev
  2. POAS Moodle plugins
  3. Moodle Plugins
  4. Issues

Переход автомата на матрицу смежности

Issue #210 closed
Former user created an issue

Originally reported on Google Code with ID 210

Возник вопрос по поводу обработки некоторых ситуаций при переходе на матрицу.

Reported by eklepilkina on 2013-07-18 16:22:08

Comments (28)

  1. Oleg Sychev repo owner 
    Очень конкретный вопрос....

    Reported by oasychev on 2013-07-18 16:56:07

  2. Former user Account Deleted 
    Насчет матриц вопрос такой. Матрица у нас двумерная, чтобы ее такой сохранить мы переходы
между одними и теми же вершинами должны объединять. Это хорошо будет работать, если
оба перехода захватытвают символы, но в таких случаях, я не знаю как правильно объединить.
1. 0->1 [label = ab];
   0->1 [label = ^];
Если идем по первом захватываем по второму нет. Если записать как ^ab, то изменим автомат,
потеряем путь без захвата да и получится, что символы только в начале строки должны
бытью Аналогичные случаи
2. 0->1 [label = ^ab];
   0->1 [label = $cd];
3. 0->1 [label = ab];
   0->1 [label = ^cd];(при мержинге может вполне получится)
4. Тоже с тегами
0->1 [label = (ab)];
   0->1 [label = сd];

    Reported by eklepilkina on 2013-07-18 17:16:13

  3. Oleg Sychev repo owner 
    Пока решено сливать переходы в ДНФ если они одинаковой длины и без тегов (с одинаковыми
тегами), иначе добавлять вершину (либо сделать массив в матрице, если это окажется
меньше памяти - проверить юнпит-тестом на матрице 20х20 например).

    Reported by oasychev on 2013-07-19 12:52:04 - Labels added: Component-Preg

  4. Former user Account Deleted 
    Проверили, выгодней добавлять вершину.

    Reported by eklepilkina on 2013-07-19 18:09:48

  5. Former user Account Deleted 
    Вопрос по работе функции intersect в charset, о которой я вам говорила.
Я ее решила протестировать и, по моему, там не правильный результат.
Тест: первый charset содержит поле флагов в виде массива
 array(1) {
  [0] =>
  array(1) {
    [0] =>
    class qtype_preg_charset_flag#10643 (3) {
      public $negative =>
      bool(false)
      public $type =>
      string(21) "enumerable_characters"
      public $data =>
      class qtype_poasquestion_string#10642 (2) {
        ...
      }
    }
  }
}
и поле data хранит "abc"
второй charset содержит поле флагов в виде массива
array(1) {
  [0] =>
  array(1) {
    [0] =>
    class qtype_preg_charset_flag#10632 (3) {
      public $negative =>
      bool(false)
      public $type =>
      string(21) "enumerable_characters"
      public $data =>
      class qtype_poasquestion_string#10633 (2) {
        ...
      }
    }
  }
}
и поле data хранит "a"
А результатом функции является объект с массивом
array(1) {
  [0] =>
  array(2) {
    [0] =>
    class qtype_preg_charset_flag#10643 (3) {
      public $negative =>
      bool(false)
      public $type =>
      string(21) "enumerable_characters"
      public $data =>
      class qtype_poasquestion_string#10642 (2) {
        ...
      }
    }
    [1] =>
    class qtype_preg_charset_flag#10632 (3) {
      public $negative =>
      bool(false)
      public $type =>
      string(21) "enumerable_characters"
      public $data =>
      class qtype_poasquestion_string#10633 (2) {
        ...
      }
    }
  }
}
где data элемента [0][0] "abc", а [0][1] "a". По моему должно быть не так. Я ожидала
результата, чтобы в массивах был один элемент и в нем хранился "a"(простое пересечение
"abc" и "a" ="a"), т.е. array(array("a")). А то что там сейчас хранится по моему простой
аналог "abc".
Я ошибаюсь?

    Reported by eklepilkina on 2013-07-20 12:30:08

  6. Former user Account Deleted 
    Я поняла, что там правильно все работает,только мне нужно добавить туда анализ флагов,
связанных конъюнкцией.

    Reported by eklepilkina on 2013-07-22 04:55:30

  7. Oleg Sychev repo owner 
    ДНФ не оптимизируется (ее судьба вообще под вопросом, так что пока не стоит отнимать
время ее улучшением - как раз ваш код должен показать, нужна ли она вообще, или стоит
сразу все в отрезки переводить), оптимизация происходит при переводе в отрезки (ranges)
- там реализовано эффективное объединение/пересечение.

Единственно, не обманывайтесь наличием флагов ДНФ для простых ассертов крышки/доллара
- они скорее всего не будут работать - раньше они никогда туда не попадали...

    Reported by oasychev on 2013-07-22 11:58:24 - Status changed: Accepted - Labels added: Type-Task - Labels removed: Type-Defect

  8. Oleg Sychev repo owner 
    Валерий, добавляю вас сюда - тут обсуждался важный для матрицы вопрос.
Когда из одной вершины в другую ведут две дуги, одна из них ассерт или тег (без захвата
символа), другая с захватом - это в матрицу не лезет, было решено завести дополнительную
вершину в таком случае.

Других проблем с матрицей вроде нет.

P.S. Я правильно понимаю, что крышка и доллар во флагах не работают на самом деле?
В ranges их не переведешь...

    Reported by oasychev on 2013-07-25 19:57:05

  9. Valeriy Streltsov 
    Читал-читал, так и не понял суть проблемы. Что значит "в матрицу не лезет"? Зачем дополнительные
вершины?

Крышка и доллар во флагах не работают, да.

    Reported by vostreltsov on 2013-07-31 12:36:26

  10. Former user Account Deleted 
    А как сделать без дополнительных вершин, чтобы оставить матрицу двумерной?

    Reported by eklepilkina on 2013-07-31 17:29:44

  11. Valeriy Streltsov 
    Она обязательно должна быть двумерной? Мне кажется, что массив переходов на пересечении
строки\столбца - вполне нормальный, трехмерный вариант.

    Reported by vostreltsov on 2013-07-31 18:05:01

  12. Former user Account Deleted 
    Нет, не обязательно. Это с Олегом Александровичем решите. Пока метод добавления переходов
при наличии уже имеющегося перехода и наличии возможности сливает добавляемый переход
с имеющимся. Если нет создает аналог вершины и туда добавляет переход. Пока так.

    Reported by eklepilkina on 2013-08-01 04:55:03

  13. Valeriy Streltsov 
    1. Сделать нормальный интерфейс у класса автомата - функции добавления переходов, создания
состояний и т.д., а также получения списка переходов, входящих/исходящих из состояний.
2. Переделать построение и матчинг НКА на новый формат.

    Reported by vostreltsov on 2013-08-17 14:16:59

  14. Oleg Sychev repo owner 
    1 я бы разделил на два пункта:
1.1 прописать сам интерфейс, т.е. выверить заголовки функций - это явно Стрельцов
1.2 реализация - тут обсуждаемо

    Reported by oasychev on 2013-08-17 14:32:20

  15. Valeriy Streltsov 
    Интерфейс (пишу в c-style для понятности):

1) int add_state() - возвращает номер добавленного состояния

2) qtype_preg_transition add_transition(int from, int to, qtype_preg_node node) - создает
переход from->to с узлом node

3) list<qtype_preg_transition> get_adjacent_transitions(int state, bool outgoing, bool
incoming) - возвращает смежные со state переходы. два флага указывают нужно ли брать
исходящие и входящие дуги (т.е. при false false получится пустой массив, при true true
все-все-все смежные переходы)

Пока вроде всё.

    Reported by vostreltsov on 2013-08-29 07:43:13

  16. Oleg Sychev repo owner 
    Гм, Валерий. Не лучше создать заголовки дело в коде - завести отдельный клон для 2.6
и прописать к ним хорошие PHPDoc комментарии (а здесь просто перечислить функции)?
Там и тип указывается, и все прочее...  И всем удобнее. Я обычно делаю именно так.

Пока даже непонятно, в каком классе вы хотите их иметь - автомата?

    Reported by oasychev on 2013-08-29 08:47:44

  17. Oleg Sychev repo owner 
    Issue 207 has been merged into this issue.

    Reported by oasychev on 2013-08-30 20:17:04

  18. Oleg Sychev repo owner 
    К списку функций добавляется
4) draw - переводит автомат в DOT, ей тоже понадобится измениться под матрицу...

    Reported by oasychev on 2013-09-05 15:55:34

  19. Oleg Sychev repo owner 
    Было решено в функции get_adjacent_transitions оставить один bool параметр, который
бы указывал входящие или исходящие переходы возвращать. И я так понимаю номера второго
узла перехода будут ключами...

Елена, подправьте тогда свои функции и опишите здесь что есть, чтобы Валерий мог оценить,
насколько этого достаточно.

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

    Reported by oasychev on 2013-09-06 13:02:41 - Labels added: Type-Enhancement, Priority-High - Labels removed: Type-Task, Priority-Medium

  20. Former user Account Deleted 
    Поправила. Как сейчас.
1. int add_state($realnumber)
2. add_transition($transition). Пока готовый, если надо в разборном виде сделаю, просто
передавать помимо 4 необходимых параметров еще 4 массива с тегами....по моему многовато,
но как скажете.
3. list<qtype_preg_transition> get_adjacent_transitions($state, bool isoutcoming)
4. draw в старой версии отрисовывало картинку через dot. Ее не трогала, осталась write_fa,
возвращающая строку в формате dot теперь используя userinscriptions.Если надо переименую.
Вроде все.

    Reported by eklepilkina on 2013-09-07 13:18:30

  21. Oleg Sychev repo owner 
    Я думаю, можно слегка подправить write_fa:
1) сделать интерфейс аналогичный draw - получить тип файла и его имя, и сохранить картинку
туда, используя type_preg_regex_handler::execute_dot
Единственно, я бы сохранил поведение execute_dot: сделал $filename=null по умолчанию,
и если имени файла нет то вернул результат работы ДОТа из функции; бывает полезно для
пересылки на компьютер клиента;
2) переименовал в write_fa_to_dot или просто fa_to_dot - чтобы было из названия четко
видно формат
3) grep'ом поискал вызовы draw для автомата (только убедитесь, что это автомат) - они
возможны в каталоге tests - и исправил на новую функцию; старой - draw - написать в
комментах перед функцией (PHPDoc комментарии) @deprecated since 2.5 - чтобы удалить
ее в следующей версии...

    Reported by oasychev on 2013-09-07 14:00:00

  22. Former user Account Deleted 
    Исправила. Сделала также и первый параметр тип картинки по умолчанию равным null для
того, чтобы при отсутствии необходимости рисовать картинку можно было просто получить
строку с описанием, как мне требуется в тестах.

    Reported by eklepilkina on 2013-09-08 06:23:12

  23. Oleg Sychev repo owner 
    Лена, если $filename=null то execute_dot возвращает файл как переменную, ее надо вернуть
и из fa_to_dot. 
Поэтому я бы написал
if ($type != null) {
    $result = qtype_preg_regex_handler::execute_dot($result, $type, $filename);
}

    Reported by oasychev on 2013-09-08 09:53:49

  24. Former user Account Deleted 
    Да, не досмотрела.

    Reported by eklepilkina on 2013-09-08 11:55:43

  25. Valeriy Streltsov 
    unite_leafs не работает. Внутри есть вызов некого has_equal_tags, которого а) нигде
нет б) узлы ничего не должны знать про теги - это автоматная сущность

Насколько я понимаю, этот метод вообще не нужен - достаточно unite(). Или по крайней
мере создать метод unite() у preg_fa_transition, который будет вызывать unite() для
своих pregleaf'ов и потом сам объединять массивы тегов.

    Reported by vostreltsov on 2013-11-01 13:18:41 - Status changed: InProgress

  26. Oleg Sychev repo owner 
    Что у нас обстоит сейчас по этому issue? Валерий - последние замечания были исправлены
Леной или все еще нет?

    Reported by oasychev on 2014-07-10 18:20:41

  27. Oleg Sychev repo owner 
    Валерий, Лена - алло, это issue готово и можно закрыть или что-то осталось?

    Reported by oasychev on 2014-12-03 00:35:04 - Status changed: Fixed

  29. Log in to comment
Assignee
Type
enhancement
Priority
major
Status
closed
Component
–
Votes
0
Watchers
0
Jira: the preferred issue tracker for Bitbucket. Join the team!