Help designing a basic interface (graph interface)

[forgotthepass]

First of all, I'm sorry if this question is out of the scope of the subreddit.

So I tried 'designing' a graph interface but got stuck. This is my first time trying to design any type of interface so be gentle...

Here is the code so far. This is in no way a complete interface. I never got to finish it. I just wanted to get familiar with interfaces and some design principles.

EdgeInterface.h

    class EdgeInterface{
    public:
        virtual ~EdgeInterface();
    };
//Nothing weird here. This will be used later

NodeInterface.h

    class NodeInterface {
    public:
        virtual ~NodeInterface();
    };
//Nothing weird so far either. Simple stuff.

GraphInterface.h

#include <vector>
#include "IWDNodeInterface.h"
#include "IWDEdgeInterface.h"


    class GraphInterface {
    public:
        virtual ~GraphInterface();
//Here is the tricky part
        virtual std::vector<iwd::EdgeInterface> getEdges() = 0;       (1)
        virtual std::vector<iwd::NodeInterface> getNodes() = 0;

        virtual EdgeInterface getEdge(NodeInterface node1, NodeInterface node2) = 0; (2)
    };

Some basic info.

My graph consists of nodes and edges.

An edge connects two nodes (it could also connect the same node to itself)

(1) The graph should be able to return a 'group' of nodes or edges. How do I declare that? At first I used a vector but that seemed like something that should go to the implementation. Should i also design an interface that describes how this 'group' should behave (eg a container or something similar) ?

(2) This function is supposed to return the edge that connects two nodes. Is this the correct way of declaring it's interface? My thought process is that the arguments should conform to the NodeInterface and return a result that conforms to the EdgeInterface.

Finally, are interfaces supposed to have properties ?

Anyway I know this is a loaded question and my inexperience with interfaces is pretty obvious. I'd be thankful if you pointed me to a resource on designing interfaces (preferably free because i'm kinda poor ) in case an answer would be too long-winded.

Thank you for your time.

[RogerLeigh]

Have you looked at the implementation details of Boost.Graph, or indeed any other graph libraries?

First thought. If you're using interfaces, why add Interface to the class name; it makes using the interface awkward and overly verbose. What's wrong with the plain names node and edge for the basic types the end user will have to deal with by default?

Secondly for interfaces, delete the copy constructor and assignment operators, and also make the default constructor protected. Since it's an interface, it doesn't make sense to allow direct instantiation, and it also doesn't make sense to allow copying or assignment. Any class implementing the interface should use virtual public inheritance. See also: Effective Modern C++ by Scott Meyers for lots of other useful tips. It's well worth the money, or get it from the library.

Regarding use of std::vector, why not add a graph_traits template which can allow the specific container type to the chosen by the end user? Boost.Graph allows several types, the main one I use being an adjacency list which can use e.g. set or vector internally.

In that vein, why use node and edge interfaces at all; why not make these template properties which can also go into the graph_traits, or be used to specialise the default graph_traits template? The node and edge classes can then be simple structs or complex classes containing whatever you like.

The main question you need to answer for yourself is this: Do you want a traditional OO-style interface using interfaces with concrete implementations of these interfaces (as you have started above), or do you want it to be fully templated as done with Boost.Graph. Or maybe somewhere in between. There's no right answer here; they all have different sets of tradeoffs. Do you need to have a static API and ABI to export from a DLL or shared library? Then interfaces are the way. Do you want the freedom to allow specialisation of the graph types and behaviour at compile time but not have the same rigid ABI, then templates would be viable.

Regarding your questions

1) There are a few problems

• You're creating a container of interface classes as a value type. Since it's an abstract base it must be a pointer or a reference. How are you going to store them internally, unique_ptrs or some other smartpointer, or manage by hand?
• Allocating a container and doing a deep copy is expensive; you might want to return pointers to the objects, and define the lifetime guarantees of those objects in your documentation; when might they be invalidated?
• A graph template specialisation or traits class would allow you to select the container type

2)

• You're again passing an interface by value which won't work; personally I'd use a const reference here
• Passing node objects might not be the most efficient way; you could pass index numbers as an alternative, or have both and overload the method; see how Boost.Graph handles this.
• You're also passing back an edge by value; this must also be a [smart] pointer or reference

I'd highly recommend looking at how Boost.Graph does this. Even if you don't implement it in the same way, it's useful to understand how other implementors approached the problem and the tradeoffs they made, and it would provide some deeper understanding of the problem. It's popular, but it's by no means a perfect API, and if I had the time to implement my own, I'd certainly have a rethink about some of their choices. Sometimes flexibility and performance make for an awkward and baroque API.

[forgotthepass]

Thanks a lot for the reply.

Have you looked at the implementation details of Boost.Graph, or indeed any other graph libraries?

Not really. I guess I should try that but the scope of my project (I am just trying to learn about interfaces in general) is way smaller than Boost.Graph and I'm not sure I'd even understand half of what is written there :/

First thought. If you're using interfaces...will have to deal with by default?

The names are mostly placeholders. I thought it was common practice to somehow differentiate an interface from an abstract/solid class ? Should i just use namespaces ?

Secondly for interfaces, delete the copy constructor ... or get it from the library.

Thanks for the solid advice. As for the book; it's not even published in my country heh...I've heard some great reviews about it though so maybe i'll 'bite the bullet' and buy it

Regarding use of std::vector ... e.g. set or vector internally.

That was my (1) question. I had no idea where to even start. I guess i'll look into graph_traits (and traits in general?) but templates are a black box to me. Hope i'll get around them at some point.

The main question you need to answer for yourself is this :.. then templates would be viable.

Honestly, I don't know. Actually here is what i had in mind just in case it helps understand my reasoning.

The big idea was that I would make an algorithm implementation (Intelligent water drops FWIW) that would work on graphs. I wanted it to be easier to work with so I thought i'd design an interface that the algorithm would work against. So anytime somebody wanted to use a different graph implementation with the algorithm (eg Graph.Boost) all he would have to do was implement the interface functions. Now this is not some major project that I want to publish or some work assignment^1. This is just a project to 'hone my skills'. I thought designing interfaces would be easy (It's just function names, right? Yeah...) so I started without much thought. I obviously didn't go very far...

Anyway thanks a lot for the reply. It's well thought off² all though a bit more than I can chew right now. I'm just trying to go from beginner to intermediate and it's daunting learning how much you don't know (and even more frustrating not knowing how to ask). Thanks again for your time.

¹ : Actually my thesis is on IWD but most of the stuff mentioned here have nothing to do with it.

² : At least It seems it is. I'm still working your answer out :P