FM / partitioner

/srv/osrm/osrm-backend/include/partitioner/

/srv/osrm/osrm-backend/include/partitioner

Name	Size	Mode	Actions
bisection_graph.hpp	4481	0644	edit dl rm
bisection_graph_view.hpp	2397	0644	edit dl rm
bisection_to_partition.hpp	619	0644	edit dl rm
cell_statistics.hpp	1805	0644	edit dl rm
cell_storage.hpp	19648	0644	edit dl rm
dinic_max_flow.hpp	3745	0644	edit dl rm
edge_based_graph.hpp	1605	0644	edit dl rm
edge_based_graph_reader.hpp	7516	0644	edit dl rm
files.hpp	3596	0644	edit dl rm
inertial_flow.hpp	584	0644	edit dl rm
multi_level_graph.hpp	9762	0644	edit dl rm
multi_level_partition.hpp	13165	0644	edit dl rm
partitioner.hpp	365	0644	edit dl rm
partitioner_config.hpp	1315	0644	edit dl rm
partition_graph.hpp	5678	0644	edit dl rm
recursive_bisection.hpp	952	0644	edit dl rm
recursive_bisection_state.hpp	1870	0644	edit dl rm
remove_unconnected.hpp	3974	0644	edit dl rm
renumber.hpp	3108	0644	edit dl rm
reorder_first_last.hpp	1783	0644	edit dl rm
serialization.hpp	2672	0644	edit dl rm
tarjan_graph_wrapper.hpp	648	0644	edit dl rm

Edit: /srv/osrm/osrm-backend/include/partitioner/recursive_bisection_state.hpp (1870B)

#ifndef OSRM_PARTITIONER_RECURSIVE_BISECTION_STATE_HPP_
#define OSRM_PARTITIONER_RECURSIVE_BISECTION_STATE_HPP_

#include <cstddef>
#include <cstdint>
#include <vector>

#include "partitioner/bisection_graph.hpp"
#include "partitioner/bisection_graph_view.hpp"
#include "util/typedefs.hpp"

namespace osrm::partitioner
{

// Keeps track of the bisection ids, modifies the graph accordingly, splitting it into a left/right
// section with consecutively labelled nodes. Requires a GraphView to look at.
class RecursiveBisectionState
{
  public:
    // The ID in the partition array
    using NodeIterator = BisectionGraph::ConstNodeIterator;

RecursiveBisectionState(BisectionGraph &bisection_graph);
    ~RecursiveBisectionState();

BisectionID GetBisectionID(const NodeID node) const;

// Bisects the node id array's sub-range based on the partition mask.
    // Returns: partition point of the bisection: iterator to the second group's first element.
    NodeIterator ApplyBisection(NodeIterator begin,
                                const NodeIterator end,
                                const std::size_t depth,
                                const std::vector<bool> &partition);

// perform an initial pre-partitioning into small components
    // on larger graphs, SCCs give perfect cuts (think Amerika vs Europe)
    // This function performs an initial pre-partitioning using these sccs.
    std::vector<BisectionGraphView> PrePartitionWithSCC(const std::size_t small_component_size);

const std::vector<BisectionID> &BisectionIDs() const;

// return the depth encoded in the SCCs
    std::uint32_t SCCDepth() const;

private:
    std::uint32_t scc_levels;
    BisectionGraph &bisection_graph;
    std::vector<BisectionID> bisection_ids;
};

} // namespace osrm::partitioner

#endif // OSRM_PARTITIONER_RECURSIVE_BISECTION_STATE_HPP_

#ifndef OSRM_PARTITIONER_RECURSIVE_BISECTION_STATE_HPP_ #define OSRM_PARTITIONER_RECURSIVE_BISECTION_STATE_HPP_ #include #include #include #include "partitioner/bisection_graph.hpp" #include "partitioner/bisection_graph_view.hpp" #include "util/typedefs.hpp" namespace osrm::partitioner { // Keeps track of the bisection ids, modifies the graph accordingly, splitting it into a left/right // section with consecutively labelled nodes. Requires a GraphView to look at. class RecursiveBisectionState { public: // The ID in the partition array using NodeIterator = BisectionGraph::ConstNodeIterator; RecursiveBisectionState(BisectionGraph &bisection_graph); ~RecursiveBisectionState(); BisectionID GetBisectionID(const NodeID node) const; // Bisects the node id array's sub-range based on the partition mask. // Returns: partition point of the bisection: iterator to the second group's first element. NodeIterator ApplyBisection(NodeIterator begin, const NodeIterator end, const std::size_t depth, const std::vector &partition); // perform an initial pre-partitioning into small components // on larger graphs, SCCs give perfect cuts (think Amerika vs Europe) // This function performs an initial pre-partitioning using these sccs. std::vector PrePartitionWithSCC(const std::size_t small_component_size); const std::vector &BisectionIDs() const; // return the depth encoded in the SCCs std::uint32_t SCCDepth() const; private: std::uint32_t scc_levels; BisectionGraph &bisection_graph; std::vector bisection_ids; }; } // namespace osrm::partitioner #endif // OSRM_PARTITIONER_RECURSIVE_BISECTION_STATE_HPP_