Вопрос
На направленном ациклическом графе (DAG) будет ли всегда предотвращаться циклическое транзитивное отношение, вызванное добавлением отношения, путем инвертированияотношение, которое будет добавлено?
Пример:
- Существующие отношения:
A -> B, B -> C, и тем самым переходное отношение A -> C, поэтому его можно рассматривать как A -> B -> C - Отношение будет добавлено:
C -> A, что приведет к A -> B -> C -> A и будет циклическим - Идея : инвертировать отношение, которое будет добавлено к
C <- A, котороеприведет к A -> B -> C <- A и, таким образом, все еще будет ациклическим
Пример, приведенный здесь, конечно, довольно прост, поэтому мне интересно знать, будет ли такой подход жизнеспособным во всех сценариях.
Фон
Для моделирования направленных отношений (например, «следует», «предшествует», «родитель», «потомок») между объектами хранилища приложений OpenProject информация об отношениях в направленном ациклическом графе (DAG) .Объекты / узлы имеют информацию о дате и могут быть перепланированы пользователем.Если пользователь изменяет значения даты, другие сущности, возможно, должны быть перепланированы автоматически, например, когда предшественник перенесен на два дня в будущее, его преемник также должен быть перенесен.
Поскольку большинство отношений используются для планированияи, поскольку именно по этой причине это ациклический граф, циклы предотвращаются.Они могут привести к бесконечным циклам планирования.
Хотя большинство отношений также имеют направление с семантической точки зрения, существует также общее отношение «относится к», которое для пользователя является ненаправленным и просто сообщает, чтоесть отношение сортов.Из-за своего характера аспект направления «относится к» отношениям, присутствующим в DAG, не виден пользователю во внешнем интерфейсе.
Когда пользователь пытается создать отношение «относится к», он может в настоящее времястолкнуться с сообщениями об ошибках, предупреждающими о циклических отношениях, что непонятно для пользователя, поскольку его восприятие отношения является ненаправленным.
Существует несколько возможных решений этой проблемы, и самым простым может быть просто обратноеотношение в таких случаях, как направление в DAG, не будет иметь значения для пользователя для такого отношения.