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

Question

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?

You can override functions defined in base classes and you can also hide functions in base classes from derived classes. https://www.w3schools.com/cpp/cpp_polymorphism.asp — Richard Bamford, Nov 23 '22 at 18:06
Are you looking for something like the [_Template Method_](https://sourcemaking.com/design_patterns/template_method) design pattern? — πάντα ῥεῖ, Nov 23 '22 at 18:07
@RichardBamford Sorry, I should have mentioned, the function DiGraph Kn (long n) is not defined in te base class. It is a generic function which returns an object of class DiGraph which it creates within the function body. — Anon, Nov 23 '22 at 18:07
@πάνταῥεῖ If that is general function templates, then I'm not sure how you would use them. Because as I mentioned in the question, you can't use assume any field of the generic class T which we define a template over. — Anon, Nov 23 '22 at 18:09
@Kaind Well you could have a templated function in your abstract base class (+ default implementation) easily. Your example doesn't even mention how you intend to introduce template parameters (for the vector stuff I guess??). Maybe elaborate better in your question. — πάντα ῥεῖ, Nov 23 '22 at 18:14
@πάνταῥεῖ Edited the question to show what type of template abstraction I had in mind. Rulle below has given an answer which compiles, but I don't understand why. Additionally I cannot add this function Kn in the base class as the base class must only store information about the graph in hand. The function Kn returns some graph and must be outside. — Anon, Nov 23 '22 at 18:19
Another way to go with completely static polymorphism could be to use the famous [CRTP](https://stackoverflow.com/questions/4173254/what-is-the-curiously-recurring-template-pattern-crtp). — πάντα ῥεῖ, Nov 23 '22 at 18:20
@Swift-FridayPie there are several varieties, including the _Mixin Pattern_ as used by the MS ATL. — πάντα ῥεῖ, Nov 23 '22 at 18:30

score 1 · Accepted Answer · answered Nov 23 '22 at 18:09

1

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.

answered Nov 23 '22 at 18:09

Rulle

4,496
1
15
21

How does this work? Shouldn't the compiler throw an error? Not every class GraphType would have a member function addEdge, no? I'm happy it works, but I'm so confused as to why... – Anon Nov 23 '22 at 18:13
1

The compiler will only check that the member function `addEdge` exists for the actual types for which the template is instatitated, which in this case happens to be `DiGraph` and `UnGraph` in the calls `Kn(4)` and `Kn(4)`. – Rulle Nov 23 '22 at 18:21
If this is so, then why do we need to define a constructor for the inherited class UnGraph to make this work? – Anon Nov 23 '22 at 18:22
@Kaind it won't work with`Kn()` if `AsinineGraph` doesn't have that member available. The function sets restriction on type it can use – Swift - Friday Pie Nov 23 '22 at 18:23
1

@Kaind Because that constructor is called on the line `GraphType G(n);` when you call `Kn(4)`. That is, `GraphType` in that case will be the type `UnGraph` and therefore a constructor that accepts a `long` must exist. – Rulle Nov 23 '22 at 18:24
@Rulle But I thought the constructor of DiGraph would be inherited by UnGraph, if I don't define one for UnGraph? (Asking as it is possible other functions which I define use some other member functions in DiGraph, in this case should I also define their equivalent versions in UnGraph?) – Anon Nov 23 '22 at 18:26
1

@Kaind By default, constructors are not inherited from derived classes, see e.g. http://cplusplus.bordoon.com/inheriting_constructors.html . But more recent versions of C++ have features to facilitate inheriting constructors, see for example https://stackoverflow.com/a/434784/1008794. – Rulle Nov 23 '22 at 18:33

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

1 Answers1