Используйте библиотеку графиков /Node Сетевая библиотека или напишите мне?

Ответ 1

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

Ответ 2

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

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

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

Это мощный и не самый маленький бит 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

Ответ 3

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

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

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

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

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

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

Ответ 4

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

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

Ответ 5

Вы также можете попробовать LEMON.

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

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

Ответ 6

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

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

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

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

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

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

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

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

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

Ответ 7

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

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

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

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

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

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

Ответ 8

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

Ответ 9

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

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