Problèmes de portée possibles avec ma mise en œuvre de l'algorithme de plus court chemin de Dijkstra dans OpenMP?

Question

J'ai travaillé sur un petit programme qui calcule les chemins les plus courts pour chaque sommet dans un graphique donné en utilisant OpenMP pour séparer les calculs entre plusieurs threads au lieu de faire un seul sommet à la fois. Bien que mon implémentation actuelle fonctionne, je veux que je puisse lire les données du graphique à partir d'un fichier au format "vertex1 vertex2 weight" afin que les graphiques ne soient pas codés en dur dans le programme.

Les sources sont ici: http://pastebin.com/bkR7QysB

Compilé comme suit:

g++ -fopenmp GraphTest.cpp WeightedGraph.cpp -o dijkstra 

En utilisant les données suivantes en entrée:

foo derp 50 
narf balls 30 
foo balls 20 
balls derp 60 
derp narf 40 
derp cox 30 
foo narf 50 
narf pie 99 
cox pie 15 
cox narf 10 

ma sortie est:

Enter filename: lol.out 
Printing all edges currently in graph: 
(foo, derp) : cost 50 
(narf, balls) : cost 30 
(foo, balls) : cost 20 
(balls, derp) : cost 60 
(derp, narf) : cost 40 
(derp, cox) : cost 30 
(foo, narf) : cost 50 
(narf, pie) : cost 99 
(cox, pie) : cost 15 
(cox, narf) : cost 10 

[thread:0] Showing single-source shortest path run for source vertex balls. Format is (start, end) : cost. 
(balls, balls : cost 0) 
(balls, derp : cost 60) 

[thread:0] Showing single-source shortest path run for source vertex cox. Format is (start, end) : cost. 
(cox, cox : cost 0) 
(cox, narf : cost 10) 

[thread:1] Showing single-source shortest path run for source vertex derp. Format is (start, end) : cost. 
(derp, derp : cost 0) 
(derp, cox : cost 30) 

[thread:1] Showing single-source shortest path run for source vertex foo. Format is (start, end) : cost. 
(foo, foo : cost 0) 
(foo, narf : cost 50) 

[thread:2] Showing single-source shortest path run for source vertex narf. Format is (start, end) : cost. 
(narf, narf : cost 0) 
(narf, cox : cost 10) 

[thread:2] Showing single-source shortest path run for source vertex pie. Format is (start, end) : cost. 
(pie, pie : cost 0) 
(pie, cox : cost 15) 

Ceci est évidemment incorrect - il est supposé imprimer le plus court chemin d'un sommet à tous les autres sommets du graphique, mais ici il imprime seulement le plus court chemin vers lui-même (qui est toujours 0) et le chemin vers un seul directement voisins adjacents. Il ne traverse pas du tout le graphique. Le plus étrange partie, cependant, est que décommentant ce bloc énorme à la fin de GraphTest.cpp et commenter le code de fichier de traitement de sorte que les données de graphique est codé en dur dans le programme, tout fonctionne bien:

Printing all edges currently in graph: 
(foo, derp) : cost 50 
(narf, balls) : cost 30 
(foo, balls) : cost 20 
(balls, derp) : cost 60 
(derp, narf) : cost 40 
(derp, cox) : cost 30 
(foo, narf) : cost 50 
(narf, pie) : cost 99 
(cox, pie) : cost 15 
(cox, narf) : cost 10 

[thread:0] Showing single-source shortest path run for source vertex balls. Format is (start, end) : cost. 
(balls, balls : cost 0) 
(balls, foo : cost 20) 
(balls, narf : cost 30) 
(balls, cox : cost 40) 
(balls, pie : cost 55) 
(balls, derp : cost 60) 

[thread:0] Showing single-source shortest path run for source vertex cox. Format is (start, end) : cost. 
(cox, cox : cost 0) 
(cox, narf : cost 10) 
(cox, pie : cost 15) 
(cox, derp : cost 30) 
(cox, balls : cost 40) 
(cox, foo : cost 60) 

[thread:1] Showing single-source shortest path run for source vertex derp. Format is (start, end) : cost. 
(derp, derp : cost 0) 
(derp, cox : cost 30) 
(derp, narf : cost 40) 
(derp, pie : cost 45) 
(derp, foo : cost 50) 
(derp, balls : cost 60) 

[thread:1] Showing single-source shortest path run for source vertex foo. Format is (start, end) : cost. 
(foo, foo : cost 0) 
(foo, balls : cost 20) 
(foo, derp : cost 50) 
(foo, narf : cost 50) 
(foo, cox : cost 60) 
(foo, pie : cost 75) 

[thread:2] Showing single-source shortest path run for source vertex narf. Format is (start, end) : cost. 
(narf, narf : cost 0) 
(narf, cox : cost 10) 
(narf, pie : cost 25) 
(narf, balls : cost 30) 
(narf, derp : cost 40) 
(narf, foo : cost 50) 

[thread:2] Showing single-source shortest path run for source vertex pie. Format is (start, end) : cost. 
(pie, pie : cost 0) 
(pie, cox : cost 15) 
(pie, narf : cost 25) 
(pie, derp : cost 45) 
(pie, balls : cost 55) 
(pie, foo : cost 75) 

Honnêtement, je n'ai aucune idée de ce qui se passe ici. La seule chose à laquelle je puisse penser, c'est que quelque chose sort de sa portée trop tôt et fait que mon objet graphique se comporte bizarrement, mais si c'était vrai alors les deux sorties auraient dû être fausses ... J'espère que quelqu'un plus intelligent que moi peut courir ceci et m'aider à comprendre ce qui s'est mal passé.

Answer 1

Je vais mentionner quelques questions que j'ai vu en lisant dans votre code:

1. Notez que votre carte de bord est indexé par une paire, donc ce que vous avez mis en œuvre ici doit être un graphe orienté. Parce que vous êtes indexé par (vi, vj), les bords (v0, v1) et (v1, v0) sont distincts et auront des valeurs différentes (on peut même pas exister!). Vous devriez probablement penser à un moyen de gérer vos bords de sorte que les regarder ne dépend pas de l'ordre. Je ne comprends pas pourquoi vous utilisez char * s dans le code qui repose fortement sur la bibliothèque de modèles standard. Les cordes sont ton ami!

Maintenant, je pense que le problème est que vous réinsérez des sommets. Dans votre code, vous n'effectuez aucune vérification pour vous assurer que le sommet que vous ajoutez n'existe pas déjà dans le graphique. Au lieu de cela, vous venez d'allouer un nouveau sommet et de le placer dans votre vertex map. S'il existe déjà un sommet avec ce nom, il est écrasé dans la carte et vous perdez votre seule référence à cette donnée. Par conséquent, vous avez une fuite de mémoire, car le sommet remplacé n'est jamais supprimé.

Donc, si votre fichier d'entrée est:

balles Narf 50 foo narf 10

Votre code va créer et ajouter un sommet narf sur les deux lignes.C'est la seule différence que je vois jusqu'à présent, mais elle est significative et donne un bogue assez coûteux ainsi qu'une fuite de mémoire.

En note, je ne vois pas nécessairement la valeur d'avoir un objet de bord. Vous pouvez facilement stocker toutes les informations pour une arête dans chaque liste de sommets. Faire de cette liste une carte, faire un nom de sommet adjacent à la clé et faire en sorte que le coût en soit la valeur:

_neighborMap [v0.name()] = cost; Avoir le type de bord semble juste ajouter beaucoup de références inutiles et de complexité. Juste une pensée ...

En regardant de plus près votre code, je vois que vous ne supprimez jamais d'objets Vertex ou Edge. Si vous ne souhaitez pas utiliser l'allocation de mémoire dynamique, faites en sorte que votre graphique utilise des instances de Vertex au lieu de pointeurs. Ce sont des objets très petits, de sorte que vous ne vont pas vous coûter beaucoup en termes d'instructions supplémentaires par copie en faisant simplement quelque chose comme:

_internalVertexMap[ "v0" ] = Vertex("v0");