CODEWITHSUNDEEP
c++algorithmdata-structures
Avinash
Avinash

Reputation: 13267

Graph Library API design

I am writing my own Graph library Graph++, I have question regarding what should interface return. For example What should my BFS return, I am confuse on the point that whether it should return set of vertices visited in the order , or should I have callback function, which will get invoked during each visit.

What could be the best option so that my library will easily consumable.

Upvotes: 0

Views: 582

Answers (3)

Ferenc Mihaly
Ferenc Mihaly

Reputation: 61

I don’t want to be unhelpful or sound arrogant. This is just a personal opinion and you should take it for what it is worth. You did not say why you are writing this library, so I’ll assume you have a specific problem to solve. If you are doing it just for fun or to learn, please go ahead and disregard the reminder of this reply.

Graphs are extremely generic abstractions. Any data structure more complex than a tree is a graph. Most programs have such data structures. For example, a web site containing linked pages is a graph. So is a representation of a map. However, when you think of these as graphs, you ignore all differences between web sites and street maps and focus on the only thing that it is common.

In the vast majority of cases, the details you are trying to abstract away, the fact that web pages are HTML, links are URLs, streets have speed limits, intersections have traffic lights, and so on, are more important. If you start your implementation with a graph abstraction, by the time you implement these other details on top of it you’ve got yourself into quite a mess. It is much better to start with other, more important abstractions as building blocks and connect those together to form a graph. Sure, you won’t get the shortest path algorithm for free for your street map, for example, but you are likely interested in the fastest route anyway, for which you need speed limits, traffic lights, and other information.

I guess what I’m trying to say is that I see very limited uses for a generic graph library. It is nice that we have the Boost Graph Library, but AFAIK, not many people are using it.

Upvotes: 3

Puppy
Puppy

Reputation: 147036

In C++11, prefer functional approach to iterative. In C++03, use iterator strategies.

Upvotes: 1

phs
phs

Reputation: 11061

A recurring pattern in the stl is to offer iterators. Your traversal algorithms might return a start iterator, and the library user could increment it as desired, while comparing against an end() iterator that either it or the graph provides.

The visitor pattern may also be relevant to your interests.

Upvotes: 3

Related Questions