Graph algorithms

[HekpoMaH]

Hello, do you have any graph algorithms implemented. I'd like to contribute with some if u haven't. I'll try to add one algo per week.

[faheel]

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.

[HekpoMaH]

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?

[faheel]

@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.

[HekpoMaH]

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).

[faheel]

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.

[HekpoMaH]

Waiting to add the data structures then :).

[Anita1017]

hello faheel, I would like to contribute graph algos.

[kbodurri]

Hello @alxmjo and @faheel!

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.

[chhawip]

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.

[alxmjo]

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.