Hi Peter, I verified in the Bay area osm data, it indeed fix this weird "problem".
*Best Regards,* *ZhiQiang ZHAO* On Wed, Jul 29, 2015 at 4:57 AM, Peter <[email protected]> wrote: > Hi ZhiQiang, > > it is indeed the case that such single nodes are SCC and this is not a bug > in our current algorithm. And it could therefor indeed lead to a > disconnected areas like you observed. Also your proposed fix of executing > the oneway removal first would make sense. I've create an issue for this: > https://github.com/graphhopper/graphhopper/issues/481 > > Would this solve your original issue too? > > Regards, > Peter > > > > On 29.07.2015 12:39, John Zhao wrote: > > Hi Peter, > > A possible solution could be: > run oneway network removal first, then run findSubNetwork(). > > *Best Regards,* > *ZhiQiang ZHAO* > > On Wed, Jul 29, 2015 at 3:38 AM, John Zhao <[email protected]> wrote: > >> Hi Peter, >> >> The test case could be: >> >> clique A ---> node c ---> clique B >> >> Clique means SCC, like all connected graph. >> node c is a SCC, if we assume a node can reach itself. >> >> Actually, an extreme case could be: >> node a ---> node b ---> node c >> >> each node is a SCC. >> >> >> >> >> >> *Best Regards,* >> *ZhiQiang ZHAO* >> >> On Wed, Jul 29, 2015 at 3:24 AM, Peter <[email protected]> wrote: >> >>> Hi ZhiQiang, >>> >>> the examples you show are SCC of only 1 node, but the original example >>> is not a SCC I think, as you have an outgoing and an incoming edge. So I >>> guess this is a bug or something. Maybe you can provide a failing and small >>> unit test for this so that I can have a look? >>> >>> Also the step 4 is indeed only for informational purposes but will print >>> new information if the step 3 changed the subnetworks. >>> >>> Regards, >>> Peter >>> >>> >>> On 29.07.2015 11:44, John Zhao wrote: >>> >>> Hi Peter, >>> >>> There are a lot of SCC with only 1 node, like: >>> http://www.openstreetmap.org/node/1707762331 >>> http://www.openstreetmap.org/node/386885888 >>> http://www.openstreetmap.org/node/364825950 >>> >>> Step 4 is only to findSubnetwork(), and print some info, not removal >>> them. >>> So, step 4 is optional. >>> >>> Now I only understand why this happen. :( >>> >>> >>> *Best Regards,* >>> *ZhiQiang ZHAO* >>> >>> On Wed, Jul 29, 2015 at 2:28 AM, Peter <[email protected]> wrote: >>> >>>> Hi ZhiQiang, >>>> >>>> > And the http://www.openstreetmap.org/node/678314919 itself is a SCC. >>>> size is 1. >>>> >>>> It shouldn't be a SCC im my opinion - is there a bug? >>>> If it is not a bug - do you have a suggestion for this, like avoiding >>>> step 4? >>>> >>>> Regards, >>>> Peter >>>> >>>> >>>> >>>> On 29.07.2015 11:18, John Zhao wrote: >>>> >>>> Hi Peter, >>>> >>>> The parameter I set are minOnewayNetworkSize = 20, minNetworkSize = >>>> 200 >>>> >>>> on step 3, despite the node >>>> http://www.openstreetmap.org/node/678314919, the inside island is a >>>> SCC, and the size is larger than 20. >>>> So, this island is kept, instead of removal. >>>> And the http://www.openstreetmap.org/node/678314919 itself is a SCC. >>>> size is 1. Then it was removed. >>>> >>>> Then on step 4, the island is recognized as a subnetwork, which has >>>> size less than 200. >>>> >>>> *Best Regards,* >>>> *ZhiQiang ZHAO* >>>> >>>> On Wed, Jul 29, 2015 at 1:04 AM, Peter <[email protected]> wrote: >>>> >>>>> Hi ZhiQiang, >>>>> >>>>> you mean the oneway procedure (step 3) removes nodes+edges leading to >>>>> further normal subnetwork removal in step 4? This should not happen. The >>>>> subnetwork should be removed already in step 3. >>>>> >>>>> > On step 2, although there is a gate >>>>> http://www.openstreetmap.org/node/703042503 >>>>> > on http://www.openstreetmap.org/way/6374339 >>>>> > And gate block that edge. >>>>> >>>>> Because of this gate the island is a oneway subnetwork (!) and should >>>>> get entirely removed in step 2 IMO. >>>>> >>>>> > On step 3, a very important point are removed due to oneway >>>>> >>>>> If just one edge/node is removed there is something wrong. The whole >>>>> island should be removed. >>>>> >>>>> Kind Regards, >>>>> Peter >>>>> >>>>> >>>>> On 29.07.2015 09:50, John Zhao wrote: >>>>> >>>>> Hi Peter, >>>>> >>>>> I know the difference between subnetworks and oneway-subnetworks. >>>>> I am talking about the step 2 and step 4, not step 3. >>>>> >>>>> step 2 and step 4 are both findSubnetwork() with the same parameter. >>>>> minOnewayNetworkSize = 20, minNetworkSize = 200 >>>>> >>>>> I think I figure out why this discrepancy occurs. >>>>> One case is a island in SF bay area. The island has 2 oneway roads >>>>> connected to the main network. >>>>> http://www.openstreetmap.org/way/53726398 >>>>> http://www.openstreetmap.org/way/6374339 >>>>> >>>>> On step 2, although there is a gate >>>>> http://www.openstreetmap.org/node/703042503 on >>>>> http://www.openstreetmap.org/way/6374339 >>>>> And gate block that edge. >>>>> The other oneway is connected >>>>> http://www.openstreetmap.org/way/53726398. >>>>> So, this island is connected to the whole network. >>>>> >>>>> On step 3, a very important point are removed due to oneway: >>>>> http://www.openstreetmap.org/node/678314919 >>>>> >>>>> Then on step 4, the island are not connected to the main network. >>>>> >>>>> *Best Regards,* >>>>> *ZhiQiang ZHAO* >>>>> >>>>> On Tue, Jul 28, 2015 at 11:12 PM, Peter <[email protected]> wrote: >>>>> >>>>>> Hi ZhiQiang, >>>>>> >>>>>> hmmh, not sure if I understand what is unknown at your side. >>>>>> >>>>>> Subnetworks are different things than oneway-subnetworks. For example >>>>>> 4-5 is a oneway subnetwork if connect with a oneway to the main graph >>>>>> only: >>>>>> mainGraph->4-5 >>>>>> >>>>>> And this cannot be detected in step 2. >>>>>> >>>>>> Please have a look at the unit tests to see more examples for the >>>>>> different scenes >>>>>> >>>>>> Regards, >>>>>> Peter >>>>>> >>>>>> >>>>>> On 28.07.2015 20:05, John Zhao wrote: >>>>>> >>>>>> Hi Peter, >>>>>> >>>>>> the result I posted is not the result of oneway-subnetwork >>>>>> procedure. >>>>>> >>>>>> The total procedures include: >>>>>> 1. remove zero-degree node >>>>>> 2. findSubnetwork >>>>>> 3. oneway-subnetwork procedure >>>>>> 4. findSubnetwork again on graphhopper.cleanup() >>>>>> >>>>>> My question is, why those islands are recognized on step 4, but not >>>>>> on step 2? >>>>>> >>>>>> >>>>>> >>>>>> *Best Regards,* >>>>>> *ZhiQiang ZHAO* >>>>>> >>>>>> On Tue, Jul 28, 2015 at 12:02 AM, Peter <[email protected]> wrote: >>>>>> >>>>>>> Hi ZhiQiang, >>>>>>> >>>>>>> I think it is because both networks are oneway subnetworks not found >>>>>>> by the normal subnetwork procedure (but by the oneway-subnetwork >>>>>>> procedure) >>>>>>> and you defined the oneway minimum size to 20 >>>>>>> >>>>>>> Regards, >>>>>>> Peter >>>>>>> >>>>>>> >>>>>>> On 28.07.2015 03:13, John Zhao wrote: >>>>>>> >>>>>>> Hi Peter, >>>>>>> >>>>>>> What I do is: >>>>>>> 1. minOnewayNetworkSize = 20, minNetworkSize = 200 >>>>>>> 2. build san francisco bay area osm data >>>>>>> 3. I print out the subnetworks result of the second call. >>>>>>> >>>>>>> int remainingSubnetworks = preparation.findSubnetworks().size(); >>>>>>> >>>>>>> 4. I found the subnetwork has some smaller than 200, like: >>>>>>> >>>>>>> subnetwork start from: 37.32611992939085,-121.9961998312816 size: 24 >>>>>>> >>>>>>> subnetwork start from: 37.78373608999855,-122.25065187925067 size: 34 >>>>>>> >>>>>>> 5. I can't understand why the subnetworks with 24 nodes and 34 nodes >>>>>>> are not removed by preparation.doWork(); >>>>>>> >>>>>>> It call the same method: >>>>>>> >>>>>>> Map map = this.findSubnetworks(); >>>>>>> >>>>>>> >>>>>>> *Best Regards,* >>>>>>> *ZhiQiang ZHAO* >>>>>>> >>>>>>> On Mon, Jul 27, 2015 at 12:54 PM, Peter <[email protected]> wrote: >>>>>>> >>>>>>>> Hi John, >>>>>>>> >>>>>>>> sorry, I do not understand your problem or question here. Would you >>>>>>>> describe it again step by step for me :) ? >>>>>>>> >>>>>>>> Kind Regards, >>>>>>>> Peter >>>>>>>> >>>>>>>> >>>>>>>> On 27.07.2015 21:45, John Zhao wrote: >>>>>>>> >>>>>>>> Hi Peter, >>>>>>>> >>>>>>>> Thanks. >>>>>>>> Actually I only have 1 flagEncoder in the EncodingManager. >>>>>>>> The call is exact same, preparation.findSubnetworks() >>>>>>>> >>>>>>>> preparation.findSubnetworks() using edgeFilter which is also from >>>>>>>> singleEncoder. >>>>>>>> >>>>>>>> >>>>>>>> *Best Regards,* >>>>>>>> *ZhiQiang ZHAO* >>>>>>>> >>>>>>>> On Sun, Jul 26, 2015 at 7:56 AM, Peter <[email protected]> wrote: >>>>>>>> >>>>>>>>> Hi John, >>>>>>>>> >>>>>>>>> it should not be related to calling these method twice. It is just >>>>>>>>> one time where you calculate the subnetworks independent of any >>>>>>>>> FlagEncoder >>>>>>>>> or direction via findSubnetworks and the second pass is FlagEncoder- >>>>>>>>> and >>>>>>>>> access-dependent via removeDeadEndUnvisitedNetworks. >>>>>>>>> >>>>>>>>> Regards, >>>>>>>>> Peter >>>>>>>>> >>>>>>>>> >>>>>>>>> On 24.07.2015 21:16, John Zhao wrote: >>>>>>>>> >>>>>>>>> Hi Peter, >>>>>>>>> >>>>>>>>> I am still confused. >>>>>>>>> at first we call >>>>>>>>> map = findSubnetworks(); >>>>>>>>> >>>>>>>>> after the cleanup, we call the same method in Graphhopper. >>>>>>>>> >>>>>>>>> int remainingSubnetworks = preparation.findSubnetworks().size(); >>>>>>>>> >>>>>>>>> Why the subnetwork was recognized the latter time, but not the first >>>>>>>>> time? >>>>>>>>> >>>>>>>>> we remove some edges make it not connected? >>>>>>>>> >>>>>>>>> >>>>>>>>> *Best Regards,* >>>>>>>>> *ZhiQiang ZHAO* >>>>>>>>> >>>>>>>>> On Thu, Jul 23, 2015 at 2:22 PM, Peter <[email protected]> wrote: >>>>>>>>> >>>>>>>>>> >>>>>>>>>> Hi ZhiQiang, >>>>>>>>>> >>>>>>>>>> yes, according to the wiki this is wrongly mapped: >>>>>>>>>> * Avoid tagging highway intersections as that does not make clear >>>>>>>>>> which way has the impediment. * >>>>>>>>>> >>>>>>>>>> http://wiki.openstreetmap.org/wiki/Tag:barrier%3Dgate >>>>>>>>>> >>>>>>>>>> Peter >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> On 23.07.2015 23:16, John Zhao wrote: >>>>>>>>>> >>>>>>>>>> Hi Peter, >>>>>>>>>> >>>>>>>>>> Maybe the following one related with >>>>>>>>>> https://github.com/graphhopper/graphhopper/issues/388#issuecomment-88066385 >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> I have a look at 37.32611992939085,-121.9961998312816. >>>>>>>>>> It seesm related with barrier=gate at intersection. >>>>>>>>>> http://www.openstreetmap.org/node/1126492194 >>>>>>>>>> >>>>>>>>>> *Best Regards,* >>>>>>>>>> *ZhiQiang ZHAO* >>>>>>>>>> >>>>>>>>>> On Thu, Jul 23, 2015 at 2:11 PM, Peter <[email protected]> >>>>>>>>>> wrote: >>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> There are two types of subnetworks and the smaller ones seems >>>>>>>>>>> to be 'one-way subnetworks' which means they are eg. only reachable >>>>>>>>>>> as >>>>>>>>>>> destination or start. But if you would start from a destination-only >>>>>>>>>>> subnetwork you'll get 'not found' for all points outside of this >>>>>>>>>>> network. >>>>>>>>>>> >>>>>>>>>>> Regards, >>>>>>>>>>> Peter >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> On 23.07.2015 23:03, John Zhao wrote: >>>>>>>>>>> >>>>>>>>>>> Interesting, >>>>>>>>>>> when I increase minOnewayNetworkSize from 20 to 50, the >>>>>>>>>>> following two disappeared. >>>>>>>>>>> subnetwork start from: 37.32611992939085,-121.9961998312816 >>>>>>>>>>> size: 24 >>>>>>>>>>> subnetwork start from: 37.78373608999855,-122.25065187925067 >>>>>>>>>>> size: 34 >>>>>>>>>>> >>>>>>>>>>> *Best Regards,* >>>>>>>>>>> *ZhiQiang ZHAO* >>>>>>>>>>> >>>>>>>>>>> On Thu, Jul 23, 2015 at 1:55 PM, John Zhao <[email protected]> >>>>>>>>>>> wrote: >>>>>>>>>>> >>>>>>>>>>>> Hi, >>>>>>>>>>>> >>>>>>>>>>>> I tried car flag encoder with following parameter on San >>>>>>>>>>>> Francisco bay area data from mapzen. >>>>>>>>>>>> >>>>>>>>>>>> https://s3.amazonaws.com/metro-extracts.mapzen.com/san-francisco-bay_california.osm.pbf >>>>>>>>>>>> >>>>>>>>>>>> minNetworkSize=200 >>>>>>>>>>>> minOnewayNetworkSize=20 >>>>>>>>>>>> >>>>>>>>>>>> I printed all the remaining subnetworks. >>>>>>>>>>>> edges: 591932, nodes 437420, there were 3496 subnetworks. >>>>>>>>>>>> removed them => 13121 less nodes. Remaining subnetworks:5 >>>>>>>>>>>> The remaining subnetworks are: >>>>>>>>>>>> subnetwork start from: 37.32611992939085,-121.9961998312816 >>>>>>>>>>>> size: 24 >>>>>>>>>>>> subnetwork start from: 37.56018439442332,-122.30257814308803 >>>>>>>>>>>> size: 436637 >>>>>>>>>>>> subnetwork start from: 37.78373608999855,-122.25065187925067 >>>>>>>>>>>> size: 34 >>>>>>>>>>>> subnetwork start from: 38.180185962770565,-121.70631393878864 >>>>>>>>>>>> size: 301 >>>>>>>>>>>> subnetwork start from: 37.85717050411933,-122.07633641532816 >>>>>>>>>>>> size: 424 >>>>>>>>>>>> >>>>>>>>>>>> I don't understand why there is still subnetwork less than >>>>>>>>>>>> 200 nodes. >>>>>>>>>>>> >>>>>>>>>>>> I have a look at 37.32611992939085,-121.9961998312816. >>>>>>>>>>>> It seesm related with barrier=gate at intersection. >>>>>>>>>>>> http://www.openstreetmap.org/node/1126492194 >>>>>>>>>>>> >>>>>>>>>>>> *Best Regards,* >>>>>>>>>>>> *ZhiQiang ZHAO* >>>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>> >>>>>>>>> >>>> > > _______________________________________________ > GraphHopper mailing list > [email protected] > https://lists.openstreetmap.org/listinfo/graphhopper > >
_______________________________________________ GraphHopper mailing list [email protected] https://lists.openstreetmap.org/listinfo/graphhopper
