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] > <mailto:[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] > <mailto:[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] >> <mailto:[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] <mailto:[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] <mailto:[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] >>>>> <mailto:[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] >>>>>> <mailto:[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] >>>>>>> <mailto:[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] >>>>>>>> <mailto:[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] >>>>>>>>> <mailto:[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] >>>>>>>>>> <mailto:[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
