0

I'm learning about graph algorithms, so to learn them better I'm beginning to write some of them using c++. For example, I created the code for implementing the Depth First Search algorithm. Here's the class structure I have:

template<class T>
class Graph
{
public:

    struct Edge
    {
        T src, dest;

    };

    struct visitCounts
    {
        int preVisitNum, postVisitNum;
    };
    
    // Default constructor
    Graph() {}
    
    // Graph Constructor
    Graph(std::vector<Edge> const &edges, T startingNode);

    void DFS();

    void restartDFS();

    void explore(T vertex);

    void previst(T vertex);
    
    void postvist(T vertex);

    // Prints the PreVisit and Post Visit numbers for each node in the graph
    void printPrePostVisits();

    void printGraph();

    // Finds nodes that have not been visited yet
    // Returns a vector of unvisited nodes
    std::vector<T> findUnvisitedNodes();

private:

    // Static integer to keep track of the number of visits we have done in total    
    static int currVisitNum;

    // Node where we start our DFS search
    T startingNode_;
    
    // marks which nodes have been visited. True = visited, false = not visited
    std::unordered_map<T, bool> visited_;

    // Keeps count the pre/post numbering for each node T
    std::unordered_map<T, visitCounts> visitCountMap_;

    // Adjacency list for graph
    std::unordered_map<T, std::vector<T>> adjList_;
};

I plan on writing more algorithms such as Bread-first Search, Dijkstra's,etc. I'm wondering if I should separate the algorithms into different classes and not just put them inside the Graph class. For example, DFS, Dijkstra, classes or perhaps just have a separate class that it's just for graph algorithms. Wondering what are the tradeoffs.

Right now I'm doing this just for educational purposes and the only place I'm planning on using these algorithms (at the moment) is in unit tests to make sure they are implemented correctly. But it would be good to know if they we're to be used in a production environment what would be a good way to structure a set of algorithms that rely on a graph data structure.

2
  • You might want to look at the Boost Graph Library for inspiration about one possible way to organize this. Sep 27, 2023 at 17:23
  • @Jerry Coffin Thanks right now everything is cereal.
    – KetDog
    Sep 28, 2023 at 11:56

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.