dependency graph

deg_graph.ml

type node = { cmd:  string; 
              deps: node list }


let nodeA = { cmd = "A"; 
              deps = [] }

let nodeB = { cmd = "B";
              deps = [] }

let nodeC = { cmd = "C";
              deps = [nodeA;nodeB] }

let nodeD = { cmd = "D";
              deps = [nodeC] } 

let nodeE = { cmd = "E";
              deps = [] } 

let nodeF = { cmd = "F";
              deps = [nodeE] }

let nodeG = { cmd = "G";
              deps = [nodeF;nodeD] }


let rec find_deps n = 
  let rec aux deps deplst = match deps with
    []    -> List.rev deplst
  | d::ds -> Printf.printf "Visiting %s\n" d.cmd ; 
             if List.mem d deplst then
               aux d.deps ((aux ds deplst)  )
             else
               aux d.deps ((aux ds (d::deplst)))  
                                  in
  aux n.deps [] ;;  

let deplst' = ref [nodeG] ;;

let rec find_deps' n = 
  (*let deplst' = ref [] in*)
  let rec aux deps deplst = match deps with
    []    -> List.rev deplst
  | d::ds -> Printf.printf "Visiting %s\n" d.cmd ; 
             deplst' := (d::(!deplst'));
             if List.mem d deplst then
               aux ds ((aux d.deps deplst)  )
             else
               aux ds ((aux d.deps (d::deplst)))  
                                  in
  aux n.deps [] ;;  

List.iter (fun x -> Printf.printf "%s" x.cmd) (find_deps nodeG);;
Printf.printf "\n";;

List.iter (fun x -> Printf.printf "%s" x.cmd) (find_deps' nodeG);;
Printf.printf "\n";;
List.iter (fun x -> Printf.printf "%s" x.cmd) (!deplst');;
Printf.printf "\n";;