I have osm file for my city, I am using Libosmium to read it, and I'm storing nodes of each way as Vertices of My Graph, and making edges between each 2 adjacent nodes in each way, and calculationg eucledian distance between them.
The ways are not connected with each other ! I can't reach my destination from my
source, even though there is a route in google map, but there is no node intersect between the ways (No common nodes) so I can't reach my destenation ! What nodes should I add to my Graph, and how to bridge them correctly ? so I can reach my destination from My Node ?
The Code I have used to create edges is the following
// Loop the Whole Map of Ways
for ( it = MyWayMap.begin(); it != MyWayMap.end(); it++ ){
WayCounter++;
NodesOfWayIndex = 0; //reset Index
//define a vector of nodes with size of Way
vector<Vertex> WayNodes(it->second.nodeRefList.size());
//======================================================
// Loop The Nodes of Each way
for(auto j = it->second.nodeRefList.begin(); j != it->second.nodeRefList.end(); ++j){
VertexID = it->second.nodeRefList.at(NodesOfWayIndex);
//declare Variable for Eucledean Distance
double dist = 0;
WayNodes[NodesOfWayIndex] = VertexID ;
//---------------------------------------------------------------------
// if the VertexId doesn't exist yet give back do the following
if(BelalMap.find(VertexID) == BelalMap.end()){
// assign idType values to the idmap
//idmap[IdMapIndex] = VertexID;
IdMapIndex++;
// Fill BelalMap
BelalMap.insert({VertexID,IdMapIndex});
if(NodesOfWayIndex == 0) Node1 = IdMapIndex;
else {
Node2 = IdMapIndex ;
dist = distance(WayNodes[NodesOfWayIndex - 1], WayNodes[NodesOfWayIndex]);
add_edge(Node1, Node2,dist,MyGraph);
add_edge(Node2, Node1,dist,MyGraph);
Node1 = Node2 ;
} // end else
}//end of outer if
//--------------------------------------------------------------------
//if the VertexId already exists give back it's Vertex number
else {
if(NodesOfWayIndex == 0) Node1 = BelalMap.find(VertexID)->second;
else {
// Calculating Eucledan Distance Between Nodes
dist = distance(WayNodes[NodesOfWayIndex - 1], WayNodes[NodesOfWayIndex]);
Node2 = BelalMap.find(VertexID)->second;
add_edge(Node1, Node2,dist,MyGraph);
add_edge(Node2, Node1,dist,MyGraph);
Node1 = Node2 ;
}// end of inner else
}//end of outer else
//======================================================
// increase The indexs after iterating each node.
NodesOfWayIndex++;
}// end of Nodes of Way Loop
}// end of Ways of Map Loop
How to build a routing graph from OSM XML has already been answered here: https://help.openstreetmap.org/questions/19213/how-can-i-convert-an-osm-xml-file-into-a-graph-representation/19214. Quoting from this answer:
Assuming you want only roads, then a possible algorithm is this:
- parse all ways; throw away those that are not roads, and for the others, remember the node IDs they consist of, by incrementing a "link counter" for each node referenced.
- parse all ways a second time; a way will normally become one edge, but if any nodes apart from the first and the last have a link counter greater than one, then split the way into two edges at that point. Nodes with a link counter of one and which are neither first nor last can be thrown away unless you need to compute the length of the edge.
- (if you need geometry for your graph nodes) parse the nodes section of the XML now, recording coordinates for all nodes that you have retained.
If you are only working on a small data set you can of course simply read everything into memory and do the above analysis in memory.
Based on your description you forgot to create edges between different ways. Ways are connected to each other if they share a node. You need to split a way at each node that is shared by more than one way in order to create proper edges in your routing graph.
Also see Routing in the OSM wiki.