Простая библиотека C/C++ для управления сетевым графиком

В настоящее время я работаю над исследовательским проектом, в котором используется проприетарное программное обеспечение. Я пытаюсь заменить проприетарные библиотеки C для представления графа. Это облегчит перенос нашего проекта на открытую платформу и сделает его доступным для всех бесплатно.

В проекте смешаны C и C++, поэтому, если мы собираемся внедрить библиотеку C, она должна прекрасно сочетаться с C++.

Текущие библиотеки используют указатели для всего и приведения типов для хранения и извлечения данных . void*

Это позволяет довольно легко:

  • добавлять и удалять вершины
  • добавлять и удалять ребра
  • получить список с ребрами вершины
  • получить список с соседями узла
  • расчет компонентов связности
  • рассчитать кратчайшие пути (используя Dijkstra )

Вершины имеют тип PrgT_Graph_Vertex*и могут иметь связанный void*указатель для хранения связанной информации. Аналогичная логика используется в отношении ребер. Вот конкретный пример .

Замена должна иметь лицензию, не обеспечивающую авторское лево, поэтому она не может быть GPL. С лицензиями в стиле BSD все в порядке.

Библиотека Boost Graph , теперь BGL, имеет лицензию OK и является частью известного пакета. Тем не менее, его документация фрагментарна и выглядит так, как будто она была «залатана» воедино, а не продуманно «построена». Удаление вершин кажется непростым делом, так как это может испортить индексы вершин.

Библиотека Lemon Graph имеет ту же лицензию , что и BGL, выглядит проще, но не так активно поддерживается (см. дорожную карту ).

У Stanford SNAP есть лицензия OK , у нее самый красивый веб-сайт, но документации очень не хватает.

iGraph не подходит, потому что он находится под лицензией GPL . Кроме того, насколько я понимаю, для C++ потребуется использовать оболочку.

Network Graph Toolkit , разработанный NIST, выпущен в общественное достояние, но не похоже, что он вообще документирован (кроме комментариев к коду).

BGL, похоже, дает наилучшие гарантии того, что он будет активно развиваться. Но это также довольно далеко от моей текущей логики реализации и займет много времени только для того, чтобы начать.

Любое предложение?

В BGL вы можете "удалить" вершины дешевле, используя этот фильтрующий адаптер, который у них, по-видимому, есть - вершины просто помечаются как удаленные (и иногда вам приходится повторно консолидировать граф).
Если вы знаете BGL и хотите получить репутацию, посмотрите мой вопрос на SO.
На самом деле я плохо знаю BGL; Я работал в группе, в которой кто-то еще был парнем, занимающимся представлением графов, и он жаловался на то, что BGL был таким, а BGL был таким...
На это действительно есть на что пожаловаться. Нашел ли он более интуитивную библиотеку?
Мы уже были слишком увлечены этим и слишком заняты другими делами, чтобы он действительно пытался заменить это. Насчет "на что жаловаться" - у вас есть ссылка на место, где это жалуется? То есть обсуждает недостатки БГЛ?
Вас перекинуло на главную страницу. Вы когда-нибудь находили решение?
Не совсем. Я перенес свой проект из лоскутного одеяла функций C на Python + NetworkX. Ничто в этом списке даже не сравнится с ним с точки зрения документации. Я изучил Python с помощью этой библиотеки.
График LEMON сохраняется, даже если он не имеет недавней версии. Я считаю, что это очень хорошая и современная библиотека C++, которая разработана так, чтобы ее было легко использовать и понимать (в отличие от BGL, который представляет собой разочаровывающий перепроектированный беспорядок, на который я всегда трачу слишком много времени).
igraph является самым простым в использовании. Он имеет интерфейс C, что означает, что ему не нужна какая-либо оболочка для использования из C++ . Но да, это GPL.

Ответы (2)

Я полагаю, что уже слишком поздно помогать оригинальному плакату, но, поскольку этот вопрос появился в списке «Горячие вопросы сети», вот рекомендация.

Библиотека STLPlus активно поддерживается и имеет хорошую реализацию ориентированного графа . Он доступен под лицензией BSD. Есть форум, мейнтейнер обычно отвечает в течение пары дней и открыт для предложений/доработок.

Ответ кажется настолько очевидным, что я боюсь, что неправильно понял вопрос.

Конечно, ничто не сравнится с Graphviz? Он существует всегда, активно поддерживается и имеет большую поддержку.

Мне это нравится, потому что он принимает обычный текстовый ввод, который я могу генерировать из своих данных самых разных форматов.

Этот

graph { 
    a -- b; 
    b -- c; 
    a -- c; 
    d -- c; 
    e -- c; 
    e -- a; 
}

производит это

введите описание изображения здесь

Не нужно связывать его с вашей программой, просто запустите его как команду оболочки из своего приложения.

Это то, что вы подразумеваете под графом сети?

введите описание изображения здесь

Смотрите еще много здесь и здесь .

Или я неправильно понял?

Я подозреваю, что GraphViz предназначен для рисования сетевых графов, а не для их построения и применения алгоритмов для анализа их свойств, верно?
Да, это так. Я неправильно понял? Разве это не то, что вы ищете?
Да, под «графическим представлением» я имел в виду «построение внутренней структуры». Я понимаю, как это может ввести в заблуждение. Мне нужны библиотеки для анализа графов и манипулирования ими. Подумайте о расчете показателей центральности и кратчайших путей. Тем не менее, ваш ответ предоставляет отличный инструмент для визуализации графика.
О! Я такой глупый. Но я рад, что вы (и другие), возможно, узнали об очень полезном инструменте. Взгляните на галерею , чтобы увидеть, как много он может сделать. Надеюсь, вы получите реальный ответ, хотя ;-)
Простая библиотека C/C++ для управления сетевым графиком
СпросиСетьПолитика конфиденциальности1y, 0v