Статически распределенный график усиления
Уважаемый все это довольно просто, я надеюсь!
У меня есть график, который я хотел бы выделить статически. Я знаю, у меня будет N узлы и в большинстве K << N ребра для каждого узла (например, N = 1,000,000 а также K = 3). Было бы удобно, если бы я мог инициализировать не только граф с определенным числом узлов, но и с заранее определенным числом ребер.
Вы знаете, возможно ли это?
Если нет, вы бы порекомендовали исключить матрицу смежности для списков смежности? У меня будет огромное количество ребер, поэтому статическое распределение было бы здорово.
Ура!
Решение
Boost.Graph имеет Сжатый график разреженных рядов который делает что-то близкое к тому, что вы хотите. Это очень дружелюбно для памяти. Как и в других графах Boost, вы можете объявить его направленным, ненаправленным и т. Д. И связать свойства с его элементами.
В качестве предостережения, этот график является неизменным, то есть вы можете создавать и заполнять его, но не обновлять позже.
Вы должны иметь все свои ребра готовы, когда вы генерируете график. Смотрите аналогичную тему Вот
Другие решения
Я не проверял это, но учитывая 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