Boost logo

Boost Users :

Subject: [Boost-users] BGL, Johnson all pair shortest path and C
From: Paolo Bolzoni (paolo.bolzoni.brown_at_[hidden])
Date: 2015-11-05 08:02:32


Dear list,

I have to use johnson all pair shortest path[1] to have the all
pair distance matrix and pass it to a C function. Here is the
problem, the C function expect a row-order array, while the
Johnson expect a BasicMatrix[2] that understands the m[row][col]
syntax.

I solved it as shown in the bottom of the email, but it seems so
convoluted, is there a simpler way I missed?

Yours faithfully,
Paolo

[1] http://www.boost.org/doc/libs/release/libs/graph/doc/johnson_all_pairs_shortest.html
[2] http://www.boost.org/doc/libs/release/libs/graph/doc/BasicMatrix.html

/* -------------- */

//p is the graph
//distance_matrix is a std vector

auto size = boost::num_vertices(p);
Matrix distance_matrix1(distance_matrix, size, size);
MatrixR distance_matrix_wrapper(distance_matrix1);

//pass distance_matrix_wrapper to johnson algorithm.

/* -------------- */

struct Matrix {
    Matrix(std::vector<int64_t>& storage, size_t rows, size_t columns)
      : m_{storage},
        columns_{columns}
    {
        m_.clear();
        m_.resize(rows * columns_, int64_t{0});
    }

    int64_t& get(size_t row, size_t column) {
        return m_[row * columns_ + column];
    }

    std::vector<int64_t>& m_;
    size_t columns_;
};

struct MatrixR;
struct MatrixRR {
    MatrixRR(MatrixR const& m, size_t column)
      : m_{m},
        column_{column}
    {}
    int64_t& operator[] (size_t row) const;

    MatrixR const& m_;
    size_t column_;
};

struct MatrixR {
    MatrixR(Matrix& m)
      : m_{m}
    {}
    MatrixRR operator[] (size_t column) const {
        return MatrixRR(*this, column);
    }

    Matrix& m_;
};

int64_t &
MatrixRR ::
operator[] (size_t row) const {
    return m_.m_.get(row, column_);
}


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net