Correct interface for a function on a base class and inherited class?

I have defined a base class DiGraph and a inherited class UnGraph as:

class DiGraph
{

    protected:

        long V;    // No. of vertices; Vertices are labelled from 0, 1, ... V-1.
    
        vector<list<long>> adj;      // Adjacency List of graph

    public:

        DiGraph(long V);  // Constructor, initialize V and resize adj;

        virtual void addEdge(long v, long w); // Add directed edge (v,w) to adj

        vector<list<long>> getadjL (); // Returns the adjacency list

        vector<vector<long>> getadjM (); // Computes and returns the adjacency matrix

};

class UnGraph: public DiGraph {

    public:

       void addEdge(long v, long w);   // Add undirected edge i.e add (v,w) and (w,v)


};

I have defined multiple functions with return value (and sometime arguments) as DiGraph such as:

DiGraph Kn (long n) {  // Returns the complete graph on n vertices
    DiGraph G(n);

    for (long i = 0; i < n ; i++) {
        for (long j = 0; j < n; j++)
            G.addEdge(i, j);
    }

    return G;
}

Now I want the ‘equivalent’ versions of these functions for UnGraph (i.e. the same function except the ‘addEdge’ function of DiGraph should be replaced with the ‘addEdge’ function of UnGraph and the class types should be changed. Do I have to make another copy of this function (for all the functions I have), or is it possible to write a single function for both base and inherited class?

I though of using function templates but then realized that you if you generalize a class T such as:

template <typename T> T Kn (long n) {  // Returns the complete graph on n vertices
    T G(n);

    for (long i = 0; i < n ; i++) {
        for (long j = 0; j < n; j++)
            G.addEdge(i, j);
    }

    return G;
}

but then realized you can’t use any of it’s fields like T.addEdge(u,v) in the function body. Any ideas?

>Solution :

As long as you provide a constructor for UnGraph that accepts a long, e.g.

UnGraph(long V) : DiGraph(V) {}

you can implement Kn as a template function taking GraphType as template parameter (e.g. DiGraph or UnGraph):

template <typename GraphType>
GraphType Kn (long n) {
  GraphType G(n);
  for (long i = 0; i < n ; i++) {
    for (long j = 0; j < n; j++)
      G.addEdge(i, j);
  }
  return G;
}

and use it like

DiGraph completeDi = Kn<DiGraph>(4);
UnGraph completeUn = Kn<UnGraph>(4);

That compiles for me.

Leave a Reply