graph_m4ri.h

Go to the documentation of this file.

#ifndef GRAPH_H
#define GRAPH_H

#include <structure.h>
#include <graph_model.h>
#include <iostream>
#include <data/matrix_pool.h>

struct mzd_t;

namespace frechet { namespace reach {

//class GraphModel;
class Graph;
typedef boost::shared_ptr<Graph> GraphPtr;

/*  Factory methods
*/
GraphPtr newGraph(const GraphModel::ptr model);
GraphPtr newGraph(const GraphModel::ptr model, IndexRange hmask);
GraphPtr newGraph(const GraphModel::ptr model, Structure& str);

class Graph
{
public:
    typedef boost::shared_ptr<Graph> ptr;
protected:
    mzd_t* mtx[2][2];

    IndexRange mask[2];

    const GraphModel::ptr model;
    mutable int diagonalElement;

    //@deprecated friend class CGraph;
public:
    struct Origin {
        enum {
            PLACEMENT,  
            RG,         
            MERGE2,     
            MERGE3      
        } operation;
        int blevel;
        int succesors;
        int i,j;
        Graph::ptr A,B;
        Graph::ptr P;
    } origin;

protected:  
    friend GraphPtr frechet::reach::newGraph(const GraphModel::ptr model);
    friend GraphPtr frechet::reach::newGraph(const GraphModel::ptr model, IndexRange hmask);
    friend GraphPtr frechet::reach::newGraph(const GraphModel::ptr model, Structure& str);

    Graph(const GraphModel::ptr amodel);
    Graph(const GraphModel::ptr amodel, IndexRange range);
    Graph(const GraphModel::ptr amodel, Structure& str);
public:
    Graph(const Graph& that);
    Graph(Graph&& that);

public:
    virtual ~Graph();
    
    void allocateAll();
    mzd_t* allocate(Orientation o1, Orientation o2);

    const IndexRange& hmask() const { return mask[HORIZONTAL]; }
    Rect rect(Orientation o1, Orientation o2) const;
    const GraphModel::ptr graphModel() const { return model; }

    void setOriginPlacement(int di, int dj);
    void setOriginRG(int i);
    void setOriginMerge2(Graph::ptr A, Graph::ptr B);
    void setOriginMerge3(Graph::ptr A, Graph::ptr B);
    void setOriginCombine(Graph::ptr P);
    void printOrigin(std::ostream& out) const;

    Graph& operator= (const Graph& that);
    Graph& operator= (Graph&& that);
    bool operator== (const Graph& that) const;

    void add_edge(Orientation ori_from, int i_from,
                  Orientation ori_to, int i_to);
    void add_range(IndexRange r_from, IndexRange r_to);
    //void add_range(IndexRange r_form, IndexRangePair r_to);
    bool contains_edge(Orientation ori_from, int i_from,
                       Orientation ori_to, int i_to) const;
    bool contains_edge(IndexRange r_from, IndexRange r_to) const;
    bool empty(Orientation o1, Orientation o2) const;
    bool zero(Orientation o1, Orientation o2) const;
    virtual void finalize();
    void releaseIfZero();

    virtual void release();
    virtual void release(Orientation o1, Orientation o2);
    virtual void release(Orientation o1, Orientation o2, MatrixPool* pool);

    int find_next1(Orientation o1, int i, Orientation o2, int j) const;
    int find_next0(Orientation o1, int i, Orientation o2, int j) const;
    IndexRange find_next_range(Orientation o1, int i, Orientation o2, int j) const;

    virtual void combine (const Graph* P);

    Graph::ptr merge2(const Graph* B, MatrixPool* pool=nullptr) const;
    //  this_VV := A_VV * B_VV (@see setOrigin)
    virtual void merge2(const Graph* A, const Graph* B, MatrixPool* pool=nullptr);

    Graph::ptr merge3(const Graph* B, MatrixPool* pool=nullptr) const;
    virtual void merge3(const Graph* A, const Graph* B, MatrixPool* pool=nullptr);
    virtual void queryDiagonalElement() const;
    virtual int foundDiagonalElement() const;

    virtual void synchToGpu() { /*no-op. implemented by GraphCL */ }
    virtual void synchFromGpu() { /*no-op. implemented by GraphCL */ }
    virtual void resetConditions() { /*no-op. implemented by GraphCL */ }
    double memory(Orientation ori1, Orientation ori2) const;
    double density(Orientation ori1, Orientation ori2) const;

    double memory() const;
    double density() const;

    void clear();
    void clear(Orientation ori1, Orientation ori2);
    bool is_upper_triangular(Orientation ori1, Orientation ori2) const;
    static bool is_upper_triangular(const mzd_t* mzd);
    void print(std::ostream& out, Orientation o1, Orientation o2) const;
protected:
    void copy(const Graph& that);
    void swap(Graph& that);

    void copy(const Structure& str, Orientation ori);
    static void print(std::ostream& out, const mzd_t* M);

public:
    static bool is_adjacent_to(const Graph& A, const Graph& B);

    static void set_bits(mzd_t* M, int row, int i, int j);
    static bool has_bits(mzd_t* M, int row, int i, int j);
    static void clear_row(mzd_t* M, int row);
    static void and_row(mzd_t* M, int r, mzd_t* M2, int r2);

    static int find_next1(mzd_t* M, int row, int i);
    static int find_next0(mzd_t* M, int row, int i);
};



} }     //  namespace frecht::reach

#endif // GRAPH_H