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