Графический интерфейс C / C ++ для представления частичного порядка
В моем коде я использую класс, который представляет направленный ациклический граф. Я сам написал код, это было не сложно. Но позже я понял, что мое приложение предъявляет больше требований: график должен быть транзитивно-сокращенным, то есть уникальным представлением частичного ордера. Каждый раз, когда пользователь выполняет перетаскивание или вырезание / копирование / вставку графического представления графического интерфейса пользователя, его необходимо проверять и адаптировать к этому требованию. Теперь все становится сложнее. Поэтому я планировал, как безопасно выполнять все операции с графами и т. Д., Но прежде чем я действительно углублюсь в код, я хотел бы знать:
Есть ли известный интерфейс C / C ++ для частичных заказов? (Предпочтительно C ++)
Я нашел много библиотек для графиков, но у меня уже есть мой простой ациклический код орграфа. Я не смог найти ничего, что конкретно касалось бы графов с транзитивным сокращением (мне не нужна матрица смежности, данные поступают от пользователя, поэтому здесь это будет неэффективно … Это небольшой график для пользовательских данных, а не что-то для математическое использование)
Я ищу интерфейс, который автоматически обнаруживает ненужные соединения и удаляет их, выполняет тесты, чтобы увидеть, будет ли операция копирования / перемещения узла действительной в частичном порядке, то есть сохранить свойства частичного порядка и т. Д.
Решение
Я бы рекомендовал добавить метод проверки частичного заказа. Когда редактирование выполняется, сделайте копию всего графика, примените редактирование к одной копии, а затем подтвердите ее. Если это пройдет, сохраните измененную копию. Если это не пройдет, вернитесь к сохраненной копии.
Возможно, валидатор мог бы найти все нижние узлы для каждого из них, построить мультимножество своих предков (или потомков, если вы их так называете) и проверить наличие дублирующих записей. Я бы вернулся к рекурсии для поиска, если вы ожидаете только небольшие графики.
Другие решения
Насколько я знаю, обычно программы имеют свои собственные графовые классы, когда они используются в нематематических целях. Это происходит потому, что графики могут быть намного сложнее, чем линейные контейнеры, такие как контейнеры STL (вектор, список и т. Д.).
Поскольку у вас нет особых потребностей в области математики или алгоритмов (алгоритм поиска в вашем случае был бы простым циклом, в большинстве случаев вам не нужно больше, и, конечно, в случае (преждевременного ) оптимизация). Если вы это сделаете, у вас есть boost :: graph, но я подозреваю, что это усложнит ситуацию больше, чем поможет вам.
Поэтому я говорю: напишите хороший класс графа / узла, и если он достаточно хорош и написан для общего назначения, мы все можем извлечь из этого пользу. Никто не отвечает на вопрос, потому что на самом деле не существует общедоступного кода, соответствующего вашим потребностям. Напишите хороший код libre один раз, и он может быть использован везде. Удачи.
P.S Ваш собственный алгоритм поиска может быть намного быстрее, чем написанный для библиотек графов общего назначения, например, boost :: graph, потому что вы можете воспользоваться преимуществами известных ограничений и правил вашего конкретного графа, тем самым делая поиск намного быстрее. Например, в графе с транзитивным сокращением, если A является родителем B, то A также не может иметь b в качестве не дочернего потомка (например, grand-child), поэтому вы можете оптимизировать свой поиск, используя эти знания. Ценой, которую вы платите, является множество тестов при смене графика, но вы получаете большую отдачу, потому что поиск / сканирование может стать намного быстрее.