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[N]], 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[NamedNode]]
  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[NamedNode](graph, na, nb)
  51         var lac = new Link[NamedNode](graph, na, nc)
  52         var lbd = new Link[NamedNode](graph, nb, nd)
  53         var lcd = new Link[NamedNode](graph, nc, nd)
  54         var lde = new Link[NamedNode](graph, nd, ne)
  55
  56         var context = new ConstantPathContext[NamedNode, Link[NamedNode]](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[NamedNode]]
  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[NamedNode](graph, na, nb)
  77         var lac = new Link[NamedNode](graph, na, nc)
  78         var lbd = new Link[NamedNode](graph, nb, nd)
  79         var lcd = new Link[NamedNode](graph, nc, nd)
  80
  81         var context = new ConstantPathContext[NamedNode, Link[NamedNode]](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 #  /3   /1
  90 # c -3 d -8 e
  91 fun case_weighted
  92 do
  93         var graph = new Graph[NamedNode,WeigthedLink[NamedNode]]
  94
  95         var na = new NamedNode(graph, "a")
  96         var nb = new NamedNode(graph, "b")
  97         var nc = new NamedNode(graph, "c")
  98         var nd = new NamedNode(graph, "d")
  99         var ne = new NamedNode(graph, "e")
 100
 101         var lab = new WeigthedLink[NamedNode](graph, na, nb, 2)
 102         var lac = new WeigthedLink[NamedNode](graph, na, nc, 3)
 103         var lbd = new WeigthedLink[NamedNode](graph, nb, nd, 1)
 104         var lcd = new WeigthedLink[NamedNode](graph, nc, nd, 3)
 105         var lde = new WeigthedLink[NamedNode](graph, nd, ne, 8)
 106
 107         var context = new WeightedPathContext[NamedNode, WeigthedLink[NamedNode]](graph)
 108
 109         var path = na.path_to(ne, 100, context)
 110         print_path(path)
 111 end
 112
 113 # Weighted graph
 114 #   a -2 b
 115 #  /3   /1
 116 # c -3 d -8 e
 117 fun case_weighted_too_long
 118 do
 119         var graph = new Graph[NamedNode,WeigthedLink[NamedNode]]
 120
 121         var na = new NamedNode(graph, "a")
 122         var nb = new NamedNode(graph, "b")
 123         var nc = new NamedNode(graph, "c")
 124         var nd = new NamedNode(graph, "d")
 125         var ne = new NamedNode(graph, "e")
 126
 127         var lab = new WeigthedLink[NamedNode](graph, na, nb, 2)
 128         var lac = new WeigthedLink[NamedNode](graph, na, nc, 3)
 129         var lbd = new WeigthedLink[NamedNode](graph, nb, nd, 1)
 130         var lcd = new WeigthedLink[NamedNode](graph, nc, nd, 3)
 131         var lde = new WeigthedLink[NamedNode](graph, nd, ne, 8)
 132
 133         var context = new WeightedPathContext[NamedNode, WeigthedLink[NamedNode]](graph)
 134
 135         var path = na.path_to(ne, 5, context)
 136         print_path(path)
 137 end
 138
 139 case_simple
 140 case_failed
 141 case_weighted
 142 case_weighted_too_long