-3

I am currently working on writing a C++ app whose purpose it is to essentially "demo" various graph algorithms. At the moment, I have a very bare-bones Graph class working (which utilizes Vertex and Edge classes) using edge-list representation (graph object has a list of vertex references where each vertex reference stores a list to incident edges), so I would like to begin adding tons of different algorithms to it.

The "problem" that I am seeing right now, is that these algorithms (at least the ones that I have learned) use various flags, or just additional fields for vertex and edge objects that you would not naturally put into a simple graph class. For example, for breadth-first search, the vertex object has discovered and predecessor fields that I really don't want to add to my basic class. It just seems far too inelegant.

I would like to hear your advice on what would be the most elegant way of using OOP and just C++ in general to tack on a variety of different algorithms to my graph. I would also appreciate any resources which would help me.

One idea that I had was making subclasses of my Graph/Vertex/Edge classes, for example BFSVertex, KruskalEdge, etc.

Improve this question
7
  • 2
    The issue with this question (and your approach) is that it deals with the vague notion of a class of problems, instead of focussing on specific cases. There are a lots of different possibilities for implementing a graph even without extra meta data for edges and vertices. There are even more possibilities when we try to introduce meta data. There may be also meta data like weights, coordinates, colors, flags which might not be algorithm specific, and other meta data which is. Hence I think in the current form this question is too vague to be answerable.
    – Doc Brown
    Apr 30 at 7:53
  • 2
    ... and no, there is no "most elegant way" in general to implement this in general, there are several different ways, each of them more or less suitable for the specific situation. That's why generic graph components are usually not simple classes, but libraries. If you want C++ examples, start with this list, or the Boost Graph lib
    – Doc Brown
    Apr 30 at 8:04
  • @DocBrown The graph is implemented as I mention in my original post, without any meta data that would be helpful for graph algorithms. I am merely asking for suggestions (or just for someone to point me in a direction) for how this is generally done. Perhaps a certain design pattern, or just a hint as to how to organize my classes. Nevertheless, thanks for the links which you've provided.
    – vovnsons
    Apr 30 at 9:27
  • "for how this is generally done" - my point is, this is a wrong assumption, there is no "general" solution, especially as long as the problem is so unspecific as presented here.
    – Doc Brown
    Apr 30 at 9:31
  • 3
    Start with something simple. For example, even for your breadth-first example, you could simply store the "discovered" fields completely outside of the graph, by using an std::unordered_set. That might be a good idea for meta data which is only required temporarily, for a specific algorithm. What you put into the unordered_set depends on how you identify the different edges in your specific graph implementations (Integer indexes? Pointers?
    – Doc Brown
    Apr 30 at 9:45

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.