資源簡介
# 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個文件信息
評論
共有 條評論
川公網安備 51152502000135號