GraphHopper.com | Forum | GitHub | Maps | Blog

About the strategy for remove unreachable Node while finish load MapData


#1

I noticed there is a cleanup procedure while after finishing readGraph as the code in GraphHopper.java cleanUp . I donn’t understand the code (mark nodes unreachable need removed) as :

why does use wayflag( edge’s cacheflag) do & 1 or & 2 ? I notice there are various value of wayflag user create edges , still don’t understand the strategy .


#2

Can you describe you question in more detail? What do you mean with “do & 1 or & 2”?


#3

My question just for code :


why does it determine the edge is backward or forward ?
Go inside the function isBackward or isForward of encoder , i see the below operation :


#4

It just determines if the specific edge is accessible for the specific vehicle profile in one or the other direction.

BTW: Please avoid code screenshots, instead paste them here, so anyone in the future can easier search.


#5

ok , i know the purpose now . But i donn’t understand why use the result of that compute " flags & forwardBit " or " flags & backwardBit " as whether the edge is accessible ?
I notice there are various values for wayflags , how to guarntee the result of compute " flags & forwardBit" is expected?
yes , i will past the original code next time :slight_smile:


#6

If you want to understand this part you should take a look into the technical docs: https://github.com/graphhopper/graphhopper/blob/master/docs/core/technical.md

But if you want to understand the unreachable node removal you should assume that the storage stuff works and have a look into Tarjan’s algorithm: https://en.wikipedia.org/wiki/Tarjan’s_strongly_connected_components_algorithm


#7

Want to import custom mapData , just do a testing against the below xml
filesample_map.pbf (1.4 KB)

(contains two ways and three nodes ) , found the three node will be remove in the log as follow
(
com.graphhopper.routing.subnetwork.PrepareRoutingSubnetworks - optimize to remove subnetworks (3), unvisited-dead-end-nodes (2), maxEdges/node (0)
com.graphhopper.storage.BaseGraph - More than a half of the network should be removed!? Nodes:3, remove:3
)
BTW: Found i export a small part of map data from openstreemap beijing-wangjing.txt (175.9 KB)
, still get the log
(INFO com.graphhopper.routing.subnetwork.PrepareRoutingSubnetworks - optimize to remove subnetworks (116), unvisited-dead-end-nodes (165), maxEdges/node (0)
com.graphhopper.storage.BaseGraph - More than a half of the network should be removed!? Nodes:116, remove:116)

I know the first case , it is a strongly conected component , but for second case for what ?
not sure the root cause :frowning:


#8

Hi @karussell , why do we assume the nodes included in SCC is unreachable ?


#9

See https://discuss.graphhopper.com/t/93

You can configure the size of the unreachable networks that should be removed: https://github.com/graphhopper/graphhopper/blob/master/config-example.properties#L59


#10

Yes , i found that configuration against the code then change to 0 . But i am still confuse the Tarjan’s algorithm you implemented to find the SSC , why do you think the nodes of SSC is unreachable ?