• Advertisement
Sign in to follow this  

Generating all possible combinations of route in a graph?

This topic is 569 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

If I had 16 destinations,

 

I have to do

But I can't predict how many destinations I have in advance

for (const auto& it = nodes.begin(); it != nodes.end(); ++it)
{
     for (const auto& it2 = std::next(it); it2 != nodes.end(); ++it2)
     {
          ... 16 inner loops
     }
}

What is a cleaner way to archieve this?

Thanks

Jack

Edited by lucky6969b

Share this post


Link to post
Share on other sites
Advertisement

What do you mean by “destination”? Are you simply looking for a path between every pair of vertices in your graph?

 

Your example code doesn't clarify your question much either – you iterate over all unordered pairs of vertices, and then what? What would those 16 inner loops do?

Share this post


Link to post
Share on other sites

I am also confused as to what the question is. Could you give an example? If you have destinations A, B, and C are you hoping to get AB, AC, BC? Or is it more complex than that, are you hoping to get AB, AC, BC, ABC, ACB, BAC, BCA etc. That is more complex but is quite a well solved problem mathematically. I recall watchign a video on something similar and I think the method was called 'Stars and Bars':

 

https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

Share this post


Link to post
Share on other sites

Is it a directed graph or is it undirected?  Do you have constraints or need to take weights into account?  Are you looking for an efficient solution to the all-points shortest-path problem (which can be O(n^2) on the number of edges) or are you looking for all possible permutations (O(n!) on the number of nodes)?

Share this post


Link to post
Share on other sites
I think I know what he is asking. Let's say I want to list all subsets of size 3 of the numbers in {0, 1, ..., 9}. I could do this:
 
  for (int i1 = 0; i1 < 10; ++i1) {
    for (int i2 = i1 + 1; i2 < 10; ++i2) {
      for (int i3 = i2 + 1; i3 < 10; ++i3) {
        // Do something
      }
    }
  }
However, this is kind of ugly and you cannot easily make it work for subsets of size k. The solution is using a recursive function. I believe the name for this technique is "backtracking". It's a little bit involved, but it's very powerful.
 
void build_subsets(int *subset, int k, int already_built, int first_index) {
  if (already_built == k) {
    // Do something
  }
  else {
    for (int i = first_index; i < 10; ++i) {
      subset[already_built] = i;
      build_subsets(subset, k, already_built + 1, i + 1);
    }
  }
}

EDIT: In case it's not entirely clear how you get this started, here's a complete program:
#include <iostream>

void build_subsets(int *subset, int k, int already_built, int first_index) {
  if (already_built == k) {
    for (int i = 0; i < k; ++i)
      std::cout << subset[i] << ' ';
    std::cout << '\n';
  }
  else {
    for (int i = first_index; i < 10; ++i) {
      subset[already_built] = i;
      build_subsets(subset, k, already_built + 1, i + 1);
    }
  }
}

int main() {
  int subset[3];
  build_subsets(subset, 3, 0, 0);
}
Edited by Álvaro

Share this post


Link to post
Share on other sites

Generating all possible combinations of route in a graph? ... But I can't predict how many destinations I have in advance ...


As above, there are several ways to interpret the question.

It looks like a question about pathfinding to me. If you are looking to find a path along a bunch of nodes, there are a few common algorithms.

For finding the shortest path between two points there is Djikstra's two point shortest path algorithm. (Google it). Unfortunately the algorithm takes a long time and a lot of space, so there is a way to guide it to faster results. By adding a heuristic -- such as the physical distance on a map -- it becomes the A-Star or A* algorithm, which is extremely common in games. A* can potentially give a less than optimal path, but it is usually good enough and the speedup is worth the rare exception.

For finding the shortest paths between all points on a map, there are algorithms to compute all the paths and store them, but the space required is usually enormous. Every pair can potentially have a length of the full set of nodes. The number of permutations I believe uses the nPr function and each path could be the full set of points in the worst case (such as a circular ring where every node must move in a single direction around a ring). So the set of all pairs for 16 nodes is up to 240 * 16 = 3840 entries. A 10x10 grid would have 9900 pairs and up to 990000 elements for the full set. A map of 500x500 cells would completely overflow my calculator and could require many terabyts or even petabytes or exabytes to store the full map in a worst case scenario.

Games usually just calculate the shortest paths as needed at runtime.

Share this post


Link to post
Share on other sites

For finding the shortest paths between all points on a map, there are algorithms to compute all the paths and store them, but the space required is usually enormous. Every pair can potentially have a length of the full set of nodes. The number of permutations I believe uses the nPr function and each path could be the full set of points in the worst case (such as a circular ring where every node must move in a single direction around a ring). So the set of all pairs for 16 nodes is up to 240 * 16 = 3840 entries. A 10x10 grid would have 9900 pairs and up to 990000 elements for the full set. A map of 500x500 cells would completely overflow my calculator and could require many terabyts or even petabytes or exabytes to store the full map in a worst case scenario.


Computing all shortest paths in a graph with N nodes can be done in O(N^3) time with O(N^2) memory. See https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

The result is stored as a single matrix indicating the total cost for the path between any two nodes. Reconstructing the paths from this information is very easy.

Share this post


Link to post
Share on other sites

For finding the shortest path between two points there is Djikstra's two point shortest path algorithm. (Google it). Unfortunately the algorithm takes a long time and a lot of space, so there is a way to guide it to faster results. By adding a heuristic -- such as the physical distance on a map -- it becomes the A-Star or A* algorithm, which is extremely common in games. A* can potentially give a less than optimal path, but it is usually good enough and the speedup is worth the rare exception.


I believe that, given a proper heuristic (distance to destination, for instance), A-star is guaranteed to return an optimal result. (See the "Admissibililty" section of the wikipedia article https://en.wikipedia.org/wiki/A*_search_algorithm) I think this is actually the common case for games, so you'll get an optimal result. Have I missed something?

 

Geoff

Share this post


Link to post
Share on other sites

 

For finding the shortest path between two points there is Djikstra's two point shortest path algorithm. (Google it). Unfortunately the algorithm takes a long time and a lot of space, so there is a way to guide it to faster results. By adding a heuristic -- such as the physical distance on a map -- it becomes the A-Star or A* algorithm, which is extremely common in games. A* can potentially give a less than optimal path, but it is usually good enough and the speedup is worth the rare exception.


I believe that, given a proper heuristic (distance to destination, for instance), A-star is guaranteed to return an optimal result. (See the "Admissibililty" section of the wikipedia article https://en.wikipedia.org/wiki/A*_search_algorithm) I think this is actually the common case for games, so you'll get an optimal result. Have I missed something?

 

Geoff

 

 

A* is optimal if you fully close the last node to ensure that there are no neighboring paths that would be shorter. The difference is trivial in some cases, so the step is optional depending on what you're doing. There are several other ways to 'relax' A* in order to fit into performance or memory constraints, such as https://en.wikipedia.org/wiki/SMA*

 

Regarding OP, if he's searching for paths to multiple destinations then Dijkstra could do it. Just keep expanding until you've touched all the goal nodes and you should end up with a sort of 'all destinations' map. Could take up a lot of memory though depending on the problem space. Without knowing what you're actually doing it's hard to say what the best option would be.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement