Getting all the longest routes given a bounding box

Developers
#1

Hi everyone,
It’s been a while since I’ve started using your open source routing engine: I found it really helpful and easy to understand, so first of all I want to thank you for your great work! Keep it going :blush:

Currently I am facing an issue: given an OSM map and a bounding box, I must be able to get all the possible paths, regardless of the road direction and the profile. Every path has to be taken at its longest (since subpaths are not allowed) and only once.

Therefore, I need a full coverage of both the nodes and the edges, belonging to the bbox, of an undirectional graph built upon the OSM map. So far I’ve tried many workarounds to achieve that, but currently I am completely stuck.

Could you please help me sort this out?

Any help would be appreciated, thanks beforehand :slight_smile:

#2

I don’t think I understood what you are trying to do, but if you need to retrieve all edges and nodes in a bbox take a look at:

This will give you all the edge IDs of edges in the box. You can then use graph.getEdgeIteratorState(edge, Integer.MIN_VALUE) to get the corresponding EdgeIteratorStates and then use edge.getBase/AdjNode() along with graph.getNodeAccess().getLat/Lon(node) to get the coordinates of the corresponding nodes.

#3

Hi easbar,
thanks for the quick reply!
I have to get all the possible routes starting from the nodes belonging to the bbox, and I can retrieve this vertices exactly as you suggest.

I have to grant that these routes are the longest (i.e. if there is a path A → B → C, the subpath A → B has to be discarged) and I also have to grant that, retrieved these paths, every node and every edge has to be covered (neither nodes, nor edges belonging to the bbox can be left uncovered).

Therefore my biggest problem is to find a way to cover all the possible paths starting from that nodes; I’ve tried to launch a recursive function:

      {
                EdgeIterator iter = explorer.setBaseNode(currentNode);

		List<Integer> currentColoured = new ArrayList<>();
		currentColoured.addAll(coloured);
		MySetClass paths = new MySetClass();

		while (iter.next()) {
			int adj = iter.getAdjNode();
			
			if (!currentColoured.contains(adj)) {
				currentColoured.add(adj);
				MySetClass result = prova(explorer, adj, currentColoured, ++level);
				paths.addAll(result);

				for (List<Integer> path : paths) {
					path.add(currentNode);
				}
			}
		}

		if (paths.isEmpty()) {
			List<Integer> path = new ArrayList<>();
			path.add(currentNode);
			paths.add(path);
		}

		return paths;
	}

Unfortunately, it doesn’t work as I expected, maybe there are some adjacent nodes that seem ignored but I’m not sure about.

How would you approach that?

#4

All possible routes from where to where? And have you thought about how many ‘all possible routes’ are? There is an infinite number of possible routes, at least unless you exclude loops.

I don’t understand this either. You want to find the longest route from where to where? And again if you do not exclude loops the longest route will be infinitely long.

#5

Let’s say, for instance, that I have an OSM map of Naples (Italy) and a bounding box on it (see the photo in attachment).
Then, according to the assignment given, I have to cover all the paths inside the bbox, excluding subpaths, so at a first glance I thought I could do something naif like the stuff I’ll show you, and then find a way to remove subpaths:

                        Set<Integer> vertices = getAllVerticesByBBox(bbox);

			for (Integer startNode : vertices) {
				for (Integer endNode : vertices) {
					GHResponse routeResponse = getRouteResponse(startNode, endNode, profile);
					allResponses.addAll(routeResponse.getAll());
				}
			}

Where getAllVerticesByBBox(…) allows me to get all the vertices in the bbox as you said before and getRouteResponse(…) is something like that:

private GHResponse getRouteResponse(Integer startNode, Integer endNode, String profile) {

		GHRequest req = new GHRequest().setProfile(profile)
				.addPoint(new GHPoint(graph.getNodeAccess().getLat(startNode), graph.getNodeAccess().getLon(startNode)))
				.addPoint(new GHPoint(graph.getNodeAccess().getLat(endNode), graph.getNodeAccess().getLon(endNode)))
				.setAlgorithm(Parameters.Algorithms.ALT_ROUTE);

		GHResponse res = graphHopper.route(req);
		
		return res;
	}

Unfortunately, this leads me on heap overflow on average-sized maps…

Let me know if this helps explaining my issue :slight_smile:

image
image1157×666 86.7 KB

#6

What do you mean you have to ‘cover’ all the paths in the box?

#7

I have to get the coordinates of the points the paths are made of, so that I can get the corresponding polyline, which allows me to go on with further processing :slight_smile:

#8

But why do you need any paths at all then? Can you not just get all the coordinates of all the edges in the box instead? I also do not understand what you mean with “excluding subpaths”.

#9

I need the polyline corresponding to each travel route (i.e. if a pedestrian can travel from A to B, I need that route) because I have to pass it to an API endpoint which gives me back some informations. Therefore, it is important to me that I retrieve each single polyline, because I don’t need only a set of all the points of the bbox.

By excluding subpaths I mean that, if I go from A to B, and B has C as adjacent, then I have to take the path A → B → C and discard A → B.

#10

that route = the shortest route from A to B? → just use any of the routing algorithms and calculate the route from A to B.

that route = any route from A to B? → then you can just as well ask for all edges that belong to the connected component A and B belong to. take a look at Tarjan’s algorithm. This is also implemented in GraphHopper (TarjanSCC.java)

#11

You’re right, I mean any route from A to B.
Once I get all the edges of the SCC A and B belongs to, ho can I retrieve the routes? It might be a stupid question, I apologize beforehand :sweat_smile:

#12

No need to apologize and it’s not a stupid question. Then again, without defining what routes you are interested in it makes no sense to ask for ‘the routes’. Imagine you have a strongly connected component where all nodes are connected by at least one path for both directions. Going from A to B you can easily come up with a route that visits all edges, and even visits all edges twice, or any number of times. So you need to come up with some criteria that define which routes you are interested in and which you are not interested in. GraphHopper can find the shortest of all routes and also a few more that are short, but not the shortest, and somewhat different to the shortest (see the algorithm=alternatives parameter).

#13

Fine, it’s everything clear, thanks for your explanation :slight_smile:
Just another question: is there a way to find more than “a few more that are short, but not the shortest, and somewhat different to the shortest”? I mean, can I get all the possible finite alternative paths from A to B, and not only the shortest ones?

I managed to get a coverage like the one in attachment but, as you can see, there’s still some route inside the bbox I cannot include. This result came up setting ALT_ROUTE to true, but unfortunately it’s not enough to achieve my goal.

percorso_piedi
percorso_piedi1920×1030 368 KB

Powered by Discourse