Использовать библиотеку графиков / сетевую библиотеку узлов или написать свою собственную?

https://stackoverflow.com/questions/1499878

19-09-2019
|

Вопрос

Я пытаюсь решить, использовать ли готовую сетевую библиотеку graph / node или создать свою собственную.

Я реализую некоторые алгоритмы поиска по графу, которые могут потребовать некоторой существенной настройки структуры классов узла и / или ребер.

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

Есть ли кто-нибудь, кто имеет непосредственный опыт использования одной из существующих библиотек и может дать совет, основанный на истории успеха или неудачи?Я хочу услышать самое худшее, чтобы, что бы я ни выбрал, я знал, во что ввязываюсь.

Есть только два, которые я нашел в своих поисках на данный момент: Библиотека Boost Graph Library (BGL) и ГОБЛИН.Мы также высоко ценим конкретные рекомендации по любому из этих вопросов или предложения для других.BGL кажется чертовски загадочным.Стоит ли с этим бороться?

Решение

Возможно, я смогу дать небольшое руководство по BGL.

Библиотека очень гибкая.Цена этого заключается в том, что синтаксис может быть очень барочным, чтобы вместить все возможности.Однако он достаточно гибкий, чтобы простые вещи можно было делать просто.

К сожалению, документация boost идет полным ходом, предоставляя описание только всей сложности, без намека на то, насколько простыми могут быть вещи.

( "Любая достаточно продвинутая технология неотличима от магии" - Артур К.Кларк.То, что он должен был сказать, это "Любая передовая технология, достаточно плохо документированная, неотличима от магии)

Рассмотреть:

typedef property_map<Graph, vertex_index_t>::type IndexMap;
IndexMap index = get(vertex_index, g);
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
std::pair<vertex_iter, vertex_iter> vp;
for (vp = vertices(g); vp.first != vp.second; ++vp.first) {
   std::cout << index[*vp.first] <<  " ";
}

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

for (int v = *vertices(g).first; v != *vertices(g).second; ++v)
    std::cout << v << " ";

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

Иногда сложный синтаксис не может быть удален.(Или, возможно, я просто не заметил лежащей в основе истины ).Затем я обычно использую небольшую служебную функцию, чтобы инкапсулировать сложность и держать ее подальше от алгоритма, над которым я работаю.

Например, мне часто приходится перебирать дочерние элементы вершины

vector<int> getVertexChildren( int v )
{
    vector<int> vc;
    typedef std::pair<graph_traits<graph_t>::out_edge_iterator, graph_traits<graph_t>::out_edge_iterator> out_edge_iter_pair_t;
    for( out_edge_iter_pair_t ep = out_edges(v,m_tree);
        ep.first != ep.second; ++(ep.first))
    {
        vc.push_back( target( *ep.first, m_tree ) );
    }
    return vc;
}
#define FOR_ALL_CHILDREN( v ) vector<int> vc=getVertexChildren(v); BOOST_FOR_EACH( int child, vc )

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

Другие советы

“требуется некоторая существенная настройка структуры классов узла и / или ребер”.

Вы смотрели на функцию “объединенные свойства” в BGL?

http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/bundles.html

Это одновременно мощно и ни в малейшей степени неординарно.

Вы определяете классы для своих ребер и вершин

class cMyVertex
{
…
};
class cMyEdge
{
…
};

Теперь вы определяете тип графика, который будет использовать ваши классы

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    cMyVertex, cMyEdge > graph_t;

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

Вы можете получить доступ к атрибутам и методам ваших классов совершенно естественным способом

Graph_t g(10)       // create a graph with 10 vertices
g[1].setA1( “alpha” );  // invoke an accessor on node #1

Недавно я предоставил библиотеке boost graph пробную версию для решения задачи о кратчайшем пути Дейкстра.Результаты:

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

Совет: Используй это но прежде чем вы это сделаете Читать Библиотека Boost Graph (Ускоряющий график):Руководство пользователя и Справочное руководство

Я думаю, если вы можете использовать алгоритмы обхода графика, стоит использовать Boost Graph.Создавать и использовать пользовательские вершины довольно просто.Примеры, включенные в BGL, были полезны для изучения того, как им пользоваться.

Я согласен с Клиффордом, я использовал GraphViz для визуализации графика во время разработки и нашел его очень полезным.

Вы также можете попробовать с ЛИМОННЫЙ библиотека графиков.

Я мог бы использовать его для выполнения поиска кратчайшего пути Dijsktra после считывания графика из файла конфигурации.

Только что вышла новая версия.

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

Решение этой проблемы зависит от контекста проблемы.Если вы хотите получить полное представление о том, как работают графические алгоритмы и программное обеспечение.Напишите свой собственный.Если вы хотите получить углубленные знания об алгоритмах и структурах графов или внедрить их в свою собственную программу, тогда изучите стандартную библиотеку графов.(Смотрите причины использования повторно используемого кода)

Лучшее из обоих миров.Делай и то, и другое.Если у вас мало времени, возьмите книгу по этому вопросу или следуйте руководствам и примерам.

Еще одно предложение:Задайте новый заостренный вопрос о том, какова {лучшая, наиболее надежная, простая в освоении} библиотека графов для {описания очень общей проблемы}?Это поможет вам выбрать, чему учиться, вместо того чтобы пытаться наугад найти то, что лучше всего соответствует вашим потребностям.Кто-то уже видел эту проблему, попросите совета.

Использование повторно используемого кода:

Код, написанный кем-то другим, включая тестовые примеры, как правило, будет более надежным, чем ваш собственный.
Исправления проще внедрять (с обновлениями компонента, который вы используете повторно), это верно в Boost (поскольку они выполняют частые обновления, и этот Boost проходит экспертную оценку).
Как только вы изучите один фреймворк, вы сможете применить его к другим приложениям...кто знает, возможно, вы позже устроитесь на работу, используя фреймворк.Компаниям нравится использовать велосипед повторно, а не изобретать его заново.

Я свернул свой собственный.Вам не следует следовать этому примеру, если вы не абсолютно уверены, что вам это нужно.

Тем не менее, это отличный опыт обучения, если вы устали от теории графов.

Мне было очень "весело" комбинировать орграфы с использованием операторов EBNF и выполнять исключение эпсилона и минимизацию на основе Хопкрофта.Особенно с минимизацией, если вы можете назвать "забавой" отчаянные попытки найти хорошую информацию и выяснить, как это работает :-(

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

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

Кроме того, иногда вы просто хотите работать с вещами, которые не были явно разработаны как орграф IYSWIM - напримернабор узлов структуры данных, которые связаны друг с другом.

IOW, полезно иметь возможность подключать различные представления орграфов, но при этом использовать одни и те же высокоуровневые инструменты для многих операций.

IMO я понял это правильно, когда написал класс 'tree tool', который выполняет такие вещи, как итерация и подписка в порядке просмотра дерева и в порядке тегов XML-элементов.Базовое древовидное представление является подключаемым (шаблон на основе политики).С орграфами я напортачил.

В любом случае, я не знаю, что на самом деле предоставляет Boost или любая другая библиотека graph, но если она предоставляет то, что вам нужно, я советую использовать ее.Это избавит вас от множества головных болей.

Прежде чем принять решение о создании вашей собственной библиотеки графиков, я бы внимательно посмотрел на igraph (http://igraph.sourceforge.net/).Он написан на C, чрезвычайно быстр и предлагает более широкий спектр базовых и продвинутых графических алгоритмов (включая визуализацию).Кроме того, у него есть оболочка python для быстрого кодирования, поэтому я думаю, что это решение сочетает в себе скорость кодирования и скорость выполнения.

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

LEMON предлагает все это, а также имеет более простой синтаксис, что меня беспокоит в LEMON, так это проблемы с установкой и компиляцией на платформах WINDOWS, но я, вероятно, переключусь на LEMON, несмотря на эти проблемы.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow