Возможные проблемы с областью применения моей реализации алгоритма кратчайшего пути Дейкстры в OpenMP?

Question

Я работал над небольшой программой, которая вычисляет кратчайшие пути для каждой вершины в данном графе, используя OpenMP для разделения вычислений между несколькими потоками вместо выполнения одной вершины за раз. Хотя моя текущая реализация работает, я хочу сделать так, чтобы я мог читать данные графика из файла в формате «vertex1 vertex2 weight», чтобы графики не были жестко запрограммированы в программе.

Источники здесь: http://pastebin.com/bkR7QysB

Составлено следующим образом:

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

Использование следующих данных в качестве ввода:

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

мой вывод:

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)

Это, очевидно, неверно - он должен печатать кратчайший путь от вершины ко всем остальным вершинам графа, и все же здесь он печатает только кратчайший путь к себе (который всегда равен 0) и путь только к ОДНОЙ из его непосредственно смежные соседи. Это не пересекает график вообще. Самая странная часть, однако, заключается в том, что раскомментируя этот огромный блок в конце GraphTest.cpp и комментируя код обработки файла, чтобы графические данные были жестко запрограммированы в программе, все работает нормально:

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)

Честно говоря, я понятия не имею, что здесь происходит. Единственное, о чем я могу думать, это то, что что-то где-то выходит из области видимости слишком рано и заставляет мой графовый объект вести себя странно, но если бы это было так, то оба выхода должны были быть неправильными ... Надеюсь, кто-то умнее меня сможет запустить это и поможет мне выяснить, что пошло не так.

Answer 1

Я упомяну некоторые проблемы, с которыми я столкнулся при чтении вашего кода:

1. Обратите внимание, что ваша карта ребер проиндексирована парой, поэтому то, что вы здесь реализовали , должно быть ориентированным графом. Поскольку вы индексируете по (vi, vj), ребра (v0, v1) и (v1, v0) различны и будут иметь разные значения (один может даже не существовать!). Вам, вероятно, следует подумать о способах управления краями, чтобы их поиск не зависел от порядка.

2. Я не понимаю, почему вы используете char * s в коде, который сильно зависит от стандартной библиотеки шаблонов. Струны твой друг!

Теперь, я думаю, проблема в том, что вы заново вставляете вершины. В вашем коде вы не проверяете, чтобы убедиться, что добавляемая вами вершина еще не существует в графе. Вместо этого вы просто выделяете новую вершину и помещаете ее в свою карту вершин. Если вершина с таким именем уже существует, она перезаписывается на карте, и вы теряете единственную ссылку на эти данные. Следовательно, у вас есть утечка памяти, потому что замененная вершина никогда не удаляется.

Итак, если ваш входной файл:

Нарф шары 50 фу нарф 10

Ваш код создаст и добавит вершину narf в обеих строках. Это единственное различие, которое я вижу до сих пор, но оно существенное и дает довольно дорогостоящую ошибку, а также утечку памяти.

В качестве примечания, я не обязательно вижу значение наличия краевого объекта. Вы можете легко хранить всю информацию для ребра в каждом списке вершин _neighbors. Сделайте этот список картой, сделайте имя смежной вершины ключом и сделайте стоимость значением:

_neighborMap [v0.name ()] = стоимость;

Наличие типа ребра просто добавляет много ненужных ссылок и сложности. Просто мысль ...

Пока я смотрю на ваш код, я вижу, что вы на самом деле никогда не удаляете объекты Vertex или Edge. Если вы не хотите использовать динамическое выделение памяти, просто заставьте ваш Graph использовать экземпляры Vertex вместо указателей. Это очень маленькие объекты, поэтому вы не будете тратить много времени на дополнительные инструкции с помощью копирования, просто делая что-то вроде:

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