boost_graph.h

 
 
#ifndef BF_P4C_LIB_BOOST_GRAPH_H_
#define BF_P4C_LIB_BOOST_GRAPH_H_
 
#include <map>
#include <optional>
 
#include <boost/graph/adjacency_list.hpp>
#include <boost/tuple/tuple.hpp>
 
#include "lib/bitvec.h"
#include "lib/cstring.h"
#include "lib/exceptions.h"
 
using namespace P4;
 
template <class Graph>
class Reachability {
 public:
    using Vertex = typename Graph::vertex_descriptor;
 
    using EdgeSet =
        typename boost::container_gen<typename Graph::vertex_list_selector, bitvec>::type;
 
    bool canReach(Vertex v1, Vertex v2) {
        if (forwardsReachableVertices.empty()) recompute();
        return forwardsReachableVertices.at(v1).getbit(v2);
    }
 
    bitvec reachableBetween(Vertex v1, Vertex v2) {
        if (forwardsReachableVertices.empty() || backwardsReachableVertices.empty()) recompute();
        return forwardsReachableVertices.at(v1) & backwardsReachableVertices.at(v2);
    }
 
    void clear() {
        forwardsReachableVertices.clear();
        backwardsReachableVertices.clear();
    }
 
    void setSink(std::optional<Vertex> sink) {
        this->sink = sink;
        clear();
    }
 
    explicit Reachability(const Graph &g) : g(g) {}
 
 private:
    void recompute() {
        forwardsReachableVertices.clear();
        backwardsReachableVertices.clear();
 
        forwardsReachableVertices.resize(boost::num_vertices(g), bitvec());
        backwardsReachableVertices.resize(boost::num_vertices(g), bitvec());
 
        // Ensure the reachability matrices have an entry for each vertex.
        typename Graph::vertex_iterator v, v_end;
        for (boost::tie(v, v_end) = boost::vertices(g); v != v_end; ++v) {
            forwardsReachableVertices[*v].clear();
            backwardsReachableVertices[*v].clear();
        }
 
        // Initialize with edges.
        typename Graph::edge_iterator edges, edges_end;
        for (boost::tie(edges, edges_end) = boost::edges(g); edges != edges_end; ++edges) {
            auto src = boost::source(*edges, g);
            auto dst = boost::target(*edges, g);
            forwardsReachableVertices[src].setbit(dst);
            backwardsReachableVertices[dst].setbit(src);
        }
 
        // Propagate reachability information via Floyd-Warshall.
        typename Graph::vertex_iterator mid, mid_end;
        for (boost::tie(mid, mid_end) = boost::vertices(g); mid != mid_end; ++mid) {
            // Ignore the sink node.
            if (sink && *mid == *sink) continue;
 
            typename Graph::vertex_iterator src, src_end;
            for (boost::tie(src, src_end) = boost::vertices(g); src != src_end; ++src) {
                recompute(backwardsReachableVertices, *src, *mid);
 
                // Ignore the sink node for forwards reachability.
                if (sink && *src == *sink) continue;
                recompute(forwardsReachableVertices, *src, *mid);
            }
        }
    }
 
    void recompute(EdgeSet &reachMatrix, Vertex src, Vertex mid) {
        // If we can't reach mid from src, don't bother going through dsts.
        if (!reachMatrix[src].getbit(mid)) return;
 
        // This is a vectorized form of a loop that goes through all dsts and sets
        //
        //   reachMatrix[src][dst] |= reachMatrix[src][mid] & reachMatrix[mid][dst]
        //
        // while taking advantage of the fact that we know that
        //
        //   reachMatrix[src][mid] = 1
        reachMatrix[src] |= reachMatrix[mid];
    }
 
    const Graph &g;
 
    std::optional<Vertex> sink = std::nullopt;
 
    EdgeSet forwardsReachableVertices;
 
    EdgeSet backwardsReachableVertices;
};
 
#endif /* BF_P4C_LIB_BOOST_GRAPH_H_ */