Статическое распределение boost Graph

Question

Дорогой, все это довольно просто, надеюсь!

У меня есть график, который я бы хотел выделить статически. Я знаю, что у меня будут N узлы и не болееK << N ребра для каждого узла (например, N = 1,000,000 и K = 3). Было бы удобно, если бы я мог инициализировать не только график с определенным количеством узлов, но и с предопределенным числом ребер.

Знаете ли вы, возможно ли это?

Если нет, вы бы посоветовали вырезать матрицу смежности для списков смежности? У меня будет огромное количество ребер, поэтому статическое распределение будет отличным.

Cheers!

Answer 1

Boost.Graph имеет Compressed Sparse Row Graph, который делает что-то близкое к тому, что вы хотите. Это очень дружелюбно. Как и в других графиках Boost, вы можете объявить их направленными, неориентированными и т. Д. И ассоциировать свойства со своими элементами.

Как предостережение, этот график является неизменным, что означает, что вы можете создавать и заполнять его, но не обновлять позже. Вам нужно, чтобы все ваши края были готовы при создании графика. См. Похожие темы. here

Answer 2

Я не проверял, но учитывая enum { A, B, C, D, E, F, N }; означает, что A = 0, B = 1, ..., N = 6, Graph g(N); кажется, выделить память о время компиляции для N = 6 узлов и что N*N края. Кажется, нет возможности уменьшить или ограничить количество ребер, если не использовать неориентированный граф.

источник: http://www.boost.org/doc/libs/1_54_0/libs/graph/doc/adjacency_matrix.html