graph_boost.cpp

Go to the documentation of this file.

//
// Created by nightrider on 19.08.18.
//

#include <frechet/reachability/graph.h>
#include <boost/graph/transitive_closure.hpp>
#include <boost/graph/copy.hpp>
#include <boost/graph/graphviz.hpp>

frechet::reach::Graph::Graph(const GraphModel& amodel, graph_t* ag)
    : model(amodel), g(ag), i2v()
{
    //  TODO if g is not empty, i2v needs to be updated
}

frechet::reach::Graph::Graph(const GraphModel& amodel)
    : Graph(amodel, new graph_t())
{ }


frechet::reach::Graph::Graph(const frechet::reach::GraphModel& amodel,
                            frechet::reach::Structure& str, int i0)
    : Graph(amodel)
{
    //  unify intervals
    model.refine(str, i0);
    //  assign indexes to intervals
    //  TODO unless already done by refine !!??
    model.indexify(str, i0);

    //  insert edges into the graph
    copy(str, str.left().first(), str.right().first());
    copy(str, str.bottom().first(), str.top().first());
    //  TODO what about backward pointers ?
}

frechet::reach::Graph::Graph(const Graph& that)
    : Graph(that.model,nullptr)
{
    copy(that);
}

frechet::reach::Graph::Graph(Graph&& that)
    : Graph(that.model,nullptr)
{
    swap(that);
}

frechet::reach::Graph::~Graph()
{
    delete g;
}

int frechet::reach::Graph::vertices() const
{
    return boost::num_vertices(*g);
}

int frechet::reach::Graph::edges() const
{
    return boost::num_edges(*g);
}

frechet::reach::Graph& frechet::reach::Graph::operator= (const Graph& that)
{
    Q_ASSERT(&model == &that.model);
    copy(that);
    return *this;
}

frechet::reach::Graph& frechet::reach::Graph::operator= (Graph&& that)
{
    swap(that);
    return *this;
}

frechet::reach::Graph& frechet::reach::Graph::operator+= (const Graph& B)
{
    Vertex2IndexMap v2i = boost::get(boost::vertex_index,*B.g);
    boost::graph_traits<graph_t>::edge_iterator ei, ei_end;
    for (boost::tie(ei, ei_end) = boost::edges(*B.g); ei != ei_end; ++ei)
    {
        vertex_t v1 = boost::source(*ei,*g);
        vertex_t v2 = boost::target(*ei,*g);

        int i1 = boost::get(v2i,v1);
        int i2 = boost::get(v2i,v2);

        this->add_edge(i1,i2);
    }
    return *this;
}

void frechet::reach::Graph::clear()
{
    delete g;
    g = new graph_t();
    i2v.clear();
    //v2i = boost::get(boost::vertex_index,*g);
}

void frechet::reach::Graph::copy(const Graph& B)
{
    clear();
    operator+= (B);
}

void frechet::reach::Graph::swap(Graph& that)
{
    Q_ASSERT(&model == &that.model);
    std::swap(g,that.g);
    //std::swap(v2i,that.v2i);
    std::swap(i2v,that.i2v);
}


void frechet::reach::Graph::copy(const Structure& str, Pointer i1, Pointer i2)
{
    for( ; i1; i1=i1->next(), i2=i2->next())
    {
        if (i1->type==NON_ACCESSIBLE) continue;
        //  traverse all reachable intervals
        StructureIterator i (str, *i1, i2);
        for( ; i; ++i) {
            if(i->type==NON_ACCESSIBLE) continue;
            add_edge(i1->index(), i->index());
        }
    }
}

frechet::reach::Graph::vertex_t frechet::reach::Graph::vertex(int i)
{
    vertex_t v;
    auto f = i2v.find(i);

    if (f==i2v.end()) {
        v = boost::add_vertex(Index(i,i),*g);
        i2v.insert(std::make_pair(i,v));
    }
    else {
        v = f->second;
    }
    Q_ASSERT(boost::get(boost::get(boost::vertex_index,*g),v) == i);
    return v;
}

void frechet::reach::Graph::add_edge(int i, int j)
{
    vertex_t v1 = vertex(i);
    vertex_t v2 = vertex(j);
    //  TODO avoid duplicate edges
    //  boost::adjacency_list < boost::setS is essential !!
    boost::add_edge(v1,v2,*g);
}


frechet::reach::Graph::ptr frechet::reach::Graph::transitiveClosure() const
{
    boost::adjacency_list<>* tc = new graph_t();
    boost::transitive_closure (*g,*tc);
    return Graph::ptr(new Graph(model,(graph_t*)tc));
}

void frechet::reach::Graph::transitiveClosureInPlace()
{
    //  TODO can this work ?? I doubt...
//    boost::transitive_closure (*g,*g);
    graph_t* tc = new graph_t();
    boost::transitive_closure (*g,*tc);

    delete g;
    g = tc;
    //  TODO i2v needs to be updated
}