Graph Library API design

Question

J'écris ma propre bibliothèque graphique Graph++, j'ai une question concernant ce que l'interface doit retourner. Par exemple Quel devrait être mon retour BFS, je suis confus sur le point que si elle devrait retourner ensemble de vertices visité dans la commande, ou devrais-je avoir callback function, qui sera invoqué lors de chaque visite.

Quelle pourrait être la meilleure option pour que ma bibliothèque soit facilement consommable.

Answer 1

Un motif récurrent dans la STL est d'offrir des itérateurs. Vos algorithmes de traversée peuvent renvoyer un itérateur de départ et l'utilisateur de la bibliothèque peut l'incrémenter comme vous le souhaitez, tout en comparant avec un itérateur end() fourni par lui ou par le graphe. Les codes visitor pattern peuvent également être pertinents pour vos centres d'intérêts.

Answer 2

En C++ 11, préférez l'approche fonctionnelle itérative. En C++ 03, utilisez des stratégies d'itérateur.

Answer 3

Je ne veux pas être inutile ou sonore arrogant. C'est juste une opinion personnelle et vous devriez le prendre pour ce que ça vaut. Vous n'avez pas dit pourquoi vous écrivez cette bibliothèque, donc je suppose que vous avez un problème spécifique à résoudre. Si vous le faites juste pour le plaisir ou pour apprendre, s'il vous plaît allez-y et ne tenez pas compte du rappel de cette réponse.

Les graphiques sont des abstractions extrêmement génériques. Toute structure de données plus complexe qu'un arbre est un graphique. La plupart des programmes ont de telles structures de données. Par exemple, un site Web contenant des pages liées est un graphique. Ainsi est une représentation d'une carte. Cependant, quand vous pensez à ces graphiques, vous ignorez toutes les différences entre les sites Web et les cartes routières et vous concentrez sur la seule chose qui est commune. Dans la grande majorité des cas, les détails que vous essayez de faire disparaître, le fait que les pages Web soient HTML, les liens sont des URL, les rues ont des limites de vitesse, les intersections ont des feux de circulation, etc. Si vous commencez votre implémentation avec une abstraction graphique, au moment où vous mettez en œuvre ces autres détails, vous vous mettez dans un sale pétrin. Il est préférable de commencer par d'autres abstractions plus importantes en tant que blocs de construction et de les relier pour former un graphique. Bien sûr, vous n'obtiendrez pas l'algorithme de chemin le plus court gratuitement pour votre carte routière, par exemple, mais vous êtes probablement intéressé par l'itinéraire le plus rapide, pour lequel vous avez besoin de limitations de vitesse, de feux de circulation et d'autres informations.

Je suppose que ce que j'essaie de dire, c'est que je vois des utilisations très limitées pour une bibliothèque de graphes génériques. C'est bien que nous ayons la Boost Graph Library, mais AFAIK, peu de gens l'utilisent.