Improving Graph implementation with more functions

[nith2001]

Feature description

I noticed that in some graph implementations (such as the one in graph_list.py, there's only one function, add_edge(). However, this does not allow floating nodes to exist, nor does it allow nodes and edges to be deleted. To make the graph implementation a lot more feature rich. I would like the recommend the following functions for any graph implementation that could use it (this example is for graph_list.py:

• add_vertex(self, vertex: T) -> GraphAdjacencyList[T]:
• remove_vertex(self, vertex: T) -> GraphAdjacencyList[T]:
• remove_edge(self, source_vertex: T, destination_vertex: T) -> GraphAdjacencyList[T]:
• clear_graph(self)

Each of these functions would be dummy-safe, so no need for error-throwing (unless we want to do that). So if the user wants an edge or node to be deleted that doesn't exist, the functions would run existence checks before doing anything hazardous, execute the request if possible, otherwise skip it, and then return successfully.

Unless this is something that y'all don't want implemented, I would like to take on this issue. Can I get a confirmation that I can work on this?

Edit: I noticed these were implemented in the other language repos, so I'm assuming it's cool to work on it.

[rohan472000]

Thank you for your proposal to add additional functionality to the graph_list.py implementation. The suggested functions, add_vertex(), remove_vertex(), remove_edge(), and clear_graph() would certainly make the implementation more versatile and feature-rich. It is important to ensure that these functions are dummy-safe, as you have suggested, to prevent any potential errors or issues.

Before proceeding with this work, it would be best to confirm that is this an area that our contributors should focus on? Please discuss with @cclauss @tianyizheng02.

Once discussed, anyone is welcome to proceed with the implementation.

[nith2001]

Sure, would love to discuss it with them (either through this thread or elsewhere, in which case I would appreciate any redirection to a different chat application if necessary). I've already completed the implementation for graph_list.py and I was going to move on to graph_matrix.py on my local fork. But ngl, graph_matrix.py looks like it could use some remodeling and implementation in terms of how node values are chosen, maybe modeling it similar to graph_list.py.

[cclauss]

We try not to slow down implementation so if you think that a pull request would be a useful addition to this project then please do not wait for permission. It is easier for all concerned to see the Python code and judge it on its merits.

It is a correct statement to say that most files focus on a single algorithm instead of all the possible manipulations that can be done with all forms of a data structure but this is not a hard rule. If you want to create a complete Graph data structure / class with lots of functions / methods and covering many different types of Graph then that would be acceptable as well. We love to see strong tests and guards against accidental misuse.

[nith2001]

Sounds good! I'll get a PR up later.

[cclauss]

the functions would run existence checks before doing anything hazardous, execute the request if possible, otherwise skip it, and then return successfully.

It is quite Pythonic to raise Exceptions and "Errors should never pass silently" is part of the Zen of Python.

• python3 -c "import this"

[nith2001]

@cclauss Fair! Then for functions listed above, should errors be thrown if for example, the edge to be deleted doesn't exist, or the node to be added already exists? I assumed not because the existing implementation for add_edge seems to just create nodes in case they don't exist before adding the edge.

[cclauss]

Let's not assume that the current implementations are perfect. -- They are not. Let's make future implementations as perfect as we know how. That means that appropriate Exceptions should be raise if there are errors in the input.

[nith2001]

Hmmm, sounds good. Then as you mentioned, I'll write up the code such that if any input parameters are faulty in any way (such as referencing non-existent or existent nodes and edges when they shouldn't), I'll have the appropriate exception thrown in all cases, and minimize any hand-holding in the back-end.

To make this easier on the client, I'll include contains_edge() and contains_node() functions as well.

[nith2001]

Update: finished implementations for graph_list.py and graph_matrix.py with all of the requested modifications, currently in the process (25% done) of writing tests for both using randomized inputs. This part is taking a hot sec because it's unironically harder than the graph implementation, but it's in progress!

[cclauss]

Let's move this discussion to #8730