Использовать библиотеку Graph Library / Node Network Library или написать мне?

16

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

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

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

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

В моем поиске пока есть только два: Библиотека Boost Graph (BGL) и GOBLIN . Особо ценятся конкретные рекомендации по любому из этих вопросов или предложения для других. BGL кажется довольно чертовски тайным. Стоит ли бороться?

    
задан Catskul 30.09.2009 в 20:29
источник
  • Boost, известное своим качеством в целом, и BGL-интерфейсы с GraphViz. –  Clifford 01.10.2009 в 19:08
  • @ Клиффорд прав - не стоит недооценивать силу возможности использовать GraphViz - это абсолютно потрясающе. –  DaveParillo 16.10.2009 в 00:24

9 ответов

24

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

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

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

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

Рассмотрим:

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, чтобы вы могли видеть, что вы кодируете.

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

Например, мне часто нужно петлю над дочерними элементами вершины

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. Это может быть упрощено, чтобы делать простые вещи, но как только вы научитесь использовать его, вся огромная гибкость будет доступна всякий раз, когда вам это нужно.

    
ответ дан ravenspoint 03.10.2009 в 20:00
  • Каков ваш опыт в отладке? У меня есть страх, что отладка с BTL может стать кошмаром. –  Catskul 05.10.2009 в 17:10
  • Кроме того, вы пробовали написать для него новые функции? Я смотрю на dijkstra_shortest_paths.hpp в качестве примера, и я поражен тем, насколько он загадочен: / –  Catskul 05.10.2009 в 17:14
  • Отладка сложнее, чем домашний код. Мой отладчик (MSVS2008) не может проникнуть в глубокие структуры данных, используемые BGL. Тем не менее, вы получаете намного меньше ошибок, чем с домашним пивом. Я не добавил новые функции для BGL. –  ravenspoint 05.10.2009 в 19:08
  • (+1) для комментария к комментарию Артура Кларка. –  Pratik Deoghare 16.10.2009 в 08:43
8

"требуют некоторой значительной настройки для структуры класса узла и / или ребер."

Вы рассматривали функцию «связанных свойств» BGL?

Ссылка

Это мощный и не самый маленький бит acrcane.

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

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
    
ответ дан ravenspoint 09.10.2009 в 21:18
  • +1 для намека на связанные свойства - они действительно облегчают многое для многих распространенных случаев использования. –  Steffen Opel 13.10.2009 в 01:46
8

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

  • Очень высокая производительность

  • Очень маленький необходимый код

  • Очень гибкий и расширяемый

  • Трудно понять или отладить

Совет: Используйте его , но прежде чем вы это сделаете прочитайте Библиотека Boost Graph: руководство пользователя и справочное руководство

    
ответ дан RED SOFT ADAIR 13.10.2009 в 10:57
  • Не слишком удивительно - это в основном общая история с стандартной библиотекой C ++, которую Boost стремится расширить. –  Steve314 15.10.2009 в 00:47
  • Я бы, конечно, не согласился сказать, что STL трудно понять или отладить. Сам STL является прямым, очень четким и даже разумным для отладки. boost :: graph - нет. boost :: spirit (библиотека парсера) еще хуже. –  RED SOFT ADAIR 16.10.2009 в 11:57
  • @REDSOFTADAIR: Два вопроса ... 1. Это руководство и руководство написано с 2001 года. Это давнее время и 3 языковых стандартных обновления. Разве это не устарело? И - разве это не означает, что BGL несколько устарел? 2. Можете ли вы ссылаться на какое-либо свободно доступное высокоуровневое описание BGL или на оценку его сильных и слабых сторон, вариантов дизайна и т. Д.? –  einpoklum 18.03.2016 в 22:48
  • @einpoklum: Нет, я не думаю, что он устарел. Я начал использовать больше boost :: graph позже - он обладает тихим высоким уровнем функциональности и работает очень хорошо. К сожалению, у меня нет ответов на ваш второй вопрос. –  RED SOFT ADAIR 30.03.2016 в 11:55
5

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

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

    
ответ дан eodonohoe 01.10.2009 в 21:16
  • Мне любопытно, для чего вы используете BGL? У вас возникли проблемы? Я предпочитаю слышать худшее, даже если я собираюсь выбрать что-то, чтобы я знал, в чем я вхожу. –  Catskul 02.10.2009 в 17:20
5

Вы также можете попробовать с помощью библиотеки графиков LEMON .

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

Вышла новая версия.

    
ответ дан rics 13.10.2009 в 09:14
  • Второе предложение LEMON. Я тестировал его сегодня и впечатлен чистым дизайном API и хорошими вариантами для различных графических реализаций; динамические графики vs static и т. д. Я до сих пор увеличил его до 1 миллиона узлов и 100 миллионов ребер без проблем с производительностью и т. д. Наконец, он скомпилирован и тщательно протестирован на трех платформах, которые я использую (Solaris, Linux, и MacOS); всегда приятно видеть при использовании открытого источника. ЛЕМОН - это не лимон. ;-) –  Joel Hoff 16.06.2010 в 02:57
3

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

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

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

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

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

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

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

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

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

    
ответ дан Steve314 10.10.2009 в 02:42
3

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

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

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

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

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

  1. Код, который кто-то еще написал, включая тестовые примеры, будет, как правило, более надежным, чем ваш собственный.
  2. Исправления легче реализовать (с обновлениями к компоненту, который вы повторно используете), это верно в Boost (поскольку они часто обновляются, и что Boost проверяется экспертами).
  3. Как только вы изучите одну фреймворк, вы можете применить ее к другим приложениям ... кто знает, что вы можете получить работу позже в жизни, используя фреймворк. Компании любят повторно использовать, а не изобретать колесо.
ответ дан monksy 13.10.2009 в 09:25
3

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

ответ дан DrDee 16.10.2009 в 19:25
2

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

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

    
ответ дан Manfred 23.07.2011 в 15:46
  • Просто установил его ... У VS2010 и последний удар ... все прошло гладко .... –  ntg 12.12.2012 в 16:30