Fonctions graphiques communes et utiles?

Question

J'implémente une bibliothèque graphique simple pour mon projet uni et puisque c'est la première fois que j'ai affaire à des graphes, j'aimerais savoir quelles sont les fonctions que vous considérez les plus courantes et les plus utiles pour les implémentations de Graph ...

jusqu'à présent, j'ai ceci:

• graphInitialize()
• graphInsertVertex()
• graphRemoveVertex()
• graphGetVertex()
• graphGetVertexValue() (non encore mis en œuvre, pas sûr si je vais en avoir besoin)
• graphInsertEdge()
• graphRemoveEdge()
• graphLinkVertices() (ce qui appelle graphInsertEdge deux fois pour le graphique bi-directionnel)
• graphUnlinkVertices() (cela appelle graphRemoveEdge deux fois pour le graphique bi-directionnel)
• graphDestroy()

Je sais que je manque une fonction ne déterminer le chemin le plus court, mais je pars que pour le dernier .. Pensez-vous que je manque une fonction commune/utile?

Answer 1

En général:

• getVertexCount
• getEdgeCount
• transposeGraph (inverse toutes les arêtes)
• getEdgeWeight
• setEdgeWeight

Plus de choses algorithmiques:

• countConnectedComponents
• countStronglyConnectedComponents
• computeAllPairsShortestPath
• computeShortestPath (source, puits)
• computeSingleSourceShortestPath (source)
• computeMaxFlow (source, puits)
• isTree
• isBipartite
• isAcyclic
• topologicSort
• getDiameter
• getPrincipleVertex

... cela pourrait durer éternellement.

Answer 2

Quelques autres choses à considérer:

• Ajout d'attributs à un nœud ou un bord, comme une pondération.
• Quel type de graphique créez-vous? Dirigé, non orienté etc ...
• Peut-être que des méthodes pour vous donner des informations générales sur le graphique? Nombre de nœuds, nombre de bords, etc.
• Puis-je obtenir facilement le degré d'un nœud?
• Pouvez-vous vérifier si un nœud ou une arête est déjà dans le graphique?

Je vous recommande de jeter un oeil à d'autres bibliothèques de graphes. Voici quelques-unes:

• JUNG - Java
• Networkx - Python
• Boost Graph Library - C++

Answer 3

Comme une note de côté, si vous écrivez votre bibliothèque dans un style POO, puis vous pouvez supprimer le préfixe «graphique» sur toutes vos méthodes car il serait redondant. Sinon, s'il s'agit d'une bibliothèque procédurale, vous pouvez vouloir définir un espace de noms.

Answer 4

Ce que vous pouvez trouver entierly utile dépend de ce que vous allez utiliser la bibliothèque pour ...

Quelques autres choses que vous pourriez trouver useful-

• une fonction qui renvoie tous les bords qui se touchent un sommet
• une fonction qui renvoie tous les sommets qui sont raccordés à un sommet avec une arête
• dikjstra algorithm

Certaines applications requièrent que chaque arête ou sommet ait une certaine propriété telle que distance ou weight. Bien sûr, vous pouvez toujours ajouter de plus en plus de membres à votre classe Edge et Vertex, mais il existe des moyens de le faire de manière générique sans encombrer vos classes avec des choses que vous pourriez ne pas avoir besoin d'utiliser.