[GraphHopper] There must be bug on the subnetwork removal
Peter
graphhopper at gmx.de
Wed Jul 29 11:57:25 UTC 2015
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 <johnthu at gmail.com
> <mailto:johnthu at gmail.com>> 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 <graphhopper at gmx.de
> <mailto:graphhopper at gmx.de>> 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 <graphhopper at gmx.de
>> <mailto:graphhopper at gmx.de>> 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
>>> <graphhopper at gmx.de <mailto:graphhopper at gmx.de>> 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
>>>> <graphhopper at gmx.de <mailto:graphhopper at gmx.de>> 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
>>>>> <graphhopper at gmx.de
>>>>> <mailto:graphhopper at gmx.de>> 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
>>>>>> <graphhopper at gmx.de
>>>>>> <mailto:graphhopper at gmx.de>> 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 <graphhopper at gmx.de
>>>>>>> <mailto:graphhopper at gmx.de>> 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 <graphhopper at gmx.de
>>>>>>>> <mailto:graphhopper at gmx.de>> 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
>>>>>>>>> <graphhopper at gmx.de
>>>>>>>>> <mailto:graphhopper at gmx.de>>
>>>>>>>>> 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
>>>>>>>>>> <johnthu at gmail.com
>>>>>>>>>> <mailto:johnthu at gmail.com>>
>>>>>>>>>> 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*
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>
>>>>>>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20150729/522df803/attachment.html>
More information about the GraphHopper
mailing list