Статическое распределение графика повышения

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

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

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

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

Ваше здоровье!


c++ boost graph adjacency-matrix boost-graph
person senseiwa    schedule 08.11.2013    source источник

Ответы (2)


arrow_upward
2
arrow_downward

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

Обратите внимание, что этот график неизменяем, то есть вы можете создать и заполнить его, но не обновлять позже. У вас должны быть готовы все ваши ребра, когда вы создаете граф. См. похожую тему SO здесь

person Michael Simbirsky    schedule 08.11.2013

arrow_upward
0
arrow_downward

Я не проверял это, но учитывая, что 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

person Theolodis    schedule 08.11.2013
comment
Интересно. Однако я определенно буду использовать направленный граф. - person senseiwa; 08.11.2013