adj_matrix.h

Go to the documentation of this file.

/*
 * This file is part of the alglib project.
 *
 * (c) Divyanshu Kakwani <divkakwani@gmail.com>
 *
 * For the full copyright and license information, please view the LICENSE file
 * that was distributed with this source code.
 */

#pragma once

#include <vector>
#include <memory>

#include <alglib/bimap/bimap.h>
#include <alglib/graph/models/graph_model.h>

namespace alglib {
namespace graph {
namespace models {

template<typename vertex_t, typename edge_t>
class adj_matrix : public graph_model<vertex_t, edge_t> {
   
 public:
    /* typedefs */ 
    typedef vertex_t vertex_type;
    typedef edge_t edge_type;
    typedef typename alglib::bimap::bimap<vertex_t, int>::type1_iterator const_viterator;
 
 private:

    /* Establishes one-to-one mapping between vertices and ints */
    alglib::bimap::bimap<vertex_t, int> vertex_to_int;
   
    /* The adjacent matrix is represented as a vector of vectors.
     * Each cell, matrix[i][j], stores a unique_ptr to the corresponding edge if
     * there exists an edge between vertex i and vertex j, otherwise it refers to
     * null. The edge is the cell's copy of the edge and hence it is its owner.
     * Once it is set to null, the edge is automatically freed.
     */
    std::vector<std::vector<std::unique_ptr<edge_t>>> matrix;

    /* vsize tells the no of vertices; The is required because the `matrix` can be
     * preallocated vertices. Hence, its size would be larger than actual vsize.
     */
    int vsize;

    /* The following members record the in-degrees and out-degrees - to fasten
     * the indeg and outdeg methods. These require to be updated by every mutating method
     * on the graph.
     */
    std::vector<int> indeg_rec;
    std::vector<int> outdeg_rec;
    
    void grow_matrix(int dim);

 public:

/*
 * Which implementation?
 * Matrix view
 * Operations:
 * 1. Constant time access of M[i][j]
 * 2. Add vertices
 * 3. Remove vertices
 * 4. 
 */
    adj_matrix() = default;

    void add_vertex(const vertex_t& u) {
        vertex_to_int.insert(u, vsize++);
        grow_matrix(vsize);
    }
    // FIXME How?
    void remove_vertex() {}

    int indeg(const vertex_t& u) const {
        return indeg_rec[vertex_to_int.get_image(u)];
    }
    int outdeg(const vertex_t& u) const {
        return indeg_rec[vertex_to_int.get_image(u)];
    }
    int num_vertices() const {
        return vertex_to_int.size();
    }
    int num_edges() const {

    }

    const_viterator vbegin() const {
        vertex_to_int.domain_begin();
    }
    const_viterator vend() const {
        return vertex_to_int.domain_end();
    }



};

}  // end of models namespace
}  // end of graph namespace
}  // end of alglib namespace