Advertisement
Guest User

Untitled

a guest
Jan 25th, 2020
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.92 KB | None | 0 0
  1. let k = 3
  2. let errs = 0
  3. let L= ["AAA"; "AAC"; "ACA"; "CAC"; "CAA"; "ACG"; "CGC"; "GCA"; "ACT";"CTT";"TTA";"TAA"]
  4.  
  5. type Edge = { src:string; dest:string; v:char }
  6. type Node = { label:string; adjacents:Edge list }
  7. type Graph = Node list
  8.  
  9. let wordsToEdges k words =
  10. List.map(fun (s:string) -> {src=s.[0..k-2]; dest=s.[1..k-1]; v=s.[k-1]}) words
  11.  
  12. let edges = wordsToEdges k L
  13.  
  14. let edgesToGraph edges :Graph =
  15. edges |>
  16. List.groupBy (fun e -> e.src) |>
  17. List.map (fun (n,l) -> { label=n; adjacents=l})
  18.  
  19. let graph = edgesToGraph edges
  20.  
  21. let transposeGraph (graph:Graph) =
  22. graph |>
  23. List.fold (fun acc elem -> acc @ elem.adjacents) [] |>
  24. List.map (fun e -> { src=e.dest; dest=e.src; v=e.v }) |>
  25. edgesToGraph
  26.  
  27. let gt = transposeGraph graph
  28.  
  29. let getPossibleEdges (graph:Graph) (k:int) =
  30. let nodes = List.map (fun a -> a.label) graph
  31. List.allPairs nodes nodes |>
  32. List.filter (fun (a,b) -> a.[1 ..] = b.[.. k-3]) |>
  33. List.map (fun (a,b) -> { src=a; dest=b; v=b.[k-2]})
  34.  
  35. let alledges = getPossibleEdges graph k
  36.  
  37. let extractPath (n:string) (graph:Graph) :(string*Graph) =
  38. let
  39.  
  40. let isSemiEulerian (graph:Graph) =
  41. let edges = graph |> List.collect (fun n -> n.adjacents)
  42. let inEdges = List.countBy (fun e -> e.dest) edges |> List.sortBy (fun (a,_) -> a)
  43. let outEdges = List.countBy (fun e -> e.src) edges |> List.sortBy (fun (a,_) -> a)
  44. match List.fold2 (fun deg (_,i) (_,o) -> deg + abs (i - o)) 0 inEdges outEdges with
  45. | 0 -> ""
  46. | 2 ->
  47. let startingNode = List.fold2 (fun _ (n,i) (_,o) -> if o > i then n) null inEdges outEdges
  48. let (mainPath,workingGraph) = extractPath startingNode graph
  49. | _ -> ""
  50.  
  51.  
  52.  
  53.  
  54. isSemiEulerian graph
  55.  
  56. let list1 = edges |> List.groupBy (fun e -> e.src)
  57. let list2 = edges |> List.groupBy (fun e -> e.dest)
  58. //let scores:int list = List.map2 list1 list2 (fun (_,a) (_,b) -> a.Length - b.Length)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement