Извлечь матрицу смежности из графа BGL

Используя библиотеку Boost Graph, я ищу способ извлечь матрицу смежности из базового графа, представленного либо boost::adjacency_list или же boost::adjacency_matrix, Я хотел бы использовать эту матрицу в сочетании с boost::numeric::ublas решить систему одновременных линейных уравнений.

Вот минимальный пример, чтобы вы начали:

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>

using namespace boost;

typedef boost::adjacency_list< listS, vecS, directedS > ListGraph;
typedef boost::adjacency_matrix< directedS > MatrixGraph;

int main(){ 

  ListGraph lg; 
  add_edge (0, 1, lg); 
  add_edge (0, 3, lg); 
  add_edge (1, 2, lg); 
  add_edge (2, 3, lg); 

  //How do I get the adjacency matrix underlying lg?

  MatrixGraph mg(3); 
  add_edge (0, 1, mg); 
  add_edge (0, 3, mg); 
  add_edge (1, 2, mg); 
  add_edge (2, 3, mg); 

  //How do I get the adjacency matrix underlying mg?

}

Если бы кто-нибудь смог придумать эффективный способ получить матрицу смежности, я был бы очень признателен. В идеале решение совместимо с uBLAS. Интересно, есть ли способ избежать итерации по всему графику.

Источник

3 ответа

Решение

Самый простой способ конвертировать adjacency_list в adjacency_matrix - это использовать boost::copy_graph

Ваш код для MatrixGraph mg следует изменить следующим образом

#include <boost/graph/copy.hpp>
#include <cassert>

using namespace boost;

typedef boost::adjacency_list< listS, vecS, directedS > ListGraph;
typedef boost::adjacency_matrix< directedS > MatrixGraph;

int main(){

    ListGraph lg;
    add_edge(0, 1, lg);
    add_edge(0, 3, lg);
    add_edge(1, 2, lg);
    add_edge(2, 3, lg);

    //How do I get the adjacency matrix underlying lg?

    //How do I get the adjacency matrix underlying mg?   
    MatrixGraph mg( num_vertices(lg));
    boost::copy_graph(lg, mg);
}

Теперь, чтобы использовать матрицу смежности с Ublas или подобным, вы можете написать простой класс "доступа", чтобы сделать синтаксис более совместимым с UBLAS. Продолжая предыдущий фрагмент, мы получаем:

template <class Graph>
class MatrixAccessor
{
public:
    typedef typename Graph::Matrix Matrix; //actually a vector<
    typedef typename Matrix::const_reference const_reference;


    MatrixAccessor(const Graph* g)
        : m_g(g)
    {
        static_assert(boost::is_same<size_t, typename Graph::vertex_descriptor>::value, "Vertex descriptor should be of integer type");
    }

    const_reference operator()(size_t u, size_t v) const
    {
        return m_g->get_edge(u, v);
    }

    const Graph* m_g;
};

void use_matrix(const MatrixGraph & mg)
{
    MatrixAccessor<MatrixGraph> matr(&mg);
    assert(matr(0, 1) == 1);
    assert(matr(0, 2) == 0);
}

Если у вашего adjacency_matrix есть свойства, связанные с ребрами, вам может потребоваться изменить operator () в MatrixAccessor.

В зависимости от того, сколько uBLAS вы используете, вы можете улучшить MatrixAccessor дальше. Например, out_edge_iterator для данной вершины MatrixGraph фактически является итератором над столбцом матрицы; vertex_iterator можно рассматривать как итератор для строк матрицы и т. д.

Конечно, графовая матрица является неизменной и поэтому должна использоваться с осторожностью.

Источник

Так же просто, и я не знаю, насколько это эффективно. Вот что я придумал:

Я использовал маленький граф мира и напечатал матрицу смежности.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/small_world_generator.hpp>
#include <boost/random/linear_congruential.hpp>

using namespace std;
using namespace boost;

typedef adjacency_list<vecS, vecS, undirectedS> Graph;
typedef small_world_iterator<boost::minstd_rand, Graph> SWGen;

int main()
{

    boost::minstd_rand gen;
    int N = 20;
    int degree = 4;
    double rewiring = 0.;

    Graph g(SWGen(gen, N, degree, rewiring), SWGen(), 20);

    cout << num_edges(g)<< '\n';

    typedef graph_traits<Graph>::edge_iterator edge_iterator;
    pair<edge_iterator, edge_iterator> ei = edges(g);

    for(edge_iterator edge_iter = ei.first; edge_iter != ei.second; ++edge_iter) {
        cout << "(" << source(*edge_iter, g) << ", " << target(*edge_iter, g) << ")\n";
    }
    vector<vector<int> > mat(N,vector<int>(N));

    for (edge_iterator edge_iter = ei.first; edge_iter != ei.second; ++edge_iter){
        int a = source(*edge_iter, g);
        int b = target(*edge_iter, g);
        mat[a][b] = 1;
        mat[b][a] = 1;
    }


    for (int i=0; i<N; i++){
        for (int j=0; j<N; j++){
            cout << mat[i][j]<<" ";
        }
        cout <<endl;
    }

  return 0;
}

Выход:

0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 
1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
Источник

Текущая редакция adjacency_matrix имеет недокументированного публичного члена m_matrix (см. строку 640). Тем не менее, это плоский вектор кортежей <bool, bundled_properties> (строка 512). Поскольку базовое хранилище выглядит очень отличным от матрицы Ublas, скорее всего, невозможно преобразовать граф в матрицу, кроме как итерировать по ребрам.

Источник
Другие вопросы по тегам