The input for partition step is cnbg_to_ebg and ebg.
cnbg_to_ebg maps node based graph to edge based graph. It records edges in the format as
struct CompressedNodeBasedGraphEdge
{
NodeID source;
NodeID target;
};ebg contains uncontracted edge-based graph, indexed by EBG NodeID
struct Coordinate
{
FixedLongitude lon;
FixedLatitude lat;
}More context could be found here
BisectionGraph(type, interface) is the data structure used for graph partition step. makeBisectionGraph is the function used to construct which, it reorder edges and build adjacent list
inline BisectionGraph makeBisectionGraph(const std::vector<util::Coordinate> &coordinates,
const std::vector<BisectionInputEdge> &edges)
{
//...
// create a bisection node, requires the ID of the node as well as the lower bound to its edges
const auto make_bisection_node = [&edges, &coordinates](
const std::size_t node_id, const auto begin_itr, const auto end_itr) {
std::size_t range_begin = std::distance(edges.begin(), begin_itr);
std::size_t range_end = std::distance(edges.begin(), end_itr);
return BisectionGraph::NodeT(range_begin, range_end, coordinates[node_id], node_id);
};
//...
}
The definition of two important data structure worth you to take a look: BisectionInputEdge and BisectionGraphNode.
Most of partition logic happened in the constructor of RecursiveBisection. The use of Intel-thread-building-blocks could speed up these process dramatically.
// Parallelize recursive bisection trees. Root cut happens serially (well, this is a lie:
// since we handle big components in parallel, too. But we don't know this and
// don't have to. TBB's scheduler handles nested parallelism just fine).
//
// [ | ]
// / \ root cut
// [ | ] [ | ]
// / \ / \ descend, do cuts in parallel
//
// https://www.threadingbuildingblocks.org/docs/help/index.htm#reference/algorithms/parallel_do_func.html
// [Perry] TreeNode likes bisection tasks, until reach stop condition it will continue to split and add to the tree
struct TreeNode
{
BisectionGraphView graph;
std::uint64_t depth;
};
// Bisect graph into two parts. Get partition point and recurse left and right in parallel.
tbb::parallel_do(begin(forest), end(forest), [&](const TreeNode &node, Feeder &feeder) {
// ...
}PrePartitionWithSCC is the function calculate strong connected component, and you could find the implementation of algorithm here
Inertial flow is the algorithm used for graph partition, which is the most important part of CRP and MLD. This blog describe the logic pretty clear, and its coming from author for this part's code.
// entrance point
DinicMaxFlow::MinCut computeInertialFlowCut(const BisectionGraphView &view,
const std::size_t num_slopes,
const double balance,
const double source_sink_rate)
//...
// main logic happened in this function
DinicMaxFlow::MinCut bestMinCut(const BisectionGraphView &view,
const std::size_t n,
const double ratio,
const double balance)bestMinCut will try with different set of source/sink nodes and find best cut on each of them, then pick the one with minimum cost for bestMinCut.
For selecting different source/sink nodes, you could go to function makeSpatialOrder, and function reorderFirstLast is the one you should not missed.
After source/sink nodes be selected, OSRM use Dinic algorithm to calculate max flow min cut. Implementation is here and you could follow the steps of function listed below
DinicMaxFlow::ComputeLevelGraph
DinicMaxFlow::BlockingFlow
DinicMaxFlow::GetAugmentingPath
DinicMaxFlow::MakeCut
Logic can be found in function bisectionToPartition.
Logic can be found in function removeUnconnectedBoundaryNodes.
For example,
/*
0---1 4---5 8---7
\ / \ / \ /
2 3------6
*/If the partition algorithm put {0, 1, 2, 3} in one partition and {4, 5, 6, 7, 8} in another partition, this function will dectect that and make partition as {3, 4, 5, 6, 7, 8}
Logic can be found in function makePermutation