Comments (10)
@HekpoMaH I'm adding two classes, one each for directed and undirected graphs, each having two versions which use either an adjacency list or an adjacency matrix as the underlying data structure. A usage example for one of those is as follows:
// for directed graph using adjacency list:
#include "DataStructures/Graph/List/DirectedGraph.hpp"
/* or, for directed graph using adjacency matrix:
#include "DataStructures/Graph/Matrix/DirectedGraph.hpp"
*/
...
DirectedGraph digraph;
for (unsigned int v = 1; v <= 8; v++)
digraph.add_vertex(v);
digraph.add_edge(1, 5, 7);
digraph.add_edge(1, 6, 4);
digraph.add_edge(2, 8, 3);
digraph.add_edge(3, 1, 3);
digraph.add_edge(3, 2, 6);
digraph.add_edge(4, 8, 8);
digraph.add_edge(5, 1, 5);
digraph.add_edge(5, 3, 9);
digraph.add_edge(6, 3, 8);
digraph.add_edge(6, 7, 9);
digraph.add_edge(7, 2, 4);
digraph.add_edge(7, 4, 7);
digraph.add_edge(8, 4, 5);
digraph.add_edge(8, 5, 6);
for (unsigned int v = 1; v <= 8; v++) {
cout << "Neighbours of " << v << ":\n";
auto neighbours = digraph.neighbours(v);
for (auto n : neighbours)
cout << n << " (" << digraph.get_edge(v, n) << ")\n";
}
The reason for adding these classes is so that everyone will have a common data structure to implement graph algorithms on, which will make the code for all of these algorithms more compatible with each other. For example, while implementing topological sort for a directed graph, you can pass the graph object to the DFS method without having to rewrite it to match your graph's specifications.
from proalgos-cpp.
Thanks for your interest @HekpoMaH! I'll soon be adding the graph data structures (directed and undirected) which you and others can use to implement graph algorithms.
from proalgos-cpp.
Tbh IDK in what format you want the representation. Depending on needs I just use array of vectors (vector[] for list representation) or 2d array (for matrix representation) or both when needed. What data structures are you adding?
from proalgos-cpp.
Makes sense, but what about other graph representations? Consider Dinitz algorithm, where you might want to represent it as doubly linked list of the edges. Are we free to use other representations, whenever these are not applicable?
Another question is how much you aim your code to be OOP i.e. files with classes for data structures that the algo uses, as I usually write my algorithms in one "big" file (most of them do not exceed 200 lines with none exceeding 500).
from proalgos-cpp.
Yes, you can use other representations where its necessary.
And as for programming paradigm, I use classes to define data structures, and in programs that don't require any user-defined data types, I use modular (procedural) programming. File size doesn't matter. The program should be easily readable and well-documented.
from proalgos-cpp.
Waiting to add the data structures then :).
from proalgos-cpp.
hello faheel, I would like to contribute graph algos.
from proalgos-cpp.
I am new to the open-source community, and I find this repo a great place to start contributing.
May I ask about the progress of the graph implementation (Adjacency Matrix and/or List)? I could start by implementing them. If that's being taken care of already, I would like to implement any graph algorithm, such as Dijkstra's algorithm or graph traversal algorithms (DFS/BFS). Please let me know. Thanks.
from proalgos-cpp.
Hello @faheel ! Since I am new to the open source community, I'd like to contribute to your repository for graph implementation algorithms. I could start implementing minimum spanning trees algorithms or something like pagerank or centralized graph algorithm.
If you want some specific implementation from me, kindly let me know.
from proalgos-cpp.
There are several parts to this:
- Implement data structures for graph algorithms.
- Implement individual algorithms based on these data structures.
With that in mind, I'm going to close this issue and open new issues specific to the issues above. See #335.
from proalgos-cpp.
Related Issues (20)
- Add Exponential search HOT 4
- Add Interpolation Search HOT 1
- Radix Sort Test cases HOT 3
- make[1]: *** No targets specified and no makefile found. Stop HOT 4
- add "longest common subsequence in the given strings" problem
- add segment tree data structure HOT 2
- Greedy algorithms. HOT 1
- Algorithm for binary tree traversal HOT 3
- Addition in data structures : AVL tree HOT 1
- Fix radix sort HOT 2
- Adding a new backtracking algorithm HOT 1
- Want to add documentation for linked list HOT 1
- Kth largest element in an array using priority queues HOT 3
- Euclidean algorithms HOT 1
- Euler's Totient HOT 1
- Sudoku Solver HOT 1
- Implement BFS and DFS HOT 1
- windows version fails to build HOT 2
- queue and stack leak HOT 2
- two algorthims fail -fsanitize = address HOT 3
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from proalgos-cpp.