multiple edges between two vertices

tygrysio commented 8 years ago

select source,target,count() from ways group by source,target having count() > 1

Whether it is correct for the route algorithms? Example map. https://www.openstreetmap.org/search?query=lubawa%20wyzwolenia%202#map=19/53.50283/19.73786

cvvergara commented 8 years ago

@tygrysio I don't think I understand your question, but hope the following helps.

osm2pgrouting converts osm data to "routing edges" given the example: suppose wizwolenia street osm data:

<way id="61800704" version="6" timestamp="2015-10-07T21:23:52Z" changeset="34500025" uid="2512300" user="xxxxxxx">
    <nd ref="770009067"/>
    <nd ref="770009070"/>
    <nd ref="3777400249"/>
    <nd ref="3777400261"/>
    <nd ref="3777400276"/>
    <nd ref="3777400298"/>
    <nd ref="1842347697"/>
    <nd ref="1842347817"/>
    <nd ref="1842347850"/>
    <tag k="name" v = "Wizwolenia">
    <tag k="highway" v="tertiary"/>
    <tag k="source" v="survey"/>
</way>

and the service road

  <way id="61800704" version="6" timestamp="2015-10-07T21:23:52Z" changeset="34500025" uid="2512300" user="xxxxxxx">
    <nd ref="3777400249"/>
    <nd ref="3777400250"/>
    <nd ref="3777400251"/>
    <nd ref="3777400261"/>
    <tag k="highway" v="service"/>
    <tag k="source" v="survey"/>
</way>

so nodes:

    <nd ref="3777400249"/>
    <nd ref="3777400261"/>

belong to both streets: "Wizwolenia" and the service street.

Because those kind of streets do not have a maxspeed column:

to set a default speed of 50 kph, the configuration must have something like:

<configuration>
  <type name="highway" id="1">
    <class name="tertiarty" id="101" />
    <class name="service" id="102" />
  </type>
</configuration>

to give a default speed, the configuration must have something like:

<configuration>
  <type name="highway" id="1">
    <class name="tertiarty" id="101" priority="1" maxspeed="30" />
    <class name="service" id="102" priority="1.1" maxspeed="10" />
  </type>
</configuration>

When routing, based on your example: inner_query:

SELECT id, source, target, cost, reverse_cost FROM ways

shortest path using length AS cost or length_m AS cost on undirected or (cost, reverse_cost) on a directed graph, the result is by not going through the service road
fastest path using cost_s AS cost will also return an answer that do not have the service road.
if use KSP, (with large enough K) one (or more) of the shortest paths will be using the service path.
if use withPoint functionality and route a point "near" the service road, it will route through the service path.
if you don't want to route using a service road the inner_query can look like:

SELECT id, source, target, cost, reverse_cost FROM ways WHERE class_id != 102

(but using the withPoint the point calculation also should be done to a segment that is not the service road)

tygrysio commented 8 years ago

Whether it is normal that in the graph are two different edges between the same nodes? Dijkstra returns nodes as the shortest path. So what is the shortest route?

cvvergara commented 8 years ago

it also returns the edge

cvvergara commented 8 years ago

which reminds me, KSP.... the parallel issue, which is this case: http://docs.pgrouting.org/2.3/en/doc/src/recipes/parallel_handling.html

woodbri commented 8 years ago

Dijkstra returns the shortest path which means there will be not other path that is shorter. There may be other paths that are the same length. The edges that are selected for the shortest path when there are equal cost parallel edges will depend on the other that the edges are inserted into the graph.

On 10/14/2016 9:00 AM, tygrysio wrote:

Whether it is normal that in the graph are two different edges between the same nodes? Dijkstra returns nodes as the shortest path. So what is the shortest route?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/pgRouting/osm2pgrouting/issues/145#issuecomment-253792773, or mute the thread https://github.com/notifications/unsubscribe-auth/AAxJggNlrIXZSPQPb3FYtZ3i7B7nBy4eks5qz3z0gaJpZM4KWt3F.

This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus

cvvergara commented 8 years ago

dijkstra tie brakes are arbitrarly

tygrysio commented 8 years ago

Perhaps, you need to divide the parallel edges? Add an additional vertex (node)

woodbri commented 8 years ago

This sounds more like a pgrouting question and not a osm2pgrouting question. osm2pgrouting just takes the OSM data and loads it into tables. If you think the data is wrong, then maybe you need to update the OSM data to fix the problem.

Regardless, you need to provide an explicit example with data and explain how the results you get are not what is expected and why.

tygrysio commented 8 years ago

I think that graphs should have one edge between the nodes. If not, you need to divide one of them or both.

woodbri commented 8 years ago

General graph theory does not require this restriction and pgrouting which is the consumer of this data does not require this restriction. For more information on pgrouting algorithms see: http://www.boost.org/doc/libs/1_62_0/libs/graph/doc/quick_tour.html If you have a specific need to support this you will need to make adjustments to your data in the database. Closing.

dkastl commented 8 years ago

The "parallel edges" issue was already discussed a couple of times. I just don't remember, if there were changes to the shortest path algorithms already, or if it's still up to the user to handle the issue, for example: http://gis.stackexchange.com/questions/45148/why-doesnt-pgrouting-return-the-best-path

I think the main point is, that algorithms like Dijkstra don't care about the edge. Only source and target ID are relevant, so if you have more than one choice as in this case, you only need to make sure, that you select the one with the lowest cost.

Of course you can "fix" your network and split ways, but I don't think this is very smart solution. The StackOverflow answer gives a pretty simple solution, because pgRouting will use the first source/target pair selected, so all you need to do is to sort by cost and only select the one with the edge with the lowest cost.

tygrysio commented 8 years ago

There are a simpler solution. Leave the network only the shortest edges.

cvvergara commented 8 years ago

@tygrysio the shortest edge might be the longer in time. example: two points are joined by two edges. the shortest one is a tertiary road and has a tracktype=grade5 the longest one is a motorway the shortest time is on the motorway the longest time is on the tertiary road

About: Leave the network only the shortest edges. That you can do by post processing on the database and removing whatever your routing application does not need.

pgRouting / osm2pgrouting

multiple edges between two vertices #145