How does the library address my Airports use case?

[akrzemi1]

The goal of this "issue" is to determine if this library can address my use case for graphs.

My application finds all "attractive" flight connections between two given airports. How "attractive" is defined is complicated, but the definition consists of at least these factors: small number of connections (ideally zero), cheap, short journey.

I store 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:

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
};

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 is max_connections + 1 or less.
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.

At high level, I suspect that I will need some form of a depth-first search that will additionally allow me to:

1. Exclude some vertices (or edges) based on the provided predicate.
2. Stop the search on the current branch (when I see that the max length is exceeded) and resume it from the next branch.

The questions to the authors:

1. Is the above a problem suitable for this graph library?
2. Which library components should I use to implement my use case?

[akrzemi1]

Stack Overflow told me that the algorithm I need is Yen's algorithm. So my question is: does graph-v2 support the Yen's algorithm (or equivalent) and some form of vertex/edge filtering?

[pratzl]

It's not on our targeted algorithms list. Andrew is the algorithm expert, so I'll have him answer your question.

Sent from Outlookhttp://aka.ms/weboutlook

---

From: Andrzej Krzemieński @.> Sent: Wednesday, May 14, 2025 11:04 AM To: stdgraph/graph-v2 @.> Cc: Subscribed @.***> Subject: Re: [stdgraph/graph-v2] How does the library address my Airports use case? (Issue #146)

[https://avatars.githubusercontent.com/u/2912717?s=20&v=4]akrzemi1 left a comment (stdgraph/graph-v2#146)https://github.com/stdgraph/graph-v2/issues/146#issuecomment-2880589778

Stack Overflowhttps://stackoverflow.com/questions/79620472/can-boost-graph-find-all-paths-from-a-to-b-in-a-graph-containing-less-than-n-edg told me that the algorithm I need is Yen's algorithmhttps://en.wikipedia.org/wiki/Yen%27s_algorithm. So my question is: does graph-v2 support the Yen's algorithm (or equivalent) and some form of vertex/edge filtering?

— Reply to this email directly, view it on GitHubhttps://github.com/stdgraph/graph-v2/issues/146#issuecomment-2880589778, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AB7NKESP4N2I75YWURQQ5JD26NLQTAVCNFSM6AAAAAB47BSPDSVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDQOBQGU4DSNZXHA. You are receiving this because you are subscribed to this thread.Message ID: @.***>

[pratzl]

Hi — We are planning to have filtering, but Yen’s algorithm seems very specialized. We are unlikely to have it in the first set of proposed algorithms.

Best, Andrew Lumsdaine

On May 16, 2025, at 12:54 PM, Phil Ratzloff @.***> wrote:

This Message Is From an Untrusted Sender You have not previously corresponded with this sender. See https://itconnect.uw.edu/email-tags for additional information. Please contact the UW-IT Service Center, @.@.> 206.221.5000, for assistance. It's not on our targeted algorithms list. Andrew is the algorithm expert, so I'll have him answer your question.

Sent from Outlookhttps://urldefense.com/v3/__http://aka.ms/weboutlook__;!!K-Hz7m0Vt54!luzHQa_me-WZcDl0yoAuLl0ZP5bJRIqbcZQMvIvQXH0ffeThHfuxDUFrOSg6zj64A0FTIKHX5Jnw$

---

From: Andrzej Krzemieński @.@.>> Sent: Wednesday, May 14, 2025 11:04 AM To: stdgraph/graph-v2 @.@.>> Cc: Subscribed @.@.>> Subject: Re: [stdgraph/graph-v2] How does the library address my Airports use case? (Issue #146)

[https://avatars.githubusercontent.com/u/2912717?s=20&v=4]akrzemi1 left a comment (stdgraph/graph-v2#146)https://urldefense.com/v3/__https://github.com/stdgraph/graph-v2/issues/146*issuecomment-2880589778__;Iw!!K-Hz7m0Vt54!luzHQa_me-WZcDl0yoAuLl0ZP5bJRIqbcZQMvIvQXH0ffeThHfuxDUFrOSg6zj64A0FTIBbxApVo$ Stack Overflowhttps://urldefense.com/v3/__https://stackoverflow.com/questions/79620472/can-boost-graph-find-all-paths-from-a-to-b-in-a-graph-containing-less-than-n-edg__;!!K-Hz7m0Vt54!luzHQa_me-WZcDl0yoAuLl0ZP5bJRIqbcZQMvIvQXH0ffeThHfuxDUFrOSg6zj64A0FTIE5TIlB3$ told me that the algorithm I need is Yen's algorithmhttps://urldefense.com/v3/__https://en.wikipedia.org/wiki/Yen*27s_algorithm__;JQ!!K-Hz7m0Vt54!luzHQa_me-WZcDl0yoAuLl0ZP5bJRIqbcZQMvIvQXH0ffeThHfuxDUFrOSg6zj64A0FTIJJ-pNrl$. So my question is: does graph-v2 support the Yen's algorithm (or equivalent) and some form of vertex/edge filtering? — Reply to this email directly, view it on GitHubhttps://urldefense.com/v3/__https://github.com/stdgraph/graph-v2/issues/146*issuecomment-2880589778__;Iw!!K-Hz7m0Vt54!luzHQa_me-WZcDl0yoAuLl0ZP5bJRIqbcZQMvIvQXH0ffeThHfuxDUFrOSg6zj64A0FTIBbxApVo$, or unsubscribehttps://urldefense.com/v3/__https://github.com/notifications/unsubscribe-auth/AB7NKESP4N2I75YWURQQ5JD26NLQTAVCNFSM6AAAAAB47BSPDSVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDQOBQGU4DSNZXHA__;!!K-Hz7m0Vt54!luzHQa_me-WZcDl0yoAuLl0ZP5bJRIqbcZQMvIvQXH0ffeThHfuxDUFrOSg6zj64A0FTIMiUNbXX$. You are receiving this because you are subscribed to this thread.