1  /********************************************************************** <BR>


2  This file is part of Crack dot Com's free source code release of


3  Golgotha. <a href="http://www.crack.com/golgotha_release"> <BR> for


4  information about compiling & licensing issues visit this URL</a>


5  <PRE> If that doesn't help, contact Jonathan Clark at


6  golgotha_source@usa.net (Subject should have "GOLG" in it)


7  ***********************************************************************/


8 


9  #include "solvegraph_breadth.hh"


10  #include "search.hh"


11 


12  void g1_breadth_first_graph_solver_class::set_graph(g1_critical_graph_class *_graph)


13  {


14  graph=_graph;


15  if (!graph  !solve_graph  graph>criticals!=nodes)


16  {


17  if (solve_graph)


18  i4_free(solve_graph);


19 


20  nodes = graph>criticals;


21  solve_graph = (solve_node*)i4_malloc(nodes*sizeof(solve_node), "solve_graph");


22  }


23  }


24 


25  g1_breadth_first_graph_solver_class::~g1_breadth_first_graph_solver_class()


26  {


27  if (solve_graph)


28  i4_free(solve_graph);


29  }


30 


31 


32  int compare_nodes(const g1_breadth_first_graph_solver_class::solve_node *a,


33  const g1_breadth_first_graph_solver_class::solve_node *b)


34  {


35  // smallest length last


36  if (b>length > a>length)


37  return 1;


38  else if (b>length < a>length)


39  return 1;


40  else


41  return 0;


42  }


43 


44  i4_bool g1_breadth_first_graph_solver_class::add_node(g1_graph_node node, g1_graph_node from,


45  i4_float len)


46  {


47  if (solve_graph[node].ref && solve_graph[node].length<len)


48  // found better one already


49  return i4_F;


50 


51  // store current path graph


52  solve_graph[node].ref = from;


53  solve_graph[node].length = len;


54 


55  // add into heap


56  w32 loc;


57  solve_node test(node,len);


58 


59  if (heap.size())


60  {


61  i4_bsearch(&test, loc, &heap[0], (w32)heap.size(), compare_nodes);


62  heap.add_at(test, loc);


63  }


64  else


65  heap.add(test);


66 


67  return i4_T;


68  }


69 


70  i4_bool g1_breadth_first_graph_solver_class::get_next_node(g1_graph_node &node, i4_float &len)


71  {


72  w32 loc;


73 


74  if ((loc=heap.size())==0)


75  // nothing left in heap


76  return i4_F;


77 


78  // get last node (shortest) & remove


79  loc;


80  node = heap[loc].ref;


81  len = heap[loc].length;


82  heap.remove(loc);


83 


84  return i4_T;


85  }


86 


87  i4_bool g1_breadth_first_graph_solver_class::path_solve(g1_graph_node start_node,


88  g1_graph_node end_node,


89  w8 group_size, w8 grade,


90  i4_float *point, w16 &points)


91  {


92  g1_graph_node node;


93  i4_float len;


94 


95  clear_heap();


96  clear_solve();


97 


98  if (!start_node  !end_node)


99  return i4_F;


100 


101  add_node(start_node, 0, 0);


102 


103  while (get_next_node(node, len))


104  {


105  g1_critical_graph_class::connection_class *c = graph>critical[node].connection;


106  for (int i=0; i<graph>critical[node].connections; i++, c++)


107  if (group_size<=c>size[grade])


108  add_node(c>ref, node, len + c>dist);


109  }


110 


111  points=0;


112 


113  if (solve_graph[end_node].ref==0)


114  return i4_F;


115 


116  // count nodes


117  node = end_node;


118  points = 0;


119  while (node!=start_node)


120  {


121  point[points*2+0] = i4_float(graph>critical[node].x)+0.5;


122  point[points*2+1] = i4_float(graph>critical[node].y)+0.5;


123  points++;


124  node = solve_graph[node].ref;


125  }


126  point[points*2+0] = i4_float(graph>critical[start_node].x)+0.5;


127  point[points*2+1] = i4_float(graph>critical[start_node].y)+0.5;


128  points++;


129 


130  return i4_T;


131  }


132 

