Customizable Route Planning开源代码CRP

# CRP Open source C++ Implementation of Customizable Route Planning (CRP) by Delling et al. This project was part of a practical course at Karlsruhe Institute of Technology (KIT). Requirements ============ In order to build CRP you need to have the following software installed: - Boost C++ Library (http://www.boost.org), more specifically Boost Iostreams. - Scons (http://scons.org) - g++ >= 4.8 (https://gcc.gnu.org) Building CRP ============ If the Boost Library is not in your PATH, make sure to edit the *SConstruct* file in the root directory to point the build script to the correct location of Boost. There is a section *Libraries* in the *SConstruct* file where you can specify the paths. Once you have installed all the software packages listed above, you can build the CRP programs by typing ``` scons --target=CRP --optimize=Opt -jX ``` into your terminal where `X` is the number of cores you want to use for building the project. If you want to use a specific g++ compiler version you can add `--compiler=g++-Version`. We also support a debug and profiling build that you can call with `--optimize=Dbg` and `--optimize=Pro` respectively. This command will build three programs in the folder *deploy*: - *osmparser*: Used to parse an OpenStreetMap (OSM) bz2-compressed map file. Call it with `./deploy/osmparser path_to_osm.bz2 path_to_output.graph.bz2` - *precalculation*: Used to build an overlay graph based on a given partition. Call it with `./deploy/precalculation path_to_graph path_to_mlp output_directory`. Here, *path_to_mlp* is the path to a *MultiLevelPartition* file for the graph that you need to provide. For more details, take a look into our project documentation. - *customization*: Used to precompute the metric weights for the overlay graph. Call it with `./deploy/customization path_to_graph path_to_overlay_graph metric_output_directory metric_type`. We currently support the following metric types: *hop* (number of edges traversed), *time* and *dist*.

/*
 * CRPQuery.cpp
 *
 *  Created on: Jan 8 2016
 *      Author: Michael Wegner & Matthias Wolf
 *
 * Copyright （c） 2016 Michael Wegner and Matthias Wolf
 *
 * Permission is hereby granted free of charge to any person obtaining a copy
 * of this software and associated documentation files （the “Software“） to deal
 * in the Software without restriction including without limitation the rights
 * to use copy modify merge publish distribute sublicense and/or sell
 * copies of the Software and to permit persons to whom the Software is
 * furnished to do so subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED “AS IS“ WITHOUT WARRANTY OF ANY KIND EXPRESS OR
 * IMPLIED INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM DAMAGES OR OTHER
 * LIABILITY WHETHER IN AN ACTION OF CONTRACT TORT OR OTHERWISE ARISING FROM
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

#include “CRPQuery.h“

#include 
#include 

#include “../timer.h“

namespace CRP {

CRPQuery::CRPQuery（const Graph& graph const OverlayGraph& overlayGraph const std::vector& metrics PathUnpacker& pathUnpacker） : Query（graph overlayGraph metrics） pathUnpacker（pathUnpacker） {
	const count vectorSize = 2 * graph.getMaxEdgesInCell（） + overlayGraph.numberOfVertices（）;
	forwardInfo = std::vector（vectorSize {inf_weight 0}）;
	backwardInfo = std::vector（vectorSize {inf_weight 0}）;	
	
	forwardGraphPQ = MinIDQueue（2 * graph.getMaxEdgesInCell（））;
	forwardOverlayGraphPQ = MinIDQueue（overlayGraph.numberOfVertices（））;

	backwardGraphPQ = MinIDQueue（2*graph.getMaxEdgesInCell（））;
	backwardOverlayGraphPQ = MinIDQueue（overlayGraph.numberOfVertices（））;

	currentRound = 0;
}

QueryResult CRPQuery::vertexQuery（index sourceVertexId index targetVertexId index metricId） {
	const BackwardEdge &backwardEdgeToStart = graph.getBackwardEdge（graph.getEntryOffset（sourceVertexId））;
	index sourceEdgeId = graph.getExitOffset（backwardEdgeToStart.tail） + backwardEdgeToStart.exitPoint;

	const ForwardEdge &forwardEdgeFromTarget = graph.getForwardEdge（graph.getExitOffset（targetVertexId））;
	index targetEdgeId = graph.getEntryOffset（forwardEdgeFromTarget.head） + forwardEdgeFromTarget.entryPoint;
	
	return edgeQuery（sourceEdgeId targetEdgeId metricId）;
}

QueryResult CRPQuery::edgeQuery（index sourceEdgeId index targetEdgeId index metricId） {
	currentRound++;

	const index s = graph.getForwardEdge（sourceEdgeId）.head;
	const index sGlobalId = graph.getEntryOffset（s） + graph.getForwardEdge（sourceEdgeId）.entryPoint;
	const pv sCellNumber = graph.getCellNumber（s）;

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2016-04-29 09:55  CRP-master\
     文件         324  2016-04-29 09:55  CRP-master\.gitignore
     文件        1080  2016-04-29 09:55  CRP-master\LICENSE
     文件        3985  2016-04-29 09:55  CRP-master\README.md
     文件        6458  2016-04-29 09:55  CRP-master\SConstruct
     目录           0  2016-04-29 09:55  CRP-master\algorithm\
     文件       23318  2016-04-29 09:55  CRP-master\algorithm\CRPQuery.cpp
     文件        2447  2016-04-29 09:55  CRP-master\algorithm\CRPQuery.h
     文件        8004  2016-04-29 09:55  CRP-master\algorithm\CRPQueryUni.cpp
     文件        2420  2016-04-29 09:55  CRP-master\algorithm\CRPQueryUni.h
     文件        4229  2016-04-29 09:55  CRP-master\algorithm\Dijkstra.cpp
     文件        2065  2016-04-29 09:55  CRP-master\algorithm\Dijkstra.h
     文件       23519  2016-04-29 09:55  CRP-master\algorithm\ParallelCRPQuery.cpp
     文件        2467  2016-04-29 09:55  CRP-master\algorithm\ParallelCRPQuery.h
     文件        7927  2016-04-29 09:55  CRP-master\algorithm\PathUnpacker.cpp
     文件        4166  2016-04-29 09:55  CRP-master\algorithm\PathUnpacker.h
     文件        2862  2016-04-29 09:55  CRP-master\algorithm\Query.h
     文件        1623  2016-04-29 09:55  CRP-master\constants.h
     目录           0  2016-04-29 09:55  CRP-master\customization\
     文件        3062  2016-04-29 09:55  CRP-master\customization\Customization.cpp
     目录           0  2016-04-29 09:55  CRP-master\datastructures\
     文件        5321  2016-04-29 09:55  CRP-master\datastructures\Graph.cpp
     文件       13948  2016-04-29 09:55  CRP-master\datastructures\Graph.h
     文件        2779  2016-04-29 09:55  CRP-master\datastructures\LevelInfo.h
     文件        4106  2016-04-29 09:55  CRP-master\datastructures\MultiLevelPartition.cpp
     文件        2630  2016-04-29 09:55  CRP-master\datastructures\MultiLevelPartition.h
     文件        9080  2016-04-29 09:55  CRP-master\datastructures\OverlayGraph.cpp
     文件        8907  2016-04-29 09:55  CRP-master\datastructures\OverlayGraph.h
     文件        8846  2016-04-29 09:55  CRP-master\datastructures\OverlayWeights.cpp
     文件        2419  2016-04-29 09:55  CRP-master\datastructures\OverlayWeights.h
     文件        1617  2016-04-29 09:55  CRP-master\datastructures\QueryResult.h
............此处省略29个文件信息