[FEAT] add a function to return a list of edges connected to a vertex for undirected graphs

[EnbyMonkey]

Feature Request

A function get_connected_edges(vertex_id_t) or get_edges(vertex_id_t) or something like that, that returns a list of edge_id_t's for a vertex.

Why is this important?

The edges of my graph store information about the relationship between vertices (as well as a weight). I want to iterate over the edges of a vertex, to look for edges with a certain type of relationship. Roughly the edges are keeping track of relative positions of nodes, so for example if two nodes are one above the other, or one beside the other. So I want to iterate over the edges of a vertex to find all neighbouring vertices that are one above the other, for example.

Describe the solution you'd like

Add a function in graph.h (and other functions wherever else needed) which takes as input a vertex_id_t and returns an edges_t = std::unordered_set<edge_id_t> (like in graph.h line 20).

Describe alternatives you've considered

For now, I am using get_neighbours, then getting the vertex_id_t's of each neighbour, then getting the edge_id for each neighbour, and then getting the edge. This solution works but is a bit goofy imo

Additional context

I'm using this library for a force-directed graph layout, and the graphs in question are planar nearly everywhere.

Are you willing to contribute?

Sure, I could probably write some or most of the necessary code

Checklist

Please check the following before submitting the issue:

• [x] I have searched for similar feature requests in the issues.
• [x] This feature is not already implemented in the library.
• [x] I have provided a clear and concise description of the feature request.
• [x] I have explained why this feature is important and how it benefits the library and users.
• [x] I am willing to contribute to the development of this feature (if applicable).

Please note that feature requests are subject to review and may or may not be implemented in the library.

[github-actions[bot]]

Hi there! Thank you for creating your first issue on the Graaf library, we will look into it shortly. In the mean time, please make sure the issue has the correct labels set.

[EnbyMonkey]

I thought I would start trying to implement this before working on in/out edges. Although now that I've spent some time on it I wonder if it's not worth it, and whether you prefer library users to implement this sort of thing on their own end.

[github-actions[bot]]

Marking this issue as stale. It will not be automatically closed.

Even though the maintainers of Graaf may not always have time to take a look in a timely fashion, your contributions are much appreciated. Please allow some time for @bobluppes to take a closer look.

[bobluppes]

Hi @EnbyMonkey, thanks for opening this issue (and sorry for the delay, it has been a while 😅)!

Looking into this a bit more, I think your suggestion to add an accessor for the edges of a vertex is a nice idea! I would see it as the dual of the existing get_neighbors. For undirected graphs the behvior is clear to me as we can simply return all associated edges of the vertex. However, for directed graphs the behavior is less clear; do we return the in-edges, out-edges, or both?

Returning out-edges should be no problem, but the tricky part is in the computation of the in-edges. Currently the graph class is implemented with an adjacency list, which stores a single "edge list" per vertex. Computing the in-edges for a directed graph therefore means doing a pass over the entire data structure.

For now I see nothing stopping us from introducing a get_edges method (and maybe constraining it to undirected graphs only). However, before tackling get_in_edges/get_out_edges I am wondering if it makes sense to introduce a "bidirectional" graph specialization.

[github-actions[bot]]

Marking this issue as stale. It will not be automatically closed.

Even though the maintainers of Graaf may not always have time to take a look in a timely fashion, your contributions are much appreciated. Please allow some time for @bobluppes to take a closer look.

[synanki]

assign me this issue @EnbyMonkey

[github-actions[bot]]

Marking this issue as stale. It will not be automatically closed.

Even though the maintainers of Graaf may not always have time to take a look in a timely fashion, your contributions are much appreciated. Please allow some time for @bobluppes to take a closer look.