Search Routines, Continued

Yay! I finished my taxes. I hope to post some more F# stuff over the coming weekend.

In the meantime, here is a first try at general purpose depth/breadth-first search routine. It's not really generic yet, being based on a specific data structure. However, my goal is, over the next few days, to turn it into a nice generic search routine that I can use in a number of applications. The final version will implement the A* search rather than depth/breadth-first search. THAT is what I will finally marry with the semantic network.

Also, the code below is very, very rough; rather grim and awfull, actually. I wrote it quickly last night in between various chores and while worrying about a half-dozen other things. I mainly post it as a way of forcing myself to stay active on the blog here.

(Presented “as-is” and without warranty or implied fitness; use at your own risk.)

// Rough-draft code, hammered-in between eating dinner, 
// playing with my pet rabbit to keep him from becoming feral,
// worrying about taxes, etc.
//
// Take it with a grain of salt 
// and an eye towards what it may become.

open System.Collections.Generic


type Node = {
  id:string
  mutable links:(Node*int) list }
  
let defaultNode = { id=""; links=[] }

type Path = int*Node*(Node list)


let search =

  let hashLoop = new HashSet<string>()
  
  let rec search0 (g:string)
                  (pl:Path list) =
                  
    let rec expand (c:int)
                   (l:(Node*int) list)
                   (nl:Node list)
                   (pl:Path list) =
      match l with
      | [] -> pl
      | (ln,lc)::t ->
          match hashLoop.Add ln.id with
          // Breadth-first.
          //| true  -> expand c t nl (List.append pl [(c+lc,ln,nl)]) 
          // Depth-first.
          | true  -> expand c t nl ((c+lc,ln,nl)::pl) 
          | false -> expand c t nl pl
          
    match pl with
    | [] -> None
    | (c,n,nl)::pt -> 
        match n.id=g with 
        | true -> Some(c,n::nl)
        | false -> 
            search0 g (expand c n.links nl pt) 
    
  let search1 (s:Node) gid =
    hashLoop.Clear()
    search0 gid [(0,s,[])]
    
  search1
  

// This is the same network used for 
// search examples in Patrick Henry Winston's 
// Artificial Intelligence, 3rd Edition, p.64ff  
  
let s = { defaultNode with id="s" }
let a = { defaultNode with id="a" }
let b = { defaultNode with id="b" }
let c = { defaultNode with id="c" }
let d = { defaultNode with id="d" }
let e = { defaultNode with id="e" }
let f = { defaultNode with id="f" }
let g = { defaultNode with id="g" }

s.links <- [(a,3);(d,4)]
a.links <- [(s,3);(b,4);(d,5)]
b.links <- [(a,4);(c,4);(e,5)]
c.links <- [(b,4)]
d.links <- [(s,4);(a,5);(e,2)]
e.links <- [(b,5);(d,2);(f,4)]
f.links <- [(e,4);(g,3)]
g.links <- [(f,3)]

          
let x0 = search s "c"


System.Console.ReadLine() |> ignore