Data model, graph library, C++

Question

I am creating a C++ library for implementing graph algorithms. I am thinking about the appropriate representation of the class "Graph".

The are two main types of graphs (oriented / not oriented) and representations (list / matrix).

I do not have problems with algorithms...But I would like to propose a suitable and robust data structure (including the inheritance sequence of classes if needed).

Currently I do not use any special data structure representing graph, static methods have as input parameters incidence, adjacency... matrices.

Should such class keep both representations of graph or only one representation with conversion function between both representations? Which could be preferred?

This problem has been solved by a lot of people using different approaches.

Answer 1

Before reinventing the wheel you might take a look at boost::graph. Don't forget bundled properties.

Answer 2

Are you doing this for a class or as learning exercise? Because if not, as you pointed out, this problem has been solved many times. And as one looks through the various solutions, one realizes there are issues one hasn't even though of such as:

• directed/undirected graphs
• associating user data with nodes and edges
• sparse vs dense graphs
• large vs small graphs
• template vs non-template based
• dependency on other packages

and so on...

Try looking at some of the most popular implementations:

https://stackguides.com/questions/2751826/which-c-graph-library-should-i-use