Hey Simon,
you are trying to implement a one-to-all search, right? This will not
work with the pre-processing method used by OSRM (Contraction
Hierarchies). What CH gives you is the guarantee that you will find a
path between all pairs (s, t) if you execute a bidirectional search.
Think about it like attaching a certain "height" to each node. CH
modifies the graph in a way that guarantees that you will find a path
if you first search only uphill from the source and then search only
uphill from the target, meeting at least one point. The path you find
this way needs to be unpacked to recover the full list of nodes
visited. (see the file routing_algorithms/routing_base.hpp and the
function UnpackPath).
If you only want to run this computation as a one-off thing, have a
look at `tools/components.cpp`. It loads a different unprocessed
version of the graph - you should be able to implement a simple
Breath-First search on top of that to get a one-to-all computation.
Best,
Patrick
On Mon, Aug 3, 2015 at 2:44 PM, Simon Doodkin <helpmep...@gmail.com> wrote:
> hello
>
> i want to find all possible paths from some start point while going in a
> single direction.
> first forward then optionally also backward. also i want to have on each
> edge distance and travel time.
>
> i home i understand correctly
> const EdgeWeight weight = GetEdgeData(edge).distance;
> is travel time in ms.
>
> but something is wrong
> the coordinates results from GetCoordinateOfNode
> are too distant from the "from" coordinate and so the result is wrong.
>
> i tested viaroute command and the routing worked correctly.
>
> how to get coordinates or a phantom node of a node id?
>
>
> Simon.
>
> #ifndef WAYS_HPP
> #define WAYS_HPP
>
> #include "plugin_base.hpp"
>
> #include "../util/json_renderer.hpp"
> #include "../util/string_util.hpp"
>
> #include <osrm/json_container.hpp>
> #include <algorithm>
> #include <string>
> #include <vector>
>
> // locates the nearest node in the road network for a given coordinate.
> template <class DataFacadeT> class WaysPlugin final : public BasePlugin
> {
> public:
> explicit WaysPlugin(DataFacadeT *facade) : descriptor_string("ways"),
> facade(facade) {}
> const std::string GetDescriptor() const override final { return
> descriptor_string; }
>
> int HandleRequest(const RouteParameters &route_parameters,
> osrm::json::Object &json_result) override final
> {
> // check number of parameters
> if (route_parameters.coordinates.empty() ||
> !route_parameters.coordinates.front().is_valid())
> {
> return 400;
> }
>
> FixedPointCoordinate snapped_coordinate;
> auto input_coordinate=route_parameters.coordinates.front();
> if (!facade->LocateClosestEndPointForCoordinate(input_coordinate,
> snapped_coordinate))
> {
> json_result.values["status"] = 207;
> }
> else
> {
> //////
> //bool allow_uturn = false;
> //auto input_coordinate=route_parameters.coordinates.front();
> PhantomNode node_at_coordinate;
>
> facade->IncrementalFindPhantomNodeForCoordinate(snapped_coordinate,node_at_coordinate);
> std::cout << "FindPhantomNodeForCoordinate: " << node_at_coordinate << '\n';
> std::vector<NodeID> stack;
> std::vector<std::vector<NodeID>> results;
> NodeID from;
> from=node_at_coordinate.reverse_node_id;
> recourceNodeIds(from,0,stack,results,node_at_coordinate);
> /*
> NodeID from=node_at_coordinate.forward_node_id;
> for (auto edge : facade->GetAdjacentEdgeRange(from))
> {
> const NodeID target = GetTarget(edge);
> const EdgeWeight weight = GetEdgeData(edge).distance;
> }
> NodeID from=node_at_coordinate.reverse_node_id;
> for (auto edge : facade->GetAdjacentEdgeRange(from))
> {
> const NodeID target = GetTarget(edge);
> const EdgeWeight weight = GetEdgeData(edge).distance;
> }
> */
> /*
> struct EdgeData {
> NodeID id : 31;
> bool shortcut : 1;
> int distance : 30;
> bool forward : 1;
> bool backward : 1;
> }
> */
>
> ///////
> json_result.values["status"] = 0;
> osrm::json::Array json_coordinate;
> json_coordinate.values.push_back(snapped_coordinate.lat /
> COORDINATE_PRECISION);
> json_coordinate.values.push_back(snapped_coordinate.lon /
> COORDINATE_PRECISION);
> json_result.values["mapped_coordinate"] = json_coordinate;
> }
> return 200;
> }
> void recourceNodeIds(NodeID from,int totaldistance,std::vector<NodeID>
> &stack,std::vector<std::vector<NodeID>> &results,PhantomNode
> node_at_coordinate)
> {
> if(totaldistance>60000)
> {
> std::vector<NodeID> saved_stack;
> saved_stack=stack;
> results.push_back(saved_stack);
> return;
> }
> auto nodename=facade->get_name_for_id(node_at_coordinate.name_id);
> std::cout << "nodename: " << nodename << '\n' ;
> for (auto edge : facade->GetAdjacentEdgeRange(from))
> {
> const NodeID target = facade->GetTarget(edge);
> //const EdgeWeight weight = facade->GetEdgeData(edge).distance;
> auto data=facade->GetEdgeData(edge);
> auto coordinate_of_from=facade->GetCoordinateOfNode(from);
> auto coordinate_of_node=facade->GetCoordinateOfNode(target);
> auto nameofedgeid=facade->GetNameIndexFromEdgeID(data.id);
> auto nameofedge=facade->get_name_for_id(nameofedgeid);
> std::cout << "GetEdgeData: " ;
> std::cout << "from: "<< from <<", target: "<<target
> <<", id: " << data.id << ", "
> << "shortcut: " << data.shortcut << ", "
> << "distance: " << data.distance << ", "
> << "forward: " << data.forward << ", "
> << "backward: " << data.backward <<", "
> << "coordinate_of_node: " << coordinate_of_node <<", "
> << "coordinate_of_from: " << coordinate_of_from
> << "nameofedge: " << nameofedge
> << '\n';
> // if not in history array then recourse:
> //if(std::find(stack.begin(), stack.end(), target)!=stack.end())
> //{
> // stack.push_back(target);
> // recourceNodeIds(target,totaldistance+weight,stack,results);
> // stack.pop_back();
> //}
> }
> }
>
> private:
> std::string descriptor_string;
> DataFacadeT *facade;
> };
>
> #endif /* WAYS_HPP */
>
>
> _______________________________________________
> OSRM-talk mailing list
> OSRM-talk@openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk
>
_______________________________________________
OSRM-talk mailing list
OSRM-talk@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk
