graph_boost.h

Go to the documentation of this file.

#ifndef GRAPH_H
#define GRAPH_H

#include <structure.h>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
//#include <boost/graph/adjacency_matrix.hpp>


namespace frechet { namespace reach {

class GraphModel;

class Graph
{
private:
    typedef boost::property <boost::vertex_name_t, int> Name;
    typedef boost::property <boost::vertex_index_t, std::size_t, Name> Index;
    typedef boost::adjacency_list < boost::setS, boost::listS, boost::directedS, Index > graph_t;
    //typedef boost::adjacency_matrix <boost::directedS> graph_t;
    typedef boost::graph_traits < graph_t >::vertex_descriptor vertex_t;

    //  TODO Map Indexes to vertices. This a awkward and error-prone. There must be better ways with boost::graph !!
    typedef boost::unordered_map<int,vertex_t> Index2VertexMap;
    typedef boost::property_map<graph_t,boost::vertex_index_t>::type Vertex2IndexMap;

    graph_t* g;
    Index2VertexMap i2v;

    const GraphModel& model;

    Graph(const GraphModel& model, graph_t* ag);
public:
    typedef boost::shared_ptr<Graph> ptr;

    Graph(const GraphModel& model);
    Graph(const GraphModel& model, Structure& str, int i0);
    Graph(const Graph&);
    Graph(Graph&&);

    ~Graph();

    int vertices() const;
    int edges() const;

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

    Graph& operator+= (const Graph&);

    Graph::ptr transitiveClosure() const;
    void transitiveClosureInPlace();

    void add_edge(int i, int j);

    void clear();

private:    

    void copy(const Graph&);
    void swap(Graph&);
    vertex_t vertex(int i);

    //  copy reachability info from Structure to Graph
    void copy(const Structure& str, Pointer i1, Pointer i2);
};

class GraphModel {
private:
    //  horizontal an vertical model (interval lists)
    BoundaryList _model[2];
    //  entry points for columns (reachability graphs starting at a certain free-space column)
    std::vector<Pointer> _column_entry;
    //  TODO do we need row entry points, too ?
    //  number of vertices
    int _count;
public:
    GraphModel();
    GraphModel(Structure& prototype);

    void init(Structure& prototype);

    int count() const { return _count; }

    //  refince (= adjust intervals to prototype = the "most refined" structure)
    void refine(Structure& str, int i0) const;

    //  (1) index Boundary Segments
    //  @deprecated should be already part of 'refine'
    void indexify(Structure& str, int i0) const;

private:
    BoundaryList& list(Orientation ori) { return _model[ori]; }

    BoundaryList& horiz() { return _model[HORIZONTAL]; }
    BoundaryList& vert() { return _model[VERTICAL]; }

    const BoundaryList& horiz() const { return _model[HORIZONTAL]; }
    const BoundaryList& vert() const { return _model[VERTICAL]; }

    void indexify(Structure& str, Orientation ori, const Pointer model) const;
    void refine(Structure& str, Orientation ori, const Pointer model) const;
};

} }     //  namespace frecht::reach

#endif // GRAPH_H