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

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

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

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


c++ boost stl boost-graph
person Community    schedule 26.01.2010    source источник

Ответы (4)


arrow_upward
2
arrow_downward

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

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

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, > Graph_t;
Graph_t g(10000);
person Tristram Gräbener    schedule 26.01.2010
comment
Я могу оценить верхнюю границу. Я попытался инициализировать свой график этим значением, но это снова заняло очень много времени. Это долго не только при создании графа, но и при его обработке (например, чтобы очистить его). - person ; 26.01.2010
comment
Что вы называете очень долго? И занимает ли много времени только добавление вершин или также включает ребра (в этом случае пытались использовать список ребер для ребер)? Чтобы очистить график, возможно, будет проще создать новый график. - person Tristram Gräbener; 26.01.2010

arrow_upward
1
arrow_downward 

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

Выбор OutEdgeListS и VertexListS сильно влияет на временную сложность графовых алгоритмов, реализованных через boost adjacency_list.

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

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

person lalitm    schedule 26.01.2010
comment
Вирджиния не может использовать listS (как объяснено в вопросе), потому что идентификаторы используются как целые числа в другом месте кода. Таким образом, VertexListS должен сохранить значение по умолчанию, vecS. - person Benoît; 26.01.2010

arrow_upward
1
arrow_downward

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

person Mark B    schedule 11.02.2010

arrow_upward
0
arrow_downward

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

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

person J.I.Perotti    schedule 06.03.2011
comment
Это не позволит вам волшебным образом ссылаться на вершину по ее индексу вершины (вам нужен какой-то поиск по вершинному дескриптору) - person sehe; 28.10.2017