Проблема с производительностью построения графика

Question

Я работаю над программным обеспечением, в котором мне нужно создать график (используя boost :: adjacency_list). Инкрементная вставка вершин занимает очень много времени. До сих пор я не работал над этой проблемой, потому что использование STLport помогло решить эту проблему. Теперь я перенес свою работу в Visual Studio 2008, но не могу тратить время на использование STLport (сложность в поддержании компиляции библиотек boost с использованием STLport).

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

Какие еще варианты есть у меня для решения этой проблемы (как в режиме отладки, так и в режиме выпуска)?

Answer 1

Вы заранее знаете, сколько у вас узлов? Если да, это значительно сократит время создания графика.

Например, для графа с 10 000 узлов:

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, > Graph_t;
Graph_t g(10000);

Answer 2

Вы действительно пытались профилировать код, выполнение которого занимает много времени? Вы можете быть удивлены и обнаружите что-то неожиданное (неявный конструктор преобразования / преобразования, больше сравнений, чем ожидалось, копирование данных и т. Д.). Кроме того, профилирование может дать вам представление о том, какая часть алгоритма вставки занимает много времени, и о возможностях (например, изменить аргументы конструктора adjacency_list) для его исправления.

Answer 3

template<class OutEdgeListS = vecS, class VertexListS = vecS,.....> adjacency_list;

Выбор OutEdgeListS и VertexListS оказывает большое влияние на временную сложность графовых алгоритмов, реализованных с помощью boost

• add_vertex () - амортизированное постоянное время для vecS и listS (реализовано с помощью push_back ()). Однако, когда тип VertexListS равен vecS, время для этой операции иногда велико, поскольку вектор будет перераспределен, а весь граф скопирован.
• remove_vertex () - это постоянное время для списков и O (V + E) для vecS.

Как вы можете видеть выше, по умолчанию для обоих это vecS. Таким образом, вы можете ожидать некоторого улучшения во времени, если вы используете listS для VertexListS (с большим объемом служебной информации)

Answer 4

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

Может быть, вы все-таки можете использовать списки. Просто объявите индекс вершины как свойство (отметьте http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/using_adjacency_list.html#sec:adjacency-list-properties). Но, если вы удалите вершину, вам, возможно, придется перенумеровать вершины. Кроме того, если вы добавляете вершину, вы должны назначить ее значение индекса вершины.