Implement data structures for graph algorithms
alxmjo opened this issue · 24 comments
In order to add graph algorithms, we must first add graph data structures. We'll need data structures for both directed and undirected graphs. We'll want to be able to add vertices and edges. In the end it'll be valuable to have implementations for both an adjacency list and an adjacency matrix.
If you're interested in adding this please explain your plan below so that we can get started. 🙂
See #70 for previous conversation on the subject.
I'm interested in doing this. I can implement adj. list and matrix for undirected graphs first. Do you think it's necessary to use classes?
Yes. Have a look at binary search tree and the linked list data structures.
Hello , I am interested in taking up the issue . I am currently new to open source and have been working on DSA for building my base foundation .
Thanks for the interest, @a-moreira and @Maverick12345678. Assigning to @a-moreira since he mentioned it first. If still open after two weeks has passed I'll put it back up for grabs to give others a shot. 🙂
@alxmjo Just to remind you I'm working on this :-) No need to put it back up for grabs yet!
@alxmjo I implemented the adjacency matrix data structure for graphs plus some methods. I haven't written the tests yet, but I'd like some thoughts and comments before proceeding to do that and to implement the adjacency lists. Should I open a pull request to show the code?
Of course. Just open it as a draft PR.
@alxmjo I opened the draft PR. I forgot the comments about the time and space complexities, I'll add them in the next commit. They're fairly easy to guess, though.
Thanks for the update. I won't be able to have a close look till this weekend or early next week. Thanks for being patient.
Is this Issue Still Open? Actually I Would Like add more features to Graph Data Structure such as BFS, DFS, Cycle Detection etc.
Please revert back if you find it appropriate. Also if you have more issue or you want to enhance any feature of a Data Structure, I would be really interested and excited in doing it.
I Would be glad to work on the algorithms of Graph for this issue,in case it is open, so kindly reply to this comment if the the issue is still open .
I'm interested in this and I would like to work on articulation point and bridges. If it's still open.
I Would be glad to work on the algorithms of Graph for this issue, in case it is open, Also if you have more issue or you want to enhance any feature of a Data Structure, I would be really interested and excited in doing it.
I would love to contribute, Can I work on it?
@Avish34 @akshatjain04 @Manoj0803 @bhavitjain @dcyrus @alxmjo I am working on this. I've been a little slow because of the pandemics, but I'm going to update it soon. As soon as I finish the Matrix and Adj. List implementations you can implement some algorithms if you want.
@a-moreira Since there are several other interested contributors, could we have an update on your progress?
@alxmjo Sure. I will deliver the data structures and tests by the end of this week so everyone can start implementing the algorithms.
@a-moreira Any progress / Is there anything I can help you with (although I'm hardly familiar with this repo)?
I've just learned several graph algorithms for building convex hulls and think it might be a good idea to implement them in this repo.
@SimonLammer @Avish34 @akshatjain04 @Manoj0803 @bhavitjain @dcyrus Yes, sure. Anyone who wants to do the adjacency list implementation of a graph, and any algorithms using it, is welcome. I really won't be able to do that in the near future. Just read the docs and follow the guidelines. If you have questions, just ask @alxmjo or me.
I want to contribute to the cause, I'm writing a generic struct so that it works for both directed and undirected graph variants, and there are two versions: one uses the list representation, the other uses the matrix representation. The struct has the methods as you've mentioned: the constructor initializes the adjacency data structure (list or matrix) and sets the number of vertices and edges (if provided any, 0 by default), there's a method to add vertices (though, I doubt if it is really helpful) and one to add edge. Finally, there's a default parameter that determines if the graph is weighted and if so, the add-edge method works likewise. Please assign me if the issue is still open, I'll be glad to help.
@hitch-hiker42 Others may be working on this issue, but don't let that keep you from working on them, too, especially if you'd like the practice.
It is alright, I actually implemented it in the afternoon and I liked the practice indeed. Good day 😄
This issue has been automatically marked as inactive because it has not had recent activity. It will be closed in 15 days if no further activity occurs. Thank you for your contributions.