Can Boost.Graph find all paths from A to B in a graph containing less than N edges?

Question

I have a use case for a graph algorithm related to finding flight connections, and I would like to determine if Boost.Graph is capable of addressing it.

My ultimate goal is to find all "attractive" flight connections between two airports given by the customer. My task in this SO question is a bit smaller though: I want to determine all interesting paths (in graph nomenclature) between the two given airports. For instance, when the client wants to fly from KRK to LHR, a possible path is KRK-FRA-LHR.

I have a list of all airports and their geographical coordinates:

struct Airport
{
  std::string name;
  double latitude;
  double longitude;
};

const std::vector<Airport> airports
{
  {"CDG", 49.009724,  2.547778  }, //  0
  {"FRA", 50.033333,  8.570556  }, //  1
  {"MUC", 48.353889,  11.786111 }, //  2
  {"LHR", 51.470020,  -0.454295 }, //  3
  {"LGW", 51.153629,  -0.182152 }, //  4
  {"KRK", 50.077778,  19.784722 }, //  5
  {"WAW", 52.165833,  20.967222 }, //  6 
  {"KTW", 50.474167,  19.08     }, //  7
  {"SIN", 1.359167,   103.989441}, //  8
  {"SYD", -33.947346, 151.179428}, //  9
  {"NRT", 35.765278,  140.385556}  // 10
};

I represent the connections between airports as a directed graph, where each vertex represents an airport, and each edge indicates that there is at least one direct connection between the two connected airports. For the time being, I store them as a vector of vectors of int, where the element in the outer vector at index i represents all outgoing edges of vertex i (but I can store them in whatever other way):

const std::vector<std::vector<int>> connections
{
// 0  1  2  3  4  5  6  7  8  9  10
  {   1, 2, 3, 4, 5, 6,    8, 9    }, //  0
  {0,    2, 3,    5, 6, 7,         }, //  1
  {0, 1,    3, 4, 5, 6,            }, //  2
  {0, 1, 2,          6,    8, 9,   }, //  3
  {0,    2,       5,       8,      }, //  4
  {0, 1, 2,    4,    6,            }, //  5
  {0, 1, 2, 3,    5,    7,       10}, //  6
  {   1,             6,            }, //  7
  {0,       3, 4,             9, 10}, //  8
  {0,       3,             8,      }, //  9
  {                  6,    8       }, // 10
};

Given this data, I want to write a function

std::vector<std::vector<int>> find_paths(int from, int to, int max_connections);

that will return all the paths in the graph that start in from and end in to and:

1. The number of edges in a pah is max_connections + 1 or less. (Nobody will buy a flight where they need to connect eight times.)
2. There are no cycles.
3. It does not include any vertex that represents an airport too far away from from and to. (This is to make sure that when I want to fly between two German airports, I will not get a solution via Australia.) So, there will be a predicate that for a given vertex v will return distance(v, from, to) which will tell if v is acceptable.

And, of course, I want to implement the function efficiently. That is, it would not be acceptable to compute loads of possible useless paths in one step only to discard most of them in the next step.

Thus my questions are:

1. Is this problem is suitable for Boost.Graph library?
2. What tools from Boost.Graph to use to solve the above problem?

I know that I can always implement this algorithm manually, so my question is not how to write it from scratch. My question is if I can implement the solution by composing components from Boost.Graph.

Answer 1

1. Is this problem is suitable for Boost.Graph library?

   • Pro: the model is essentially a graph. However, since your model is already an adjacency list, BGL doesn't necessarily improve your life much on the representation side (perhaps e.g. compressed sparse row graphs depending on your data set?).

   • Contra: because the algorithm you describe ignores classical graph algorithms. Classical graph algorithms will focus on tours, coverage, minimum cuts, edge weights; all to aid in optimization problems where brute-force is not viable.

     Your question seems to explicitly be about brute-forcing subsets of the graph. Graph theoretical algorithms are going to be of less value there.

     Even e.g. Yen's algorithm specifically focus on k-shortest paths, which would be a waste of time if the goal is to have the exhaustive set of paths (satisfying the criteria) anyways.

2. What tools from Boost.Graph to use to solve the above problem?

   • you might employ any of the graph models

     • adjacency_list, which is similar to what you showed
     • adjacency_matrix, which could improve on locality and edge lookup
     • compressed_sparse_row_graph which would reduce memory requirements in case of sparse graphs

   • alternatively you could adapt your current graph representation for use with BGL (by implementing the relevant concepts. Of course, you will want to answer the question whether one of the algorithms fits your scenario before that would be useful

---

What's Next?

You should probably first consider

• writing the bruteforce approach yourself - it's pretty trivial. The only risk is that the set of paths becomes too large.
• in that case the real question becomes: what do you need the full set of paths for? Is this merely to do some statistics (in that case you might tweak the algorithm to discard the concrete predecessor information, and just count unique paths)

On the boost mailing list I already suggested a way to optimize selecting the Airports within allowable range (see also here) from (source,target) using Boost Geometry. Given the current sample size this would very likely be overkill.

I'm tempted to show answers to both first steps, but I feel I might be wasting time since you will likely be able to refine the requirements based on the questions raised.