Designing a generic graph

Question

I am looking at designing a Graph class, that should work for both lists and matrix.
For ex: something like,

class Graph {
public:
    virtual ~Graph() = 0;
    virtual bool AddEdge(int src, int dest)=0;  
    virtual int Size() = 0;
};

Now, I can have two derived classes(G_Matrix, G_AdjList), each of which implements it in its respective way.
I was curious to know, whats the best way to extend the design to incorporate the respective algorithms (ex: dfs, bfs etc) on each of these. What I'm thinking is to have an interface like GraphAlgo, with some generic functionalities like below and have them implemented with concrete types (Bfs, Dfs , Dijkistra etc).

class GraphAlgo {
public:
    virtual ~GraphAlgo()=0;
    virtual std::string Traversal(int src) = 0;
    virtual bool DetectAllPaths(int src, int dest, std::string &path ) = 0;
    virtual bool DetectCycle()=0;
};

I've a few questions :

1. What is the best way to incorporate the concrete classes from the above into the concrete Graph classes defined above ?

2. Considering the algorithms vary between the list & matrix representations of the graph, what is the best way to represent them in the interface.

Answer 1

On one side you have an abstract graph with several possible concrete implementations.

On the other side you have a generic algorithms that work with these graphs, but that could have specific optimized implementation. So we need to decouple the abstract algorithm and the concrete implementations so that both can vary independently.

For this purpose, and in order to ensure the maximum flexibility, you could use the bridge pattern:

• The Abstraction would be a family of algorithm (e.g. search algorithms, path finding algorithms, etc...)
• The AbstractionImpl would be the specialisation of an abstract algorithm (e.g. BFS or A*)
• The Implementor would provide an interface the underlying services needed by the abstraction implementation and that could depend on the graph implementation.
• The ConcreteImplementor would provide a specific implementation of these services for a specific graph;

Remarks:

• This might in some cases be overkill, when the algorithm's implementation is straightforward and a strategy could just allow some variations, without necessarily decouple the implementation as strictly as when using an Implementor. Interestingly, structurally it would still look very similar to the Implementor, but the way it is used is slightly different way.
• In fact, your design may already flawed, looking at the path. The path is not a string ! The path can be represented as a succession of nodes in a string in the case of matrix representation. But for an adjacency list, where you could have several edges between the same nodes, you need to identify the edge you use to move to the next node. So you have here yet another abstraction.

Unrelated suggestion: Once you have finalised the design, I'd suggest to add a new form of graph that is neither defined by adjacency list, nor by a matrix, but by an adjacency function. Just to verify that your design is robust enough to work at a really abstract level.