contraction_hierarchy.cpp File Reference

#include <routingkit/contraction_hierarchy.h>
#include <routingkit/id_queue.h>
#include <routingkit/sort.h>
#include <routingkit/inverse_vector.h>
#include <routingkit/timer.h>
#include <routingkit/graph_util.h>
#include <routingkit/vector_io.h>
#include <vector>
#include <fstream>
#include <stdexcept>

Include dependency graph for contraction_hierarchy.cpp:

Go to the source code of this file.

Namespaces
namespace	RoutingKit

Functions
void	RoutingKit::check_contraction_hierarchy_for_errors (const ContractionHierarchy &ch)
template int	RoutingKit::ContractionHierarchyQuery::get_extra_weight_distance< std::vector< int >, SaturatedWeightAddition > (const std::vector< int > &, const SaturatedWeightAddition &)
template unsigned	RoutingKit::ContractionHierarchyQuery::get_extra_weight_distance< std::vector< unsigned >, SaturatedWeightAddition > (const std::vector< unsigned > &, const SaturatedWeightAddition &)

Variable Documentation

backward

Side backward

Definition at line 605 of file contraction_hierarchy.cpp.

Referenced by RailEdge< E, V >::addVirtualTurns(), GNETLSEditorFrame::buildInternalLanes(), and computeRoutes().

backward_arc_count

unsigned backward_arc_count

Definition at line 1297 of file contraction_hierarchy.cpp.

Referenced by RoutingKit::check_contraction_hierarchy_for_errors().

backward_queue

MinIDQueue backward_queue

private

Definition at line 522 of file contraction_hierarchy.cpp.

backward_tentative_distance

std::vector<unsigned> backward_tentative_distance

private

Definition at line 520 of file contraction_hierarchy.cpp.

Referenced by RoutingKit::CustomizableContractionHierarchyQuery::get_distance(), RoutingKit::CustomizableContractionHierarchyQuery::get_distances_to_sources(), RoutingKit::CustomizableContractionHierarchyQuery::reset(), RoutingKit::CustomizableContractionHierarchyQuery::reset_target(), RoutingKit::CustomizableContractionHierarchyQuery::run_to_pinned_sources(), and RoutingKit::CustomizableContractionHierarchyQuery::run_to_pinned_targets().

bypass_node

unsigned bypass_node

private

Definition at line 364 of file contraction_hierarchy.cpp.

forward

Side forward

Definition at line 605 of file contraction_hierarchy.cpp.

Referenced by NBRailwayTopologyAnalyzer::addBidiEdgesBetweenSwitches(), MSDriveWay::addReversalFoes(), RailEdge< E, V >::addVirtualTurns(), NIImporter_OpenStreetMap::applyLaneUse(), GNETLSEditorFrame::buildInternalLanes(), MSDriveWay::buildSubFoe(), computeRoutes(), NBRailwayTopologyAnalyzer::extendDirectionPriority(), NIImporter_OpenStreetMap::extendRailwayDistances(), MSDriveWay::forwardRouteConflict(), MSLaneChanger::getBestLanesOpposite(), CHRouter< E, V >::getVia(), GNEChange::GNEChange(), GNEChange_TLS::GNEChange_TLS(), GNEChange_TLS::GNEChange_TLS(), NIImporter_OpenStreetMap::EdgesHandler::interpretLaneUse(), PedestrianEdge< E, L, N, V >::PedestrianEdge(), NBRailwayTopologyAnalyzer::reverseEdges(), and IntermodalNetwork< E, L, N, V >::splitEdge().

forward_arc_count

unsigned forward_arc_count

Definition at line 1296 of file contraction_hierarchy.cpp.

Referenced by RoutingKit::check_contraction_hierarchy_for_errors().

forward_queue

MinIDQueue forward_queue

private

Definition at line 521 of file contraction_hierarchy.cpp.

forward_tentative_distance

std::vector<unsigned> forward_tentative_distance

private

Definition at line 519 of file contraction_hierarchy.cpp.

Referenced by RoutingKit::CustomizableContractionHierarchyQuery::get_distance(), RoutingKit::CustomizableContractionHierarchyQuery::get_distances_to_targets(), RoutingKit::CustomizableContractionHierarchyQuery::reset(), RoutingKit::CustomizableContractionHierarchyQuery::reset_source(), RoutingKit::CustomizableContractionHierarchyQuery::run_to_pinned_sources(), and RoutingKit::CustomizableContractionHierarchyQuery::run_to_pinned_targets().

graph

const Graph* graph

private

Definition at line 518 of file contraction_hierarchy.cpp.

Referenced by RoutingKit::ContractionHierarchy::build(), RoutingKit::ContractionHierarchy::build_given_rank(), ROCCHMetrics::init(), and ROCCHMetrics::patchRestrictions().

hop_length

unsigned hop_length

Definition at line 183 of file contraction_hierarchy.cpp.

in_

std::vector<std::vector<Arc> > in_

private

Definition at line 226 of file contraction_hierarchy.cpp.

level_

std::vector<unsigned> level_

private

Definition at line 227 of file contraction_hierarchy.cpp.

magic_number

unsigned long long magic_number

Definition at line 1294 of file contraction_hierarchy.cpp.

max_pop_count

unsigned max_pop_count

private

Definition at line 517 of file contraction_hierarchy.cpp.

Referenced by RoutingKit::ContractionHierarchy::build(), RoutingKit::ContractionHierarchy::build_given_order(), and RoutingKit::ContractionHierarchy::build_given_rank().

mid_node

std::vector<unsigned> mid_node

Definition at line 184 of file contraction_hierarchy.cpp.

Referenced by RoutingKit::CustomizableContractionHierarchyMetric::build_contraction_hierarchy_using_perfect_witness_search(), RoutingKit::CustomizableContractionHierarchy::CustomizableContractionHierarchy(), and RoutingKit::CustomizableContractionHierarchyPartialCustomization::customize().

node

unsigned node

Definition at line 181 of file contraction_hierarchy.cpp.

Referenced by NIImporter_SUMO::_loadNetwork(), NGNet::add(), NBRailwayTopologyAnalyzer::addBidiEdgesForBufferStops(), NBRailwayTopologyAnalyzer::addBidiEdgesForStops(), NBNodeCont::addCluster2Join(), NIXMLConnectionsHandler::addCrossing(), NIXMLNodesHandler::addJoinCluster(), NIImporter_SUMO::addJunction(), NIXMLNodesHandler::addNode(), NBTrafficLightDefinition::addNode(), RONet::addNode(), PCLoaderOSM::addPOI(), NBEdgeCont::addPrefix(), NBNodeCont::addPrefix(), NIVissimDisturbance::addToNode(), NIXMLConnectionsHandler::addWalkingArea(), NBPTLine::addWayNode(), NBRailwayTopologyAnalyzer::allBroken(), NBRailwayTopologyAnalyzer::allSharp(), NBTrafficLightLogicCont::applyOpenDriveControllers(), NIVisumTL::build(), NLTriggerBuilder::buildCalibrator(), GNETLSEditorFrame::TLSPhases::buildDefaultPhase(), NGNode::buildNBNode(), NIVissimNodeCluster::buildNBNode(), GNEProhibitionFrame::buildProhibition(), NBRailwaySignalGuesser::canBeSignal(), CCHGraph< E, V >::CCHGraph(), KDTreePartition< E, N, V >::Cell::Cell(), KDTreePartition< E, N, V >::cellNumbers(), KDTreePartition< E, N, V >::cellNumbersAux(), GNEConnection::changeTLIndex(), NGRandomNetBuilder::checkAngles(), Circuit::checkCircuit(), GNETLSEditorFrame::cleanup(), NBLoadedTLDef::collectNodes(), NBNetBuilder::compute(), RoutingKit::compute_separator_decomposition(), AFBuild< E, N, V, M >::computeArcFlagsAux(), NBEdgePriorityComputer::computeEdgePriorities(), NBOwnTLDef::computeLogicAndConts(), NBTrafficLightLogicCont::computeLogics(), NBTurningDirectionsComputer::computeTurnDirectionsForNode(), NGNode::connected(), KDTreePartition< E, N, V >::Cell::contains(), NGNet::createChequerBoard(), NGNet::createSpiderWeb(), GNETLSEditorFrame::TLSPrograms::createTLS(), NBNodesEdgesSorter::crossing_by_junction_angle_sorter::crossing_by_junction_angle_sorter(), NBNodeCont::customTLID(), NIXMLNodesHandler::deleteNode(), Circuit::deployResults(), NIVissimNodeCluster::dict_addDisturbances(), NBNodeCont::discardRailSignals(), NBNodeCont::discardTrafficLights(), GUIOverheadWire::drawGL(), GNELane::drawLane2LaneConnections(), CCHGraph< E, V >::edgeOf(), GNETLSEditorFrame::editJunction(), NBNodeCont::erase(), Circuit::eraseNode(), CCHGraph< E, V >::expandNodePath(), NBRailwayTopologyAnalyzer::extendBidiEdges(), NBEdge::extendGeometryAtNode(), NIImporter_OpenStreetMap::extendRailwayDistances(), NBNodeCont::extract(), NGRandomNetBuilder::findPossibleOuterNodes(), NBRampsComputer::fulfillsRampConstraints(), NBRailwayTopologyAnalyzer::getBrokenRailNodes(), NIVissimDisturbance::getConnection(), NBEdge::getCrossingAngle(), NBEdge::getEndpointAtNode(), NIVissimEdge::getFromNode(), NBEdge::getInternalLaneWidth(), NBEdge::getJunctionPriority(), NIImporter_VISUM::getNamedEdgeContinuating(), NIImporter_VISUM::getNamedEdgeContinuating(), NIImporter_VISUM::getNamedEdgeContinuating(), NIImporter_VISUM::getNamedNode(), NIImporter_VISUM::getNamedNodeSecure(), NIImporter_OpenStreetMap::getNeighboringNodes(), Circuit::getNode(), Circuit::getNode(), NBEdge::getNodeBorder(), NIVissimConnectionCluster::getPositionForEdge(), NBRailwayTopologyAnalyzer::getRailEdges(), NBRailwayTopologyAnalyzer::getRailNodes(), NIImporter_VISUM::getReversedContinuating(), Element::getTheOtherNode(), NIVissimEdge::getToNode(), Circuit::getVoltage(), NBNodeCont::guessTLs(), NBEdge::hasDefaultGeometryEndpointAtNode(), NBRailwayTopologyAnalyzer::hasStraightPair(), KDTreePartition< E, N, V >::init(), NBNodeCont::insert(), NBNodeCont::insert(), NIImporter_OpenStreetMap::insertNodeChecking(), IntermodalNetwork< E, L, N, V >::IntermodalNetwork(), NIImporter_OpenStreetMap::interpretDistance(), GNEJunction::invalidateTLS(), KDTreePartition< E, N, V >::Cell::isInBounds(), NIImporter_VISUM::isSplitEdge(), NBRailwayTopologyAnalyzer::isStraight(), NBNodeCont::joinLoadedClusters(), NIImporter_OpenStreetMap::load(), NBNodeCont::markAsNotTLS(), NBNodeCont::markAsSplit(), NBEdgeCont::markRoundabouts(), NBOwnTLDef::maxCrossingIndex(), MSCalibrator::MSCalibrator(), NBTrafficLightDefinition::mustBrake(), NBRequest::mustBrakeForCrossing(), NIImporter_ITSUMO::Handler::myEndElement(), NIImporter_MATSim::NodesHandler::myStartElement(), NIImporter_OpenStreetMap::EdgesHandler::myStartElement(), NBNodeShapeComputer::NBNodeShapeComputer(), NBTrafficLightDefinition::NBTrafficLightDefinition(), GNETLSEditorFrame::TLSPrograms::onCmdSaveChanges(), NBNodeCont::onlyCrossings(), NBNodeCont::paretoCheck(), NIImporter_VISUM::parse_Lanes(), NIImporter_VISUM::parse_LanesConnections(), NIImporter_VISUM::parse_NodesToTrafficLights(), NLTriggerBuilder::parseAndBuildCalibrator(), NIXMLNodesHandler::processNodeType(), NBNodeCont::recheckGuessedTLS(), NBNodeCont::recheckTLSThreshold(), PedestrianRouter< E, L, N, V >::recomputeWalkCosts(), NIImporter_OpenStreetMap::reconstructLayerElevation(), NBNodeCont::remapIDs(), NBTrafficLightDefinition::removeNode(), NGRandomNetBuilder::removeOuterNode(), NBEdgeCont::removeRoundabout(), GNEJunction::removeTLSConnections(), NBNodeCont::rename(), GNEJunction::replaceIncomingConnections(), NIImporter_DlrNavteq::TrafficlightsHandler::report(), NBEdge::resetEndpointAtNode(), NBEdge::resetNodeBorder(), NIVissimEdge::resolveSameNode(), NBNodeCont::retrieveByPos(), NBEdgeCont::retrievePossiblySplit(), KDTreePartition< E, N, V >::searchNode(), NBNodeCont::setAsTLControlled(), GNEJunction::setAttribute(), MSOverheadWire::setCircuitEndNodePos(), MSOverheadWire::setCircuitStartNodePos(), NBEdge::setJunctionPriority(), GNEJunction::setJunctionType(), Element::setNegNode(), NBEdge::setNodeBorder(), Element::setPosNode(), NIVissimConflictArea::setPriorityRegulation(), NBEdge::shiftPositionAtNode(), NBEdge::shortenGeometryAtNode(), NBEdgeCont::splitAt(), NBEdgeCont::splitAt(), NBEdgeCont::splitAt(), NBEdgeCont::splitGeometry(), and NWWriter_SUMO::writeNetwork().

node_count

unsigned node_count

Definition at line 1295 of file contraction_hierarchy.cpp.

Referenced by RoutingKit::ContractionHierarchyQuery::add_source(), RoutingKit::CustomizableContractionHierarchyQuery::add_source(), RoutingKit::ContractionHierarchyQuery::add_target(), RoutingKit::CustomizableContractionHierarchyQuery::add_target(), RoutingKit::check_contraction_hierarchy_for_errors(), RoutingKit::compute_inverse_sort_permutation_first_by_tail_then_by_head(), RoutingKit::compute_inverse_sort_permutation_first_by_tail_then_by_head_and_apply_sort_to_tail(), RoutingKit::compute_nested_node_dissection_order_using_inertial_flow(), RoutingKit::compute_sort_permutation_first_by_tail_then_by_head(), RoutingKit::compute_sort_permutation_first_by_tail_then_by_head_and_apply_sort_to_tail(), RoutingKit::CustomizableContractionHierarchyParallelization::CustomizableContractionHierarchyParallelization(), RoutingKit::decompose_graph_fragment_into_connected_components(), RoutingKit::BlockingFlow::get_balanced_cut(), RoutingKit::inertial_flow(), RoutingKit::make_graph_fragment(), RoutingKit::pick_smaller_side(), and RoutingKit::ContractionHierarchyExtraWeight< Weight >::reset().

out_

std::vector<std::vector<Arc> > out_

private

Definition at line 226 of file contraction_hierarchy.cpp.

tail

std::vector<unsigned> tail

Definition at line 602 of file contraction_hierarchy.cpp.

Referenced by RoutingKit::ContractionHierarchy::build(), RoutingKit::ContractionHierarchy::build_given_order(), RoutingKit::ContractionHierarchy::build_given_rank(), RoutingKit::compute_inverse_sort_permutation_first_by_tail_then_by_head(), RoutingKit::compute_inverse_sort_permutation_first_by_tail_then_by_head_and_apply_sort_to_tail(), RoutingKit::compute_nested_node_dissection_order_using_inertial_flow(), RoutingKit::compute_sort_permutation_first_by_tail_then_by_head(), RoutingKit::compute_sort_permutation_first_by_tail_then_by_head_and_apply_sort_to_tail(), and RoutingKit::make_graph_fragment().

was_backward_pushed

TimestampFlags was_backward_pushed

private

Definition at line 524 of file contraction_hierarchy.cpp.

was_forward_pushed

TimestampFlags was_forward_pushed

private

Definition at line 523 of file contraction_hierarchy.cpp.

weight

unsigned weight

Definition at line 182 of file contraction_hierarchy.cpp.

Referenced by NBDistrictCont::addSink(), ODDistrict::addSink(), NBDistrict::addSink(), NBDistrictCont::addSource(), ODDistrict::addSource(), NBDistrict::addSource(), RoutingKit::ContractionHierarchy::build(), RoutingKit::ContractionHierarchy::build_given_order(), RoutingKit::ContractionHierarchy::build_given_rank(), combCallback(), combineCallback(), CCHGraph< E, V >::fillInputWeights(), PollutantsInterface::getClass(), HelpersPHEMlight::getClass(), PollutantsInterface::Helper::getClass(), LinearApproxHelpers::getInterpolatedValue(), MSStoppingPlaceRerouter::getTargetValue(), GUIPropertyScheme< T >::interpolate(), GUIPropertyScheme< T >::interpolate(), RGBColor::interpolate(), TrajectoriesHandler::myStartElement(), ODDistrictHandler::parseTAZ(), AdditionalHandler::parseTAZSinkAttributes(), AdditionalHandler::parseTAZSourceAttributes(), NIImporter_OpenStreetMap::reconstructLayerElevation(), GNETAZFrame::TAZSelectionStatistics::updateStatistics(), GNETAZ::updateTAZStatistic(), and MSAmitranTrajectories::writeVehicle().