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 .
Can you describe you question in more detail? What do you mean with “do & 1 or & 2”?
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 :
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.
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
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
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
Hi @karussell , why do we assume the nodes included in SCC is unreachable ?
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 ？