Ticket #11723: boost_bug.cpp

#include <iostream>
#include <fstream>
#include <sstream>
#include <unordered_map>

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/r_c_shortest_paths.hpp>
#include <boost/utility/result_of.hpp>

static constexpr double EPS = 0.00001;

struct VertexInfo {
    unsigned int id;
    unsigned int pickup;    // Quantity to be picked up (> 0 iff delivery == 0)
    unsigned int delivery;  // Quantity to be delivered (> 0 iff pickup == 0)
    double dual;            // Vertex dual value from a Linear Program
    double penalty;         // Penalty avoided if visiting this vertex
};

struct EdgeInfo {
    unsigned int id;
    unsigned int source_id;
    unsigned int target_id;
    double cost;            // Cost of going from source to target
};

using namespace boost;

using Graph = adjacency_list<listS, listS, bidirectionalS, VertexInfo, EdgeInfo>;
using Vertex = Graph::vertex_descriptor;
using Edge = Graph::edge_descriptor;
using Path = std::vector<Edge>;

struct GraphForLabelling {
    const Graph graph;
    const Vertex source;
    const Vertex sink;
};

struct Label {
    unsigned int pickup;    // Quantity that can be picked up after the current node
    unsigned int delivery;  // Quantity that can be delivered after the current node
    double cost;            // Cost of the partial path
};

inline bool operator<(const Label& lhs, const Label& rhs) {
    return (    lhs.pickup >= rhs.pickup &&     // LHS can pickup more
                lhs.delivery >= rhs.delivery &&   // LHS can deliver more
                rhs.cost - lhs.cost > EPS &&    // LHS costs less
                // And at least one of the first two inequalities is strict
                (lhs.pickup > rhs.pickup || lhs.delivery > rhs.delivery)
           );
}

inline bool operator==(const Label& lhs, const Label& rhs) {
    return (    lhs.pickup == rhs.pickup &&
                lhs.delivery == rhs.delivery &&
                std::abs(lhs.cost - rhs.cost) < EPS
           );
}

class LabelExtender {
public:
    bool operator()(const Graph& graph, Label& new_label, const Label& label, const Edge& edge) const {
        auto destination = graph[target(edge, graph)];

        new_label.pickup = label.pickup - destination.pickup;
        new_label.delivery = std::min(label.delivery - destination.delivery, label.pickup - destination.pickup);
        new_label.cost = label.cost + graph[edge].cost - destination.penalty - destination.dual;

        return (new_label.pickup >= destination.pickup && new_label.delivery >= destination.delivery);
    }
};

class LabelDominance {
public:
    inline bool operator()(const Label& lhs, const Label& rhs) const {
        return (lhs < rhs || lhs == rhs);
    }
};

class VertexIdFnt {
    using result_type = unsigned int;

    const Graph& g;

public:
    explicit VertexIdFnt(const Graph& g) : g{g} {}

    result_type operator()(const Vertex& v) const { return g[v].id; }
};

class EdgeIdFnt {
    using result_type = unsigned int;

    const Graph& g;

public:
    explicit EdgeIdFnt(const Graph& g) : g{g} {}

    result_type operator()(const Edge& e) const { return g[e].id; }
};

template<typename Fun, typename Arg>
class FntPropertyMap {
    using value_type = typename boost::result_of<Fun(Arg)>::type;

    const Fun& f;

public:
    explicit FntPropertyMap(const Fun& f) : f{f} {}
    friend value_type get(const FntPropertyMap& pm, const Arg& arg) { return pm.f(arg); }
    value_type operator[](const Arg& arg) const { return f(arg); }
};

namespace boost{
    template<typename Fun, typename Arg> struct property_traits<FntPropertyMap<Fun, Arg>> {
        using value_type = typename boost::result_of<Fun(Arg)>::type;
        using reference = value_type;
        using key_type = Arg;
        using category = readable_property_map_tag;
    };
}

template<typename Arg, typename Fun> FntPropertyMap<Fun, Arg> make_property_map(const Fun& f) {
    return FntPropertyMap<Fun, Arg>(f);
}

GraphForLabelling read_graph() {
    std::ifstream gfile;
    std::string line;

    Graph graph{};
    Vertex source{}, sink{};
    unsigned int source_id = 0u, sink_id = 0u;

    gfile.open("graph.txt");

    /****** Read number of vertices ******/

    unsigned int num_vertices;

    if(std::getline(gfile, line)) {
        std::stringstream ss(line);
        ss >> num_vertices;
        std::cout << "Reading a graph with " << num_vertices << " vertices." << std::endl;
    } else {
        std::cerr << "Can't read first line of the file!" << std::endl;
    }

    /****** Read vertices ******/

    using VertexList = std::unordered_map<unsigned int, Vertex>;

    VertexList vl{};
    unsigned int id, pickup, delivery;
    double dual, penalty;
    std::string vertex_type;
    std::stringstream ss("");

    for(auto line_counter = 0u; line_counter < num_vertices; ++line_counter) {
        std::getline(gfile, line);

        ss.str(line);
        ss >> id >> vertex_type >> pickup >> delivery >> dual >> penalty;

        if(vertex_type == "src") {
            source = add_vertex(graph);
            source_id = id;
            graph[source] = VertexInfo{id, pickup, delivery, dual, penalty};
        } else if(vertex_type == "snk") {
            sink = add_vertex(graph);
            sink_id = id;
            graph[sink] = VertexInfo{id, pickup, delivery, dual, penalty};
        } else {
            assert(vertex_type == "reg");
            vl.insert({id, add_vertex(graph)});
            graph[vl[id]] = VertexInfo{id, pickup, delivery, dual, penalty};
        }

        ss.str(std::string());
        ss.clear();
    }

    /****** Read edges ******/
    Edge e;
    unsigned int edge_source_id, edge_target_id, edge_n = 0u;
    double cost;

    while(std::getline(gfile,line)) {
        ss.str(line);
        ss >> id >> edge_source_id >> edge_target_id >> cost;

        assert(edge_source_id != sink_id && edge_target_id != source_id);

        if(edge_source_id == source_id) {
            e = add_edge(source, vl[edge_target_id], graph).first;
        } else if(edge_target_id == sink_id) {
            e = add_edge(vl[edge_source_id], sink, graph).first;
        } else {
            e = add_edge(vl[edge_source_id], vl[edge_target_id], graph).first;
        }

        graph[e] = EdgeInfo{id, edge_source_id, edge_target_id, cost};

        ss.str(std::string());
        ss.clear();
        ++edge_n;
    }

    std::cout << "Created a graph with " << edge_n << " edges." << std::endl;

    return GraphForLabelling{graph, source, sink};
}

void do_labelling(GraphForLabelling gfl, unsigned int capacity) {
    std::vector<Path> optimal_paths{};
    std::vector<Label> optimal_labels{};
    VertexIdFnt vi{gfl.graph};
    EdgeIdFnt ei{gfl.graph};

    std::cout << "Launching r_c_shortest_paths ..." << std::endl;

    r_c_shortest_paths(
        gfl.graph,
        make_property_map<Vertex>(vi),
        make_property_map<Edge>(ei),
        gfl.source,
        gfl.sink,
        optimal_paths,
        optimal_labels,
        Label{capacity, capacity, 0.0},
        LabelExtender{},
        LabelDominance{},
        std::allocator<r_c_shortest_paths_label<Graph, Label>>{},
        default_r_c_shortest_paths_visitor{}
    );

    std::cout << "Done: r_c_shortest_paths completed successfully" << std::endl;
}

int main() {
    auto graph_for_labelling = read_graph();

    do_labelling(graph_for_labelling, 450u);

    return 0;
}