[shootingstar] crash and weird results

[lapinos03]

software version: rev355 + shootingstar_sp_smart() sql function
testing platform: mac os leopard + xcode

symptom: by moving starting and end points around their respective edge (ie the generated fake point/segments remain on the same edge), changes the calculated path from time to time in a unlogical manner (reproductible case), sometimes produces no result at all.

diagnostic: with "no result" case data, the crash occurs in file: shootingstar_search.hpp function:

void gray_target(Edge e, Edge pe, Graph& g, int e_max_id)

at line 354:

m_Q.update(e);

...more specifically in mutable_queue.hpp at line 106:

c[current_pos] = x;

...resulting into an out-of-bounds error msg (* sorry, don't have memorized the exact message *). It occured when an edge_descriptor (u;v) was updated while its sibling (v;u) was already poped out of the queue. Debugging further revealed that both original and reverted edge_descriptors were assigned the same index in the index_array in mutable_queue.hpp

void push(const IndexedType& x) {
		c.push_back(x);
		/*set index-array*/
		index_array[ get(id, x) ] = c.size()-1;

function. (This 'index' value is also referred by graph[e].index).

solution: give a unique index value to each added edge to the graph by replacing, at lines 237 and 275 in file shooting_star_boost_wrapper.cpp, variable j by an incremental counter:

graph_add_edge<graph_t, edge_descriptor>(graph, 
 /*j*/edge_index++, //lapinos03 patch
 edges_array[j].id, edges_array[j].source, 
 edges_array[j].target, edges_array[j].cost, 
 edges_array[j].s_x, edges_array[j].s_y, 
 edges_array[j].t_x, edges_array[j].t_y, 
 adjacent_edges);

final word: well, took me 2 days of intense head-ache but looks to work fine and stable now ;-)