c++ - Possible scope issues with my implementation of Dijkstra's shortest path algorithm in OpenMP? -

i've been working on small program calculates shortest paths every vertex in given graph using openmp split calculations between multiple threads instead of doing 1 vertex @ time. while current implementation works, want make can read graph data in file in format "vertex1 vertex2 weight" graphs aren't hard-coded program.

sources here: http://pastebin.com/bkr7qysb

compiled follows:

g++ -fopenmp graphtest.cpp weightedgraph.cpp -o dijkstra 

using following data input:

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 

my output is:

enter filename: lol.out printing edges 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 source vertex balls. format (start, end) : cost. (balls, balls : cost 0) (balls, derp : cost 60)  [thread:0] showing single-source shortest path run source vertex cox. format (start, end) : cost. (cox, cox : cost 0) (cox, narf : cost 10)  [thread:1] showing single-source shortest path run source vertex derp. format (start, end) : cost. (derp, derp : cost 0) (derp, cox : cost 30)  [thread:1] showing single-source shortest path run source vertex foo. format (start, end) : cost. (foo, foo : cost 0) (foo, narf : cost 50)  [thread:2] showing single-source shortest path run source vertex narf. format (start, end) : cost. (narf, narf : cost 0) (narf, cox : cost 10)  [thread:2] showing single-source shortest path run source vertex pie. format (start, end) : cost. (pie, pie : cost 0) (pie, cox : cost 15) 

this incorrect - it's supposed print shortest path vertex every other vertex in graph, , yet here it's printing shortest path (which 0) , path 1 of directly adjacent neighbors. it's not traversing graph @ all. weirdest part, however, uncommenting huge block near end of graphtest.cpp , commenting out file-handling code graph data hard-coded program, works fine:

printing edges 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 source vertex balls. format (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 source vertex cox. format (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 source vertex derp. format (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 source vertex foo. format (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 source vertex narf. format (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 source vertex pie. format (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) 

i have no idea what's going on here. thing can think of somewhere going out of scope , causing graph object behave oddly, if true both outputs should've been wrong... smarter me can run , me figure out went wrong.

i'll mention issues saw while reading through code:

1. notice edge map indexed pair, have implemented here must directed graph. because indexing ( vi, vj ), edges ( v0, v1 ) , ( v1, v0 ) distinct , have different values ( 1 may not exist! ). should think of way manage edges looking them isn't dependent on order.

2. i don't understand why using char*s in code relies heavily on standard template library. strings friend!

now, think problem re-inserting vertices. in code, don't check make sure vertex adding doesn't exist in graph. instead, allocate new vertex , put in vertex map. if there vertex name already, overwritten in map , lose reference data. hence, have memory leak, because replaced vertex never deleted.

so, if input file is:

narf balls 50 foo narf 10

your code create , add narf vertex on both lines. difference see far, significant , gives pretty costly bug memory leak.

as side note, don't see value in having edge object. can store information edge in each vertices _neighbors list. make list map, make adjacent vertex's name key , make cost value:

_neighbormap[ v0.name() ] = cost;

having edge type seems add lot of unnecessary references , complexity. thought...

as @ code further, see never deleting vertex or edge objects. if not want use dynamic memory allocation, make graph use instances of vertex instead of pointers. these small objects, aren't going cost in terms of instructions via copy in doing like:

_internalvertexmap[ "v0" ] = vertex( "v0" );