20 août 2010

Les problèmes du Dr. Decay

Point d'interrogationCette série d'articles a beau être toute nouvelle, elle se base sur un principe vieux comme le monde : je pose une problème de conception ou d'architecture logicielle, vous me proposez des solutions, puis je vous propose ma solution. C'est un challenge - il n'y a rien à gagner, sauf peut être mon respect (mais puisque vous lisez ces lignes, je vous respecte déjà.

On va commencer par quelque chose qui parait simple, mais qui ne l'est pas nécessairement : le problème sommet/arc dans un graphe.

Le Dr. Decay, maître du mal et invité anonyme régulier du blog de Victor Nicollet a besoin d'une librairie de gestion de graphes. Il considère en effet que bien que son intelligence supérieure lui permet de résoudre des problèmes complexes en un temps dérisoire, certains plans qu'il fomente pour le futur nécessite des traitements automatisés - et beaucoup de ces traitements peuvent être ramenés à un problème de théorie des graphes.

En particuliers, ses besoins sont les suivants :

  • la librairie supporte la création de multigraphes.
  • La librairie doit autoriser la création de graphes orientés ou de graphes non orientés.
  • Connaissant un des sommets du graphe, le Dr. Decay souhaite obtenir la liste des sommets adjacents.
  • Connaissant un des arcs du graphe, le Dr. Decay souhaite obtenir les sommets qu'il relie.

Mais le Dr. Decay est un puriste, avec des connaissance assez pointues en architecture logicielle. En particulier, avant de vous acheter ce composant, il souhaite s'assurer de certains points particuliers :

  • Il aime la conception orientée objet. Il souhaite donc que la conception de la librairie suive ce paradigme.
  • Il souhaite pouvoir associer un poids à chaque arc, mais ne sait pas encore à quoi ce poids va ressembler (le même type est utilisé pour tous les arcs du graphe).
  • Il souhaite en outre associer des propriétés et des comportements à chaque sommet, mais il n'a pas encore décidé lesquels (le même type est utilisé pour tous les sommets du graphe).
  • Il n'aime pas les dépendances circulaires, et ne souhaite en voir aucune dans votre proposition.

Bien entendu, il s'attends à obtenir des solutions de grande qualité, et afin de choisir la meilleur, il prendre le temps de considérer certains points pratiques, comme l'élégance de la conception, la qualité des algorithmes induits par cette conception - parce que si le graphe l'empêche d'écrire des algorithmes rapides, il en sera fort chagriné - ou les contraintes mémoire induites - il aimerait éviter de louer les serveurs de google pour stocker un graphe de taille importante.

Pouvez-vous proposer une conception originale au Dr. Decay qui lui permette d'atteindre ses objectifs tout en satisfaisant aux contraintes qu'il impose ?

Commentaires

1. Le vendredi, août 20 2010, 16:35 par Romain Verdier

Du côté .NET, QuickGraph a bonne réputation. Pour C++, il y a toujours Boost avec sa BGL. (Note : vérifier qu'ils supportent les multigraphes)

2. Le vendredi, août 20 2010, 19:24 par Emmanuel Deloget

Du côté .NET, QuickGraph a bonne réputation. Pour C++, il y a toujours Boost avec sa BGL. (Note : vérifier qu'ils supportent les multigraphes)

QuickGraph réponds au besoin. BGL supporte les multigraphes et correspond aussi au besoin. En fait, je soupçonne toute les librairies de correspondre au besoin, modulo celles qui sont mal pensée et recèlent ici et là quelques dépendances circulaires.

Ceci dit, avec wattzillion de librairies de gestion de graphes, il est évident qu'il y en a au moins une qui réponds au problème. L'idée de base du challenge, c'est de proposer votre conception, pas celle des autres :)

Promis, la prochaine fois j'essaierai de vous pondre quelque chose qui n'est pas directement trouvable sur internet :)

Ajouter un commentaire

Les commentaires peuvent être formatés en utilisant une syntaxe wiki simplifiée.

Fil des commentaires de ce billet