tests/test_a_star.nit

   1 module test_a_star
   2
   3 import a_star
   4
   5 #redef class Object
   6 #       redef fun debug_a_star do return true
   7 #end
   8
   9 class NamedNode
  10         super Node
  11
  12         redef type N: NamedNode
  13
  14         var name: String
  15
  16         init(graph: Graph[N, Link], name: String)
  17         do
  18                 self.name = name
  19                 super
  20         end
  21
  22         redef fun to_s do return "node:{name}"
  23 end
  24
  25 fun print_path(path: nullable Path[NamedNode]) do if path == null then
  26         print "null path"
  27 else
  28         var names = new Array[String]
  29         while not path.at_end_of_path do
  30                 var step = path.step
  31                 names.add(step.name)
  32         end
  33         print names.join(", ")
  34 end
  35
  36 # Graph
  37 #   a - b
  38 #  /   /
  39 # c - d - e
  40 fun case_simple
  41 do
  42         var graph = new Graph[NamedNode, Link]
  43
  44         var na = new NamedNode(graph, "a")
  45         var nb = new NamedNode(graph, "b")
  46         var nc = new NamedNode(graph, "c")
  47         var nd = new NamedNode(graph, "d")
  48         var ne = new NamedNode(graph, "e")
  49
  50         var lab = new Link(graph, na, nb)
  51         var lac = new Link(graph, na, nc)
  52         var lbd = new Link(graph, nb, nd)
  53         var lcd = new Link(graph, nc, nd)
  54         var lde = new Link(graph, nd, ne)
  55
  56         var context = new ConstantPathContext(graph)
  57
  58         var path = na.path_to(ne, 100, context)
  59         print_path(path)
  60 end
  61
  62 # Graph
  63 #   a - b
  64 #  /   /
  65 # c - d    e
  66 fun case_failed
  67 do
  68         var graph = new Graph[NamedNode,Link]
  69
  70         var na = new NamedNode(graph, "a")
  71         var nb = new NamedNode(graph, "b")
  72         var nc = new NamedNode(graph, "c")
  73         var nd = new NamedNode(graph, "d")
  74         var ne = new NamedNode(graph, "e")
  75
  76         var lab = new Link(graph, na, nb)
  77         var lac = new Link(graph, na, nc)
  78         var lbd = new Link(graph, nb, nd)
  79         var lcd = new Link(graph, nc, nd)
  80
  81         var context = new ConstantPathContext(graph)
  82
  83         var path = na.path_to(ne, 100, context)
  84         print_path(path)
  85 end
  86
  87 # Weighted graph
  88 #     a -2- b
  89 #    /     /
  90 #   3     1
  91 #  /     /
  92 # c -3- d -8- e
  93 fun case_weighted
  94 do
  95         var graph = new Graph[NamedNode,WeightedLink]
  96
  97         var na = new NamedNode(graph, "a")
  98         var nb = new NamedNode(graph, "b")
  99         var nc = new NamedNode(graph, "c")
 100         var nd = new NamedNode(graph, "d")
 101         var ne = new NamedNode(graph, "e")
 102
 103         var lab = new WeightedLink(graph, na, nb, 2)
 104         var lac = new WeightedLink(graph, na, nc, 3)
 105         var lbd = new WeightedLink(graph, nb, nd, 1)
 106         var lcd = new WeightedLink(graph, nc, nd, 3)
 107         var lde = new WeightedLink(graph, nd, ne, 8)
 108
 109         var context = new WeightedPathContext(graph)
 110
 111         var path = na.path_to(ne, 100, context)
 112         print_path(path)
 113 end
 114
 115 # Weighted graph
 116 #     a -2- b
 117 #    /     /
 118 #   3     1
 119 #  /     /
 120 # c -3- d -8- e
 121 fun case_weighted_too_long
 122 do
 123         var graph = new Graph[NamedNode,WeightedLink]
 124
 125         var na = new NamedNode(graph, "a")
 126         var nb = new NamedNode(graph, "b")
 127         var nc = new NamedNode(graph, "c")
 128         var nd = new NamedNode(graph, "d")
 129         var ne = new NamedNode(graph, "e")
 130
 131         var lab = new WeightedLink(graph, na, nb, 2)
 132         var lac = new WeightedLink(graph, na, nc, 3)
 133         var lbd = new WeightedLink(graph, nb, nd, 1)
 134         var lcd = new WeightedLink(graph, nc, nd, 3)
 135         var lde = new WeightedLink(graph, nd, ne, 8)
 136
 137         var context = new WeightedPathContext(graph)
 138
 139         var path = na.path_to(ne, 5, context)
 140         print_path(path)
 141 end
 142
 143 # Big weighted graph
 144 #     a -2- b -1- f -1- g
 145 #    /     /       \   /
 146 #   3     1        4  1
 147 #  /     /         \ /
 148 # c -3- d -8- e -2- h -2- i -3- j
 149 fun case_weighted_big
 150 do
 151         var graph = new Graph[NamedNode,WeightedLink]
 152
 153         var na = new NamedNode(graph, "a")
 154         var nb = new NamedNode(graph, "b")
 155         var nc = new NamedNode(graph, "c")
 156         var nd = new NamedNode(graph, "d")
 157         var ne = new NamedNode(graph, "e")
 158         var nf = new NamedNode(graph, "f")
 159         var ng = new NamedNode(graph, "g")
 160         var nh = new NamedNode(graph, "h")
 161         var ni = new NamedNode(graph, "i")
 162         var nj = new NamedNode(graph, "j")
 163
 164         var lab = new WeightedLink(graph, na, nb, 2)
 165         var lac = new WeightedLink(graph, na, nc, 3)
 166         var lbd = new WeightedLink(graph, nb, nd, 1)
 167         var lcd = new WeightedLink(graph, nc, nd, 3)
 168         var lde = new WeightedLink(graph, nd, ne, 8)
 169         var lbf = new WeightedLink(graph, nb, nf, 1)
 170         var lfg = new WeightedLink(graph, nf, ng, 1)
 171         var leh = new WeightedLink(graph, ne, nh, 2)
 172         var lhi = new WeightedLink(graph, nh, ni, 2)
 173         var lij = new WeightedLink(graph, ni, nj, 3)
 174         var lfh = new WeightedLink(graph, nf, nh, 4)
 175         var lgh = new WeightedLink(graph, ng, nh, 1)
 176
 177         var context = new WeightedPathContext(graph)
 178
 179         var path = na.path_to(nj, 100, context)
 180         print_path(path)
 181 end
 182
 183 case_simple
 184 case_failed
 185 case_weighted
 186 case_weighted_too_long
 187 case_weighted_big