source: golgotha/src/golg/solvegraph_breadth.cc

Last change on this file was 80, checked in by Sam Hocevar, 12 years ago
  • Adding the Golgotha source code. Not sure what's going to be interesting in there, but since it's all public domain, there's certainly stuff to pick up.
File size: 3.5 KB
Line 
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
12void 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
25g1_breadth_first_graph_solver_class::~g1_breadth_first_graph_solver_class()
26{
27  if (solve_graph)
28    i4_free(solve_graph);
29}
30
31
32int 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
44i4_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
70i4_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
87i4_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
Note: See TracBrowser for help on using the repository browser.